← Back to results

p to content Main menu Main menu move to sidebar hide Navigation Main page Contents Current events Random article About Wikipedia Contact us Contribute Help Learn to edit Community portal Recent changes Upload file Special pages Search Search Appearance Donate Create account Log in Personal tools Donate Create account Log in Contents move to sidebar hide (Top) 1 Application specifics 2 Objectives and constraints 3 Basic techniques 4 See also 5 References 6 Further reading/External links Toggle the table of contents Placement (electronic design automation) 4 languages العربية Deutsch 吴语 中文 Edit links Article Talk English Read Edit View history Tools Tools move to sidebar hide Actions Read Edit View history General What links here Related changes Upload file Permanent link Page information Cite this page Get shortened URL Print/export Download as PDF Printable version In other projects Wikidata item Appearance move to sidebar hide From Wikipedia, the free encyclopedia Stage of electronic circuit design 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. Application specifics [ edit ] 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. [ 1 ] 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. [ 1 ] 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). Here, prefabricated transistors are typically arranged in rows (or “arrays”) that are separated by routing channels. [ 2 ] 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 [ edit ] Placement is formulated as constrained optimization . In particular, 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. Other key constraints include avoiding overlaps between circuit components (the instances in the netlist) placing circuit components into predetermined "sites" There are usually multiple optimization objectives, including: Total wire length : the sum of the lengths of all the wires in the design Routing congestion : local congestion is the difference between the lengths of wires in a region and the length of routing tracks available in that region; local values can be aggregated in several ways, such as adding up the top 10% greatest values. Power : dynamic switching power depends on wire lengths, which in turn depend on component locations. Additionally, it is desirable to finish the placement process quickly. Total wirelength is typically the primary objective of most existing placers and serves as a precursor to other optimizations because, e.g., power and delay tend to grow with wire length. Total wire length determines the routing demand and whether it can be satisfied by the routing supply defined by available routing tracks. However, making wires very short sometimes leads to local routing demand exceeding local routing supply. Such situations often require routing detours, which increase wire lengths and signal delays. Therefore, after preliminary optimization of total wirelength, it is also important to handle routing congestion. Power minimization typically notes wires with greater switching activity factors and assigns greater priority to making them shorter. When many "hot" components are placed nearby, a hot spot may arise and lead to harmful temperature gradients. In such cases, components can be spread out. Basic techniques [ edit ] Placement is divided into global placement and detailed placement. Global placement introduces dramatic changes by distributing all the instances to appropriate locations in a 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. Early techniques for placement of integrated circuits can be categorized as combinatorial optimization . For IC designs with thousands or tens of thousands of components, simulated annealing [ 3 ] methodologies such as TimberWolf [ 4 ] exhibits the best results. When IC designs grew to millions of components, placement leveraged hypergraph partitioning [ 5 ] using nested-partitioning frameworks such as Capo. [ 6 ] Combinatorial methods directly prevent component overlaps but struggle with interconnect optimization at large scale. They are typically stochastic and can produce very different results for the same input when launched multiple times. Analytical methods for global placement model interconnect length by a continuous function and minimize this function directly subject to component density constraints. These methods run faster and scale better than combinatorial methods, but do not prevent component overlaps and must be postprocessed by combinatorial methods for detailed placement. Quadratic placement is an early analytical method that models interconnect length by a quadratic function and uses high-performance quadratic optimization techniques. When it was developed, it demonstrated competitive quality of results and also stability, unlike combinatorial methods. GORDIAN [ 7 ] formulates the wirelength cost as a quadratic function while still spreading cells apart through recursive partitioning. The algorithm [ 8 ] models placement density as a linear term into the quadratic cost function and solves the placement problem by pure quadratic programming. A common enhancement is weighting each net by the inverse of its length on the previous iteration. Provided the process converges, this minimizes an objective linear in the wirelength. [ 9 ] The majority of modern quadratic placers (KraftWerk, [ 10 ] FastPlace, [ 11 ] SimPL [ 12 ] ) follow this framework, each with different heuristics on how to determine the linear density force. Nonlinear placement models wirelength by exponential (nonlinear) functions and density by local piece-wise quadratic functions, in order to achieve better accuracy thus quality improvement. [ 13 ] Follow-up academic work includes APlace [ 14 ] and NTUplace. [ 15 ] ePlace [ 16 ] is a state-of-the-art global placement algorithm. It spreads instances apart by simulating an electrostatic field, which minimizes quality overhead thus achieves good performance. In 2021, Google Brain reported good results from the use of AI techniques (in particular, reinforcement learning) for the placement problem. [ 17 ] However, this result is quite controversial, [ 18 ] [ 19 ] [ 20 ] as the paper does not contain head-to-head comparisons to existing placers, and is difficult to replicate due to proprietary content. At least one initially favorable commentary has been retracted upon further review. [ 21 ] See also [ edit ] Electronic design automation Design flow (EDA) Integrated circuit design Floorplan (microelectronics) Place and route References [ edit ] ^ a b A. Kahng, J. Lienig, I. Markov, J. Hu: "VLSI Physical Design: From Graph Partitioning to Timing Closure", Springer (2022), doi : 10.1007/978-90-481-9591-6 , ISBN   978-3-030-96414-6 , pp. 10-13. ^ A. Kahng, J. Lienig, I. Markov, J. Hu: "VLSI Physical Design: From Graph Partitioning to Timing Closure", Springer (2022), doi : 10.1007/978-90-481-9591-6 , ISBN   978-3-030-96414-6 , pp. 14-15. ^ S. Kirkpatrick, C. D. G. Jr., and M. P. Vecchi (1983). "Optimization by Simulated Annealing". Science . 220 (4598): 671– 680. Bibcode : 1983Sci...220..671K . doi : 10.1126/science.220.4598.671 . PMID   17813860 . {{ cite journal }} : CS1 maint: multiple names: authors list ( link ) ^ C. Sechen and A. Sangiovanni-Vincentelli (1986). "TimberWolf3.2: A New Standard Cell Placement and Global Routing Package.". Proceedings of the Design Automation Conference . ACM. pp.  432– 439. ^ George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar (1997). "Multilevel Hypergraph Partitioning: Applications in VLSI Domain". Proceedings of the Design Automation Conference . ACM. pp.  526– 529. {{ cite conference }} : CS1 maint: multiple names: authors list ( link ) ^ 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. doi : 10.1109/DAC.2000.855358 . ^ 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. Bibcode : 1991ITCAD..10..356K . doi : 10.1109/43.67789 . S2CID   15274014 . ^ H. Eisenmann and F. M. Johannes (1998). "Generic Global Placement and Floorplanning". Proceedings of the Design Automation Conference . ACM. pp.  269– 274. ^ Sigl, Georg, Konrad Doll, and Frank M. Johannes (1991). "Analytical placement: A linear or a quadratic objective function?". Proceedings of the 28th ACM/IEEE design automation conference . ACM. pp.  427– 432. {{ cite conference }} : CS1 maint: multiple names: authors list ( link ) ^ P. Spindler, U. Schlichtmann, and F. M. Johannes (2008). "Kraftwerk2 - A Fast Force-Directed Quadratic Placement Approach Using an Accurate Net Model". IEEE Transactions on Computer-Aided Design . 27 (8): 1398– 1411. Bibcode : 2008ITCAD..27.1398S . doi : 10.1109/TCAD.2008.925783 . S2CID   16054185 . {{ cite journal }} : CS1 maint: multiple names: authors list ( link ) ^ N. Viswanathan, M. Pan, and C. Chu (2007). "FastPlace3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion Control". Proceedings of the Asia-South Pacific Design Automation Conference . pp.  135– 140. {{ cite conference }} : CS1 maint: multiple names: authors list ( link ) ^ 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. CiteSeerX   10.1.1.187.1292 . doi : 10.1109/TCAD.2011.2170567 . S2CID   47293399 . ^ USA 6301693 , 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"   ^ A. B. Kahng, S. Reda and Q. Wang (2005). "Architecture and Details of a High Quality, Large-Scale Analytical Placer". Proceedings of the International Conference on Computer-Aided Design . pp.  891– 898. ^ T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang (2008). "NTUPlace3: An Analytical Placer for Large-Scale Mixed-Size Designs with Preplaced Blocks and Density Constraint" (PDF) . IEEE Transactions on Computer-Aided Design . 27 (7): 1228– 1240. Bibcode : 2008ITCAD..27.1228C . doi : 10.1109/TCAD.2008.923063 . S2CID   11912537 . {{ cite journal }} : CS1 maint: multiple names: authors list ( link ) ^ J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-S. Huang, C.-C. Teng and C.-K. Cheng (2014). "ePlace: Electrostatics Based Placement Using Nesterov's Method". Proceedings of the Design Automation Conference . ACM. pp.  1– 6. {{ cite conference }} : CS1 maint: multiple names: authors list ( link ) ^ Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan (2021). "A Graph Placement Methodology for Fast Chip Design". Nature . 594 (7862): 207– 212. arXiv : 2004.10746 . Bibcode : 2021Natur.594..207M . doi : 10.1038/s41586-021-03544-w . PMID   34108699 . S2CID   235395490 . {{ cite journal }} : CS1 maint: multiple names: authors list ( link ) ^ Cheng, Chung-Kuan, Andrew B. Kahng, Sayak Kundu, Yucheng Wang, and Zhiang Wang (Mar 2023). "Assessment of Reinforcement Learning for Macro Placement". Proceedings of the 2023 International Symposium on Physical Design . pp.  158– 166. arXiv : 2302.11014 . doi : 10.1145/3569052.3578926 . ISBN   978-1-4503-9978-4 . {{ cite book }} : CS1 maint: multiple names: authors list ( link ) ^ Igor L. Markov (2023). "The False Dawn: Reevaluating Google's Reinforcement Learning for Chip Macro Placement". arXiv : 2306.09633 [ cs.LG ]. ^ Agam Shah (October 3, 2023). "Google's Controversial AI Chip Paper Under Scrutiny Again" . ^ Kahng, Andrew B. (2021). "RETRACTED ARTICLE: AI system outperforms humans in designing floorplans for microchips". Nature . 594 (7862): 183– 185. Bibcode : 2021Natur.594..183K . doi : 10.1038/d41586-021-01515-9 . PMID   34108693 . S2CID   235394411 . Further reading/External links [ edit ] IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) ACM Transactions on Design Automation of Electronic Systems (TODAES) IEEE Transactions on Very Large Scale Integration Systems (TVLSI) v t e Digital electronics Components Transistor Resistor Inductor Capacitor Printed electronics Printed circuit board Electronic circuit Flip-flop Memory cell Combinational logic Sequential logic Logic gate Boolean circuit Integrated circuit (IC) Hybrid integrated circuit (HIC) Mixed-signal integrated circuit Three-dimensional integrated circuit (3D IC) Emitter-coupled logic (ECL) Erasable programmable logic device (EPLD) Macrocell array Programmable logic array (PLA) Programmable logic device (PLD) Programmable Array Logic (PAL) Generic Array Logic (GAL) Complex programmable logic device (CPLD) Field-programmable gate array (FPGA) Field-programmable object array (FPOA) Application-specific integrated circuit (ASIC) Tensor Processing Unit (TPU) Theory Digital signal Boolean algebra Logic synthesis Logic in computer science Computer architecture Digital signal Digital signal processing Circuit minimization Switching circuit theory Gate equivalent Design Logic synthesis Place and route Placement Routing Transaction-level modeling Register-transfer level Hardware description language High-level synthesis Formal equivalence checking Synchronous logic Asynchronous logic Finite-state machine Hierarchical state machine Applications Computer hardware Hardware acceleration Digital audio radio Digital photography Digital telephone Digital video cinematography television Electronic literature Design issues Metastability Runt pulse Retrieved from " https://en.wikipedia.org/w/index.php?title=Placement_(electronic_design_automation)&oldid=1318451403 " Categories : Integrated circuits Electronic design automation Electronics optimization Hidden categories: CS1 maint: multiple names: authors list Articles with short description Short description matches Wikidata Use American English from April 2019 All Wikipedia articles written in American English This page was last edited on 23 October 2025, at 23:08  (UTC) . Text is available under the Creative Commons Attribution-ShareAlike 4.0 License ; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy . Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. , a non-profit organization. Privacy policy About Wikipedia Disclaimers Contact Wikipedia Legal & safety contacts Code of Conduct Developers Statistics Cookie statement Mobile view Search Search Toggle the table of contents Placement (electronic design automation) 4 languages Add topic