The analog placement algorithm Plantage, presented in this paper, generates placements for analog circuits with comprehensive placement constraints. Plantage is based on a hierarchically bounded enumeration of basic building blocks, using B*-trees. The practically relevant solution space is thereby enumerated quasi-complete. The sets of possible placements of the basic building blocks are represented and combined in a new efficient way, using enhanced shape functions. The result of Plantage is the Pareto front of placements with respect to different aspect ratios. The whole approach is deterministic, in contrast to existing analog placement algorithms.

Standard cell circuits consist of millions of standard cells, which have to be aligned overlap-free to the rows of the chip. Placement of these circuits is done in consecutive steps. First, a global placement is obtained by roughly spreading the cells on the chip, while considering all relevant objectives like wirelength, and routability. After that, the global placement is legalized, i.e., the cell overlap is removed, and the cells are aligned to the rows. To preserve the result of global placement, cells should be moved as little as possible during legalization

The force-directed quadratic placer ldquoKraftwerk2,rdquo as described in this paper, is based on two main concepts. First, the force that is necessary to distribute the modules on the chip is separated into the following two components: a hold force and a move force. Both components are implemented in a systematic manner. Consequently, Kraftwerk2 converges such that the module overlap is reduced in each placement iteration. The second concept of Kraftwerk2 is to use the ldquoBound2Boundrdquo net model, which accurately represents the half-perimeter wirelength (HPWL) in the quadratic cost function. Aside from these features, this paper presents additional details about Kraftwerk2. An approach to remove halos (free space) around large modules is described, and a method to control the module density is presented. In order to choose the important tradeoff between runtime and quality, a systematic quality control is shown. Furthermore, plots demonstrating the convergence of Kraftwerk2 are presented. Results using various benchmark suites demonstrate that Kraftwerk2 offers both high quality and excellent computational efficiency.

This paper presents a robust quadratic placement approach, which offers both high-quality placements and excellent computational efficiency. The additional force which distributes the modules on the chip in force-directed quadratic placement is separated into two forces: hold force and move force. Both of these forces are determined without any heuristics. Based on this novel systematic force implementation, we show that our iterative placement algorithm converges to an overlapfree placement. In addition, engineering change order (ECO) is efficiently supported by our placer. To handle the important trade-off between CPU time and placement quality, a deterministic quality control is presented.

During the ispd05 placement contest, we employed the force-directed approach Kraftwerk for global placement complemented by the network-flow based final placer DOMINO. These powerful and exible tools for standard cell placement can cope with various placement objectives and design conditions.

The performance of timing-driven placement methods depends strongly on the choice of the net model. In this paper a more precise net model is presented that does not increase numerical complexity. We introduce a method that replaces the clique model of a net by a tree model in the quadratic placement formulation. This improvement enables us to control the length of every tree segment separately. Furthermore, we present an analysis of the effects of every tree segment to the net delay.The result is in turn used to control the placement engine.Our presented results are based on legal placements. They show significant improvements over state-of-the art methods.

Performance optimization has become one of the most important problems at all design stages of today's highly integrated circuits. During logic synthesis performance optimization is guided by only rough net delay models. Therefore, net delays cannot be optimized effectively during logic synthesis. As device dimensions are shrinking in deep submicron designs, net delays tend to dominate performance. Consequently, the netlist generated during logic synthesis is suboptimal as only rough approximations for the most dominant part of the path delays are available. In this paper, we present a placement approach that exploits the optimization potential of netlist transformations during placement. As netlist transformations are integrated into the placement process, they can be guided by more accurate net delay models. In contrast to previous approaches that apply netlist transformations during placement, our approach is not restricted to local transformations like buffer insertion and gate resizing, but exploits global dependencies between the signals in a circuit. On the average, the maximum path delay is reduced by 11% compared to the initial performance-driven placement of the original netlist. Furthermore, the experiments show that applying the same netlist transformation procedure before placement yields no improvement as net delays cannot be considered due to missing layout information.

