FPGA implementation tool speed has not kept pace with the increase in design size and FPGA density. It is difficult to parallelize place-and-route algorithms without sacrificing determinism or quality of results. We address the implementation problem using a divide-and-conquer approach. The PATIS automatic floorplanner enables dynamic modular design, which sacrifices some design speed and area optimization for faster implementation of layout changes, including addition of debug logic. Automatic generation of a timing-driven floorplan for a partially reconfigurable design aims to remove the need for implementation iterations to meet all constraints. Floorplan speculation may anticipate small changes to a design. Although PATIS supports incremental design, complete re-implementation is still rapid because the partial bitstream for each block is generated by independent concurrent invocations of the standard Xilinx tools. / Master of Science

FPGA implementation tool turnaround time has unfortunately not kept pace with FPGA density advances. It is difficult to parallelize place-and-route algorithms without sacrificing determinism or quality of results. We approach the problem in a different way for development environments in which some circuit speed and area optimization may be sacrificed for improved implementation and debug turnaround. The PATIS floorplanner enables dynamic modular design, which accelerates non-local changes to the physical layout arising from design exploration and the addition of debug circuitry. We focus in this work on incremental and speculative floorplanning in PATIS, to accommodate minor design changes and to proactively generate possible floorplan variants. Current floorplan topology is preserved to minimize ripple effects and maintain reasonable module aspect ratios. The design modules are run-time reconfigurable to enable concurrent module implementation by independent invocations of the standard FPGA tools running on separate cores or hosts. / Master of Science

The floorplanning problem aims to arrange a set of rectangular modules on a rectangular chip area so as to optimize an appropriate measure of performance. This problem is known to be NP-hard, and is particularly challenging if the chip dimensions are fixed. Fixed-outline floorplanning is becoming increasingly important as a tool to design flows in the hierarchical design of Application Specific Integrated Circuits and System-On-Chip. Therefore, it has recently received much attention. A two-stage convex optimization methodology is proposed to solve the fixed-outline floorplanning problem. It is a global optimization problem for wirelength minimization. In the first stage, an attractor-repeller convex optimization model provides the relative positions of the modules on the floorplan. The second stage places and sizes the modules using convex optimization. Given the relative positions of the modules from the first stage, a Voronoi diagram and Delaunay triangulation method is used to obtain a planar graph and hence a relative position matrix connecting the two stages. An efficient method for generating sparse relative position matrices and an interchange-free algorithm for local improvement of the floorplan are also presented. Experimental results on the standard benchmarks MCNC and GSRC demonstrate that we obtain significant improvements on the best results in the literature. Overlap-free and deadspace-free floorplans are achieved in a fixed outline and floorplans with any specified percentage of whitespace can be produced. Most important, our method provides a greater improvement as the number of modules increases. A very important feature of our methodology is that not only do the dimensions of the floorplans in our experiments comply with the original ones provided in the GSRC benchmark, but also zero-deadspace floorplans can be obtained. Thus, our approach is able to guarantee complete area utilization in a fixed-outline situation. Our method is also applicable to area minimization in classical floorplanning.

The floorplanning problem aims to arrange a set of rectangular modules on a rectangular chip area so as to optimize an appropriate measure of performance. This problem is known to be NP-hard, and is particularly challenging if the chip dimensions are fixed. Fixed-outline floorplanning is becoming increasingly important as a tool to design flows in the hierarchical design of Application Specific Integrated Circuits and System-On-Chip. Therefore, it has recently received much attention. A two-stage convex optimization methodology is proposed to solve the fixed-outline floorplanning problem. It is a global optimization problem for wirelength minimization. In the first stage, an attractor-repeller convex optimization model provides the relative positions of the modules on the floorplan. The second stage places and sizes the modules using convex optimization. Given the relative positions of the modules from the first stage, a Voronoi diagram and Delaunay triangulation method is used to obtain a planar graph and hence a relative position matrix connecting the two stages. An efficient method for generating sparse relative position matrices and an interchange-free algorithm for local improvement of the floorplan are also presented. Experimental results on the standard benchmarks MCNC and GSRC demonstrate that we obtain significant improvements on the best results in the literature. Overlap-free and deadspace-free floorplans are achieved in a fixed outline and floorplans with any specified percentage of whitespace can be produced. Most important, our method provides a greater improvement as the number of modules increases. A very important feature of our methodology is that not only do the dimensions of the floorplans in our experiments comply with the original ones provided in the GSRC benchmark, but also zero-deadspace floorplans can be obtained. Thus, our approach is able to guarantee complete area utilization in a fixed-outline situation. Our method is also applicable to area minimization in classical floorplanning.

The main objective of this thesis is to develop a physical design tool that is capable of being used by microarchitects to evaluate the impact of their design decisions on the physical design aspects of future microprocessor development. For deep submicron technology wire delay will scale increasingly badly compared to gate delay and so will become a major bottleneck to performance improvement. Three dimensional integrated circuits (3D ICs) offer a new method of dealing with non-linear wire latency by allowing shorter interconnects that act within their linear region. Thermal considerations in 3D ICs will be more important than traditional designs however, so this problem must also be addressed. This thesis presents a microarchitectural floorplanning tool that will help computer architects to attack the wire delay problem early in the design stages of higher performance microprocessors by including consideration of design for 3D ICs. Consideration of the new problems that occur due to the move to 3D and inherent difficulties with deep submicron design is included. Experiments demonstrate that this tool can generate microprocessor floorplans that include many objectives and continue to enhance performance into the next generation of high performance design.

The main objective of this research is to examine the performance, power noise, and thermal trade-offs in modern traditional (2D) and three-dimensionally-integrated (3D) architectures and to present design automation tools and physical design methodologies that enable higher reliability while maintaining microarchitectural performance for these systems. Five main research topics that support this goal are included. The first topic focuses on thermal reliability. The second, third, and fourth, topics examine power-supply noise. The final topic presents a set of physical design and analysis methodologies used to produce a 3D design that was sent for fabrication in March of 2010. The first section of this dissertation details a microarchitectural floorplanning algorithm that enables the user to choose and adjust the trade-off between microarchitectural performance and general operating temperature in both 2D and 3D systems, which is a major determinant of overall reliability and chip lifetime. Simulation results demonstrate that the algorithm performs as expected and successfully provides the user with the desired trade-off. The first section also presents a thermal-aware microarchitectural floorplanning algorithm designed to help reduce the operating temperature of the cores in the unique environment present within multi-core processors. Heat-coupling between neighboring cores is considered during the optimization process to provide floorplans that result in lower maximum temperature. The second section explores power-supply noise in processors caused by fine-grained clock-gating and describes a floorplanning algorithm created to work with an active noise-canceling clock-gating controller. Simulation results show that combining these two techniques results in lower power-supply noise with minimal processor performance impact. The third section turns to future 3D systems with a large number of stacked active layers (many-tier systems) and examines power-supply delivery challenges in these systems. Parasitic resistance, capacitance, and inductance are calculated for the 3D vias, and the results of scaling various parameters in the power-supply-network design are presented. Several techniques for reducing power-supply-network noise in these many-tier systems are explored. The fourth section describes a layout-level analysis of a novel power distribution through-silicon-via topology and it's effect on IR-drop and dynamic noise. Simulations show that both types of power-supply noise can be reduced by more than 20\% in systems with non-uniform per-tier power dissipation when using the proposed topology. The final section explains the physical design and analysis techniques used to produce the layouts for 3D-MAPS, a 64-core 3D-stacked memory-on-processor system targeted at demonstration of large memory bandwidth using 3D connections. The 3D-aware physical design flow utilizing non-3D-aware commercial tools is detailed, along with the techniques and add-ons that were developed to enable this process.

For the microprocessor technology of today and the foreseeable future, multi-core is a key engine that drives performance growth under very tight power dissipation constraints. While previous research has been mostly focused on individual processor cores, there is a compelling need for studying how to efficiently manage shared resources among cores, including physical space, on-chip communication and on-chip storage. In managing physical space, floorplanning is the first and most critical step that largely affects communication efficiency and cost-effectiveness of chip designs. We consider floorplanning with regularity constraints that requires identical processing/memory cores to form an array. Such regularity can greatly facilitate design modularity and therefore shorten design turn-around time. Very little attention has been paid to automatic floorplanning considering regularity constraints because manual floorplanning has difficulty handling the complexity as chip core count increases. In this dissertation work, we investigate the regularity constraints in a simulated-annealing based floorplanner for multi/many core processor designs. A simple and effective technique is proposed to encode the regularity constraints in sequence-pair, which is a classic format of data representation in automatic floorplanning. To the best of our knowledge, this is the first work on regularity-constrained floorplanning in the context of multi/many core processor designs. On-chip communication and shared last level cache (LLC) play a role that is at least as equally important as processor cores in terms of chip performance and power. This dissertation research studies dynamic voltage and frequency scaling for on-chip network and LLC, which forms a single uncore domain of voltage and frequency. This is in contrast to most previous works where the network and LLC are partitioned and associated with processor cores based on physical proximity. The single shared domain can largely avoid the interfacing overhead across domain boundaries and is practical and very useful for industrial products. Our goal is to minimize uncore energy dissipation with little, e.g., 5% or less, performance degradation. The first part of this study is to identify a metric that can reflect the chip performance determined by uncore voltage/frequency. The second part is about how to monitor this metric with low overhead and high fidelity. The last part is the control policy that decides uncore voltage/frequency based on monitoring results. Our approach is validated through full system simulations on public architecture benchmarks.

Genetic Algorithms (GAs) are search algorithms inspired by genetics and natural selection, and have been used to solve difficult problems in many disciplines, including modelling, control systems and automation. GAs are generally able to find good solutions in reasonable time, however as they are applied to larger and harder problems they are very demanding in terms of computation time and memory. The Internet is the most powerful parallel and distributed computation environment in the world, and the idle cycles and memories of computers on the Internet have been increasingly recognized as a huge untapped source of computation power. By combining Internet computing and GAs, this dissertation provides a framework for Internet-based parallel and distributed GAs that gives scientists and engineers an easy and affordable way to solve hard real world problems. Developing parallel computation applications on the Internet is quite unlike developing applications in traditional parallel computation environments, such as multiprocessor systems and clusters. This is because the Internet is different in many respects, such as communication overhead, heterogeneity and volatility. To develop an Internet-based GA, we need to understand the implication of these differences. For this purpose, a convergence model for heterogenous and volatile networks is presented and used in experiments that study GA performance and robustness in Internet-like scenarios. The main outcome of this research is an Internet-based distributed GA framework called G2DGA. G2DGA is an island model distributed GA, which can provide support for big populations needed to solve many real world problems. G2DGA uses a novel hybrid peer-to-peer (P2P) design with island node activity coordinated by supervisor nodes that offer a global overview of the GA search state. Compared to client/server approaches, the P2P architecture improves scalability and fault tolerance by allowing direct communication between the islands and avoiding single-point-of-failure situations. One of the defining characteristics of Internet computing is the dynamics and volatility of the environment, and a parallel and distributed GA that does not adapt to its environment cannot use the available resources efficiently. Two novel adaptive methods are investigated. The first method is migration topology adaptation, which uses clustering on elite individuals from each island to rebuild the migration topology. Experiments with the migration topology adapter show that it gives G2DGA better performance than a GA with static migration topology of a similar or larger connectivity level. The second method is population size adaptation, which automatically finds the number of islands and island population sizes needed to solve a given problem efficiently. Experiments on the population size adapter show that it is robust, and compares favourably with the traditional trial-and-error approach in terms of computational effort and solution quality. The scalability and robustness of G2DGA has been extensively tested in network scenarios of varying volatility and heterogeneity. Experiments with up to 60 computers were conducted in computer laboratories, while more complex network scenarios have been studied in an Internet simulator. In the experiments, G2DGA consistently performs as well as, and usually significantly better than, static distributed GAs and the difference grows larger with increased network instability. The results show that G2DGA, by continuously adjusting the migration policy and the population size, can detect and make efficient use of idle cycles donated over volatile Internet connections. To demonstrate that G2DGA can be used to implement and solve real world problems, a challenging application in VLSI design was developed and used in the testing of the framework. The application is a multi-layer floorplanner, which uses a novel GA representation and operators based on a slicing structure approach. Its packing quality compares favourably with other multi-layer floorplanners found in the literature. Internet-based distributed GA research is exciting and important since it enables GAs to be applied to problem areas where resource limitations make traditional approaches unworkable. G2DGA provides a scalable and robust Internet-based distributed GA framework that can serve as a foundation for future work in the field.

No description available.

Made available in DSpace on 2015-05-14T12:36:50Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1579166 bytes, checksum: d3ba80babda5e722f7dbc5aaf9f3a941 (MD5) Previous issue date: 2013-08-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / EDA Tools (Electronic Design Automation) are used to facilitate the project and layout of Integrated Circuits (IC). Floorplanning is an important step in the layout design phase of the development of an IC. In this step the macroblocks are positioned on the chip, and the following properties are determined: the location of input and output pads, the location of the power pads and the strategies of distribution of the power and clock signal by the core. Commonly a wrapper in HDL that maps the input and output ports of the project in instances of pads is done, with the different types, defined by the developer and a file that indicates the position of each pad on the circuit. Thus, both the mapping and positioning are usually manually done through scripts, generating a great difficulty for developers, because an IC with a reasonable amount of inputs and outputs becomes extremely susceptible to human failure. These files are generally used by all EDA tools as well as by the Design kits suppliers, moreover, the tools have different syntaxes for the files. This work shows a tool with a GUI (Graphical User Interface) able to provide to the developers an easy and intuitive way to manage both the mapping and positioning of the pads, making the process faster and less susceptive to human failure. To validate the work, the tool is tested on some IC projects / As ferramentas EDA (Electronic Design Automation) são utilizadas para facilitar o projeto e desenho de circuitos integrados (CI). O Floorplaning é uma importante etapa na fase de design do layout no desenvolvimento de um CI. Nesta etapa, os macroblocos são posicionados no chip, além de serem decididas: a localização dos pads de entrada e saída, a localização dos pads de alimentação e as estratégias de distribuição da alimentação e do sinal de clock pelo núcleo. Comumente, é feito um wrapper em HDL que mapeia as portas de entrada e saída do projeto em instâncias de Pads, com seus diferentes tipos, definidos pelo desenvolvedor e um arquivo que indica a posição de cada Pad no circuito. Dessa maneira, tanto esse mapeamento quanto tal posicionamento, em geral, são feitos manualmente por meio de scripts, gerando uma dificuldade para os desenvolvedores, pois para um CI com uma quantidade razoável de entradas e saídas esses procedimentos são susceptíveis a falhas. Esses arquivos, em geral, são utilizados em todas as ferramentas EDA e também pelos fornecedores de Design Kits, além disso, as ferramentas possuem sintaxes diferentes para os arquivos. Este trabalho propõe a construção de uma ferramenta com interface gráfica capaz de fornecer aos desenvolvedores uma maneira mais fácil e intuitiva de gerenciar tanto o mapeamento quanto o posicionamento dos pads, tornando o processo mais rápido e menos susceptível a falhas humanas. Para validar o trabalho, a ferramenta é testada em projetos de CI s.