Placement (electronic design automation)

Placement is an essential step in electronic design automation — the portion of the physical design flow that assigns exact locations for various circuit components within the chip's core area. An inferior placement assignment will not only affect the chip's performance but might also make it non-manufacturable by producing excessive wire-length, which is beyond available routing resources. Consequently, a placer must perform the assignment while optimizing a number of objectives to ensure that a circuit meets its performance demands. Together, the placement and routing steps of IC design are known as place and route.

A placer takes a given synthesized circuit netlist together with a technology library and produces a valid placement layout. The layout is optimized according to the aforementioned objectives and ready for cell resizing and buffering — a step essential for timing and signal integrity satisfaction. Clock-tree synthesis and Routing follow, completing the physical design process. In many cases, parts of, or the entire, physical design flow are iterated a number of times until design closure is achieved.

In the case of application-specific integrated circuits, or ASICs, the chip's core layout area comprises a number of fixed height rows, with either some or no space between them. Each row consists of a number of sites which can be occupied by the circuit components. A free site is a site that is not occupied by any component. Circuit components are either standard cells, macro blocks, or I/O pads. Standard cells have a fixed height equal to a row's height, but have variable widths. The width of a cell is an integral number of sites. On the other hand, blocks are typically larger than cells and have variable heights that can stretch a multiple number of rows. Some blocks can have preassigned locations — say from a previous floorplanning process — which limit the placer's task to assigning locations for just the cells. In this case, the blocks are typically referred to by fixed blocks. Alternatively, some or all of the blocks may not have preassigned locations. In this case, they have to be placed with the cells in what is commonly referred to as mixed-mode placement.

In addition to ASICs, placement retains its prime importance in gate array structures such as field-programmable gate arrays (FPGAs). In FPGAs, placement maps the circuit's subcircuits into programmable FPGA logic blocks in a manner that guarantees the completion of the subsequent stage of routing.

Objectives and constraints

Placement is usually formulated as a problem of constrained optimization. The constraint is to remove overlaps between all the instances in the netlist. The optimization objective can be of multiple, which typically include:

  • Total wirelength: Minimizing the total wirelength, or the sum of the length of all the wires in the design, is the primary objective of most existing placers. This not only helps minimize chip size, and hence cost, but also minimizes power and delay, which are proportional to the wirelength (This assumes long wires have additional buffering inserted; all modern design flows do this.)
  • Timing: The clock cycle of a chip is determined by the delay of its longest path, usually referred to as the critical path. Given a performance specification, a placer must ensure that no path exists with delay exceeding the maximum specified delay.
  • Congestion: While it is necessary to minimize the total wirelength to meet the total routing resources, it is also necessary to meet the routing resources within various local regions of the chip’s core area. A congested region might lead to excessive routing detours, or make it impossible to complete all routes.
  • Power: Power minimization typically involves distributing the locations of cell components so as to reduce the overall power consumption, alleviate hot spots, and smooth temperature gradients.
  • A secondary objective is placement runtime minimization.

Basic techniques

Placement is divided into global placement and detailed placement. Global placement introduces dramatic changes by distributing all the instances to appropriate locations in the global scale with minor overlaps allowed. Detailed placement shifts each instance to nearby legal location with very moderate layout change. Placement and overall design quality is most dependent on the global placement performance.

At early time, placement of integrated circuits is handled by combinatorial approaches. When IC design was of thousand-gate scale, simulated annealing[1] methodologies such as TimberWolf[2] exhibits the best performance. As IC design entered million-scale integration, placement was achieved by recursive hyper-graph partitioning[3] like Capo.[4]

Quadratic placement later outperformed combinatorial solutions in both quality and stability. GORDIAN[5] formulates the wirelength cost as a quadratic function while still spreading cells apart through recursive partitioning. The algorithm[6] models placement density as a linear term into the quadratic cost function and solves the placement problem by pure quadratic programming. The majority of modern quadratic placers (KraftWerk,[7] FastPlace,[8] SimPL[9]) follow this framework, each with different heuristics on how to determine the linear density force.

Nonlinear placement presents better performance over other categories of algorithms. The approach in[10] first models wirelength by exponential (nonlinear) functions and density by local piece-wise quadratic functions, in order to achieve better accuracy thus quality improvement. Follow-up academic works mainly include APlace[11] and NTUplace.[12]

ePlace[13] is the state of the art global placement algorithm. It spreads instances apart by simulating an electrostatic field, which introduces the minimum quality overhead thus achieves the best performance.

See also

References
  1. S. Kirkpatrick, C. D. G. Jr., and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671–680, 1983.
  2. C. Sechen and A. Sangiovanni-Vincentelli. TimberWolf3.2: A New Standard Cell Placement and Global Routing Package. In DAC, pages 432–439, 1986.
  3. George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel Hypergraph Partitioning: Applications in VLSI Domain. In DAC, pp. 526 - 529, 1997.
  4. Caldwell, A.E.; Kahng, A.B.; Markov, I.L. (June 2000). "Can recursive bisection alone produce routable placements? ". Proceedings of the 37th Design Automation Conference. pp. 477–482.
  5. Kleinhans, J.M.; Sigl, G.; Johannes, F.M.; Antreich, K.J. (March 1991). "GORDIAN: VLSI placement by quadratic programming and slicing optimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 10 (3): 356–365. doi:10.1109/43.67789. S2CID 15274014.
  6. H. Eisenmann and F. M. Johannes. Generic Global Placement and Floorplanning. In DAC, pages 269–274, 1998.
  7. P. Spindler, U. Schlichtmann, and F. M. Johannes. Kraftwerk2 - A Fast Force-Directed Quadratic Placement Approach Using an Accurate Net Model. IEEE TCAD, 27(8):1398–1411, 2008.
  8. N. Viswanathan, M. Pan, and C. Chu. FastPlace3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion Control. In ASPDAC, pages 135–140, 2007.
  9. Kim, M.-C.; Lee D.-J.; Markov I.L. (January 2011). "SimPL: An Effective Placement Algorithm". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 31 (1): 50–60. doi:10.1109/TCAD.2011.2170567. S2CID 47293399.
  10. W. C. Naylor, R. Donelly, and L. Sha. Non-Linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer. In US Patent 6301693, 2001.
  11. A. B. Kahng, S. Reda and Q. Wang, "Architecture and Details of a High Quality, Large-Scale Analytical Placer", In ICCAD 2005, pp. 891-898.
  12. T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang. NTUPlace3: An Analytical Placer for Large-Scale Mixed-Size Designs with Preplaced Blocks and Density Constraint. IEEE TCAD, 27(7):1228– 1240, 2008.
  13. J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-S. Huang, C.-C. Teng and C.-K. Cheng, "ePlace: Electrostatics Based Placement Using Nesterov's Method", DAC 2014, pp. 1-6.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.