We present a new force directed method for global placement. Besides the well-known wire length dependent forces we use additional forces to reduce cell overlaps and to consider the placement area. Compared to existing approaches, the main advantage is that the algorithm provides increased flexibility and enables a variety of demanding applications. Our algorithm is capable of addressing the problems of global placement, floorplanning, timing minimization and interaction to logic synthesis. Among the considered objective functions are area, timing, congestion and heat distribution. The iterative nature of the algorithm assures that timing requirements are precisely met. While showing similar CPU time requirements it outperforms Gordian by an average of 6 percent and TimberWolf by an average of 8 percent in wire length and yields significantly better timing results.

This paper presents a technology mapping approach for the standard cell technology, which takes into account both gate area and routing area so as to minimize the total chip area after layout. The routing area is estimated using two parameters available at the mapping stage; one is the fanout count of a gate, and the other is the "overlap of fanin level intervals". To estimate the routing area in terms of accurate fanout counts, an algorithm is proposed which solves the problem of dynamic fanout changes in the mapping process. This also enables us to calculate the gate area more accurately. Experimental results show that this approach provides an average reduction of 15% in the final chip area after placement and routing.

This paper presents an innovative two-phase approach which combines technology mapping with logic resynthesis for minimizing the post-placement delays. The main idea is to alleviate the effect of inaccurate delay models in the mapping phase and to use a more accurate post-placement delay model in the logic resynthesis phase. To achieve this, our mapping phase disables the operations which may provide unpredictable effects on the circuit performance and leave them to be solved in the resynthesis phase. In the resynthesis phase, a post-placement delay model is extracted from the placement of the circuits. The techniques developed in our resynthesis algorithm are remapping, signal substitution, and gate duplication. Based on a wide range of benchmark examples, experimental results show that our approach provides 17% reduction in terms of post-placement delays when compared with SIS-1.2.

In this paper, we present a new approach that performs timing driven placement for standard cell circuits in interaction with netlist transformations.As netlist transformations are integrated into the placement process, an accurate net delay model is available.This model provides the basis for effective netlist transformations.In contrast to previous approaches that apply netlist transformations during placement, we are not restricted to local transformations like fanout buffering or gate resizing.Instead, we exploit global dependencies between the signals in the circuit.Results for benchmark circuits show excellent placement quality.The maximum path delay is reduced up to 33 % compared to the initial timing driven placement of the original netlist and up to 18 % compared to the results obtained by consecutive optimization of the netlist and timing driven placement of the optimized netlist.This delay reduction is achieved with almost no increase in chip area. 1.

Partitioning plays an increasingly important role in the design process of VLSI circuits and systems.There are partitioning problems to be solved on all levels of abstraction.The rapidly increasing size of the designs will make good partitioning tools even more essential in the future.As an introduction to the other papers in this session, this tutorial presentation discusses the numerous facets of partitioning.

A new partitioning approach for very large circuits is described.W e demonstrate that applying a recently developed analytical placement algorithm, that pro ts from a linear objective function, signi cantly improves the partitioning quality compared to the well-known eigenvector approach, which minimi zes a quadratic objective function.For the rst time, results of benchmark circuits with up to 100,000 cells are presented.The cutsize and the minim um ratio cut is impro ved up to 90%.The average improvement is about 50%.

The routing of modern sea-of-gates circuits is a very hard to solve combinatorial problem. The use of three or more layers of metal allows for channelless designs, where area routers are used to connect the pins of a net. In this paper, we present a new router that aims at combining the good quality of the traditional global/final routing approach with the high efficiency of strictly hierarchical routers. This is achieved by reducing the routing problem until its complexity is manageable. The reduced problem is then solved hierarchically by well-known maze-running algorithms using the divide-and-conquer paradigm. In addition to the ability to handle big circuits efficiently, this approach allows the parallel solution of subproblems, yielding significant speedups even when using workstation networks.>

We describe an efficient iterative improvement procedure for row-based cell placement with special emphasis on the objective function used to model net lengths. Two new net models are introduced and we prove theoretically that the net models are accurate approximations of the widely used half perimeter of a rectangle enclosing all pins of a net. In addition, unlike the half perimeter model, our net models allow us to compute costs for assigning cells to locations independently for all cells to be placed simultaneously. This offers our algorithm an important advantage compared to other iterative improvement techniques: many cells can be placed simultaneously by formulating placement as a network flow problem. This makes our algorithm more independent from a processing sequence than standard iterative improvement techniques. Finally, we compare our method to some existing algorithms including TimberWolfSC 5.4. We ran all of the algorithms on the SIGDA Benchmark Suite. We found that our method produced solutions with up to 23% less layout area while using an order of magnitude less running time compared to TimberWolfSC 5.4.>

An efficient iterative improvement procedure for row based cell placement is described. Special emphasis is placed on the objective function used to model net lengths. It is shown that minimizing the net length estimated with the net model also minimizes the half perimeter of a rectangle enclosing all pins of a net. Contrary to the half perimeter the new objective function permits computation of costs for assigning cells to locations independently for all cells to be placed simultaneously. This provides the algorithm an important advantage compared to other iterative improvement techniques: many cells can be placed simultaneously by formulating placement as a network flow problem. The algorithm is superior to Timber-WolfSC 5.4, which minimizes the half perimeter.>

Article Analytical placement: A linear or a quadratic objective function? Share on Authors: Georg Sigl Institute of Electronic Design Automation, Department of Electrical Engineering, Technical University of Munich, D-8000 Munich 2, Germany Institute of Electronic Design Automation, Department of Electrical Engineering, Technical University of Munich, D-8000 Munich 2, GermanyView Profile , Konrad Doll Institute of Electronic Design Automation, Department of Electrical Engineering, Technical University of Munich, D-8000 Munich 2, Germany Institute of Electronic Design Automation, Department of Electrical Engineering, Technical University of Munich, D-8000 Munich 2, GermanyView Profile , Frank M. Johannes Institute of Electronic Design Automation, Department of Electrical Engineering, Technical University of Munich, D-8000 Munich 2, Germany Institute of Electronic Design Automation, Department of Electrical Engineering, Technical University of Munich, D-8000 Munich 2, GermanyView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 427–432https://doi.org/10.1145/127601.127707Online:01 June 1991Publication History 167citation908DownloadsMetricsTotal Citations167Total Downloads908Last 12 Months36Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors present a placement method for cell-based layout styles. It is composed of alternating and interacting global optimization and partitioning steps that are followed by an optimization of the area utilization. Methods using the divide-and-conquer paradigm usually lose the global view by generating smaller and smaller subproblems. In contrast, GORDIAN maintains the simultaneous treatment of all cells over all global optimization steps, thereby considering constraints that reflect the current dissection of the circuit. The global optimizations are performed by solving quadratic programming problems that possess unique global minima. Improved partitioning schemes for the stepwise refinement of the placement are introduced. The area utilization is optimized by an exhaustive slicing procedure. The placement method is applied to real-world problems, and excellent results in terms of placement quality and computation time are obtained.>

A placement method for cell-based layout styles composed of alternating and interacting global optimization and partitioning phases is presented. In contrast to other methods using the divide-and-conquer paradigm, it maintains the simultaneous treatment of all cells during optimization over all levels of partitioning. In the global optimization phases, constrained quadratic optimization problems with unique global minima are solved. Their solutions induce the assignment of cells to regions during the partitioning phases. For general-cell circuits, a highly efficient exhaustive slicing procedure is applied to small subsets of cells. The designer may choose a configuration from a menu to meet his requirements on chip area, chip aspect ratio and wire length. Placements with high area utilization are obtained within short computation times. The method has been applied to general-cell and standard-cell circuits with up to 3000 cells and nets.>