research-article

Free access

SimPL: an algorithm for placing VLSI circuits

Authors:

Myung-Chul Kim,

Igor L. MarkovAuthors Info & Claims

Communications of the ACM, Volume 56, Issue 6

Pages 105 - 113

https://doi.org/10.1145/2461256.2461279

Published: 01 June 2013 Publication History

All formats PDF

Abstract

VLSI placement optimizes locations of circuit components so as to reduce interconnect. Formulated in terms of (hyper) graphs, it is NP-hard, and yet must be solved for challenging million-node instances within several hours. We propose an algorithm for large-scale placement that outperforms prior art both in runtime and solution quality on standard benchmarks. The algorithm is more straightforward than existing placers and easier to integrate into timing-closure flows. Our C++ implementation is compact, self-contained and exploits instruction-level and thread-level parallelism. Due to its simplicity and superior performance, the algorithm has been adopted in the industry and was extended by several university groups to multi-objective optimization.

References

[1]

Alpert, C.J., et al. Techniques for fast physical synthesis. Proc. IEEE 95, 3 (2007), 573--599.

[2]

Brenner, U., Struzyna, M., Vygen, J. BonnPlace: Placement of leading-edge chips by advanced combinatorial algorithms. IEEE TCAD 27, 9 (2008), 1607--1620.

Digital Library

[3]

Chan, T.F., et al. mPL6: Enhanced multilevel mixed-size placement. ISPD (2006), 212--214.

Digital Library

[4]

Chen, T.C., et al. NTUPlace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints. IEEE TCAD 27, 7 (2008), 1228--1240.

Digital Library

[5]

Dagum, L., Menon, R. OpenMP: An industry standard API for shared-memory programming. IEEE Comput. Sci. Eng. (1998), 46--55.

Digital Library

[6]

He, X., Huang, T., Xiao, L., Tian, H., Cui, G., Young, E.F.Y. Ripple: An effective routability-driven placer by iterative cell movement. ICCAD (2011), 74--79.

Digital Library

[7]

Hu, B., Marek-Sadowska, M. FA R: Fixed-points addition & relaxation based placement. ISPD (2005), 161--166.

Digital Library

[8]

Kahng, A.B., Wang, Q. A faster implementation of APlace. ISPD (2006), 218--220.

Digital Library

[9]

Kim, M.C., Markov, I.L. ComPLx: A competitive primal-dual Lagrange optimization for global placement. DAC (2012), 747--752.

Digital Library

[10]

Kim, M.C., et al. MAPLE: Multilevel adaptive PLacEment for mixed-size designs. Proc. ISPD (2012).

Digital Library

[11]

Kim, M.C., Hu, J., Lee, D., Markov, I.L. A SimPLR method for routability-driven placement. ICCAD (2011), 67--73.

Digital Library

[12]

Kahng, A.B., Lienig, J., Markov, I.L., Hu, J. VLSI Physical Design: From Graph Partitioning to Timing Closure, Springer, 2011, 312.

Digital Library

[13]

Kennings, A.A., Vorwerk, K. Force-directed methods for generic placement. IEEE TCAD 25, 10 (2006), 2076--2087.

Digital Library

[14]

Kleinhans, J.J., et al. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE TCAD 10, 3 (1991), 356--365.

Digital Library

[15]

Nam, G.J., Cong, J. Modern Circuit Placement: Best Practices and Results, Springer, 2007.

Digital Library

[16]

Pan, M., Viswanathan, N., Chu, C. An efficient & effective detailed placement algorithm. ICCAD (2005), 48--55.

Digital Library

[17]

Raman, S.K., Pentkovski, V., Keshava, J. Implementing streaming SIMD extensions on the Pentium III processor. IEEE Micro 20, 4 (2000), 47--57.

Digital Library

[18]

Roy, J.A., et al. Capo: Robust and scalable open-source min-cut floorplacer. ISPD (2005), 224--226.

Digital Library

[19]

Saad, Y. Iterative methods for sparse linear systems. SIAM (2003).

Digital Library

[20]

Spindler, P., Schlichtmann, U., Johannes, F.M. Kraftwerk2 -- A fast force-directed quadratic placement approach using an accurate net model. IEEE TCAD 27, 8 (2008), 1398--1411.

Digital Library

[21]

Trefethen, L.N., Bau, D. Numerical linear algebra. SIAM (1997), 296--298.

[22]

Viswanathan, N., Pan, M., Chu, C. FastPlace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control. ASPDAC (2007), 135--140.

Digital Library

[23]

Viswanathan, N., et al. RQL: Global placement via relaxed quadratic spreading and linearization. DAC (2007), 453--458.

Digital Library

Cited By

Hou YYe HZhang YXu SSong GBaeza-Yates RBonchi F(2024)RoutePlacer: An End-to-End Routability-Aware Placer with Graph Neural NetworkProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671895(1085-1095)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671895
Martin TBarnes CGrewal GAreibi S(2023)FPGA Placement: Dynamic Decision Making Via Machine Learning2023 36th SBC/SBMicro/IEEE/ACM Symposium on Integrated Circuits and Systems Design (SBCCI)10.1109/SBCCI60457.2023.10261650(1-6)Online publication date: 28-Aug-2023
https://doi.org/10.1109/SBCCI60457.2023.10261650
Barn CVermeulen SAreibi SGrewal G(2023)An Adaptive Analytical FPGA Placement flow based on Reinforcement Learning2023 International Conference on Microelectronics (ICM)10.1109/ICM60448.2023.10378891(178-183)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICM60448.2023.10378891
Show More Cited By

Index Terms

SimPL: an algorithm for placing VLSI circuits

Recommendations

SimPL: An Effective Placement Algorithm

We propose a self-contained, flat, quadratic global placer that is simpler than existing placers and easier to integrate into timing-closure flows. It maintains lower-bound and upper-bound placements that converge to a final solution. The upper-bound ...
SimPL: an effective placement algorithm
ICCAD '10: Proceedings of the International Conference on Computer-Aided Design

We propose a self-contained, flat, force-directed algorithm for global placement that is simpler than existing placers and easier to integrate into timing-closure flows. It maintains lower-bound and upper-bound placements that converge to a final ...
MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 56, Issue 6

June 2013

104 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/2461256

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2013

Published in CACM Volume 56, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Popular
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
6,025
Total Downloads

Downloads (Last 12 months)479
Downloads (Last 6 weeks)59

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hou YYe HZhang YXu SSong GBaeza-Yates RBonchi F(2024)RoutePlacer: An End-to-End Routability-Aware Placer with Graph Neural NetworkProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671895(1085-1095)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671895
Martin TBarnes CGrewal GAreibi S(2023)FPGA Placement: Dynamic Decision Making Via Machine Learning2023 36th SBC/SBMicro/IEEE/ACM Symposium on Integrated Circuits and Systems Design (SBCCI)10.1109/SBCCI60457.2023.10261650(1-6)Online publication date: 28-Aug-2023
https://doi.org/10.1109/SBCCI60457.2023.10261650
Barn CVermeulen SAreibi SGrewal G(2023)An Adaptive Analytical FPGA Placement flow based on Reinforcement Learning2023 International Conference on Microelectronics (ICM)10.1109/ICM60448.2023.10378891(178-183)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICM60448.2023.10378891
Dadaliaris AKranas GOikonomou PFloros GDossis M(2022)Exploiting Net Connectivity in Legalization and Detailed Placement ScenariosInformation10.3390/info1305021213:5(212)Online publication date: 20-Apr-2022
https://doi.org/10.3390/info13050212
Martin TBarnes CAreibi SGrewal G(2022)An Adaptive Sequential Decision Making Flow for FPGAs using Machine Learning2022 International Conference on Microelectronics (ICM)10.1109/ICM56065.2022.10005468(34-37)Online publication date: 4-Dec-2022
https://doi.org/10.1109/ICM56065.2022.10005468
Ray BSahoo SRay RMohanty SSethy D(2018)An Iterative Concave-Convex Wirelength Model for Analytical Placement2018 IEEE International Symposium on Smart Electronic Systems (iSES) (Formerly iNiS)10.1109/iSES.2018.00023(64-69)Online publication date: Dec-2018
https://doi.org/10.1109/iSES.2018.00023
Ray BMohanty SSethy DRay R(2017)HPWL Formulation for Analytical Placement Using Gaussian Error Function2017 International Conference on Information Technology (ICIT)10.1109/ICIT.2017.34(56-61)Online publication date: Dec-2017
https://doi.org/10.1109/ICIT.2017.34
Wang CHuang CLiu SChin CHu SWu WChen HDavoodi AYoung E(2015)Closing the Gap between Global and Detailed PlacementProceedings of the 2015 Symposium on International Symposium on Physical Design10.1145/2717764.2717776(149-156)Online publication date: 29-Mar-2015
https://dl.acm.org/doi/10.1145/2717764.2717776
Kim MHu JViswanathan NChang Y(2014)ICCAD-2014 CAD contest in incremental timing-driven placement and benchmark suiteProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691438(361-366)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691438
Kim MHuj JViswanathan N(2014)ICCAD-2014 CAD contest in incremental timing-driven placement and benchmark suite: Special session paper: CAD contest2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2014.7001376(361-366)Online publication date: Nov-2014
https://doi.org/10.1109/ICCAD.2014.7001376
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents