SimPL: an algorithm for placing VLSI circuits

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.
3. Chan, T.F., et al. mPL6: Enhanced multilevel mixed-size placement. ISPD (2006), 212--214.
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.
5. Dagum, L., Menon, R. OpenMP: An industry standard API for shared-memory programming. IEEE Comput. Sci. Eng. (1998), 46--55.
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.
7. Hu, B., Marek-Sadowska, M. FA R: Fixed-points addition & relaxation based placement. ISPD (2005), 161--166.
8. Kahng, A.B., Wang, Q. A faster implementation of APlace. ISPD (2006), 218--220.
9. Kim, M.C., Markov, I.L. ComPLx: A competitive primal-dual Lagrange optimization for global placement. DAC (2012), 747--752.
10. Kim, M.C., et al. MAPLE: Multilevel adaptive PLacEment for mixed-size designs. Proc. ISPD (2012).
11. Kim, M.C., Hu, J., Lee, D., Markov, I.L. A SimPLR method for routability-driven placement. ICCAD (2011), 67--73.
12. Kahng, A.B., Lienig, J., Markov, I.L., Hu, J. VLSI Physical Design: From Graph Partitioning to Timing Closure, Springer, 2011, 312.
13. Kennings, A.A., Vorwerk, K. Force-directed methods for generic placement. IEEE TCAD 25, 10 (2006), 2076--2087.
14. Kleinhans, J.J., et al. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE TCAD 10, 3 (1991), 356--365.
15. Nam, G.J., Cong, J. Modern Circuit Placement: Best Practices and Results, Springer, 2007.
16. Pan, M., Viswanathan, N., Chu, C. An efficient & effective detailed placement algorithm. ICCAD (2005), 48--55.
17. Raman, S.K., Pentkovski, V., Keshava, J. Implementing streaming SIMD extensions on the Pentium III processor. IEEE Micro 20, 4 (2000), 47--57.
18. Roy, J.A., et al. Capo: Robust and scalable open-source min-cut floorplacer. ISPD (2005), 224--226.
19. Saad, Y. Iterative methods for sparse linear systems. SIAM (2003).
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.
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.
23. Viswanathan, N., et al. RQL: Global placement via relaxed quadratic spreading and linearization. DAC (2007), 453--458.

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Mathematics and statistics

• Computing methodologies

  • Modeling and simulation

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis