Gravity: Fast placement for 3-D VLSI

ABSTRACT

Three dimensional integration is an increasingly feasible method of implementing complex circuitry. For large circuits, which most benefit from 3-D designs, efficient placement algorithms with low time complexity are required.We present an iterative 3-D placement algorithm that places circuit elements in three dimensions in linear time. Using an order of magnitude less time, our proposed algorithm produces placements with better than 11% less wire lengths than partitioning placement using the best and fastest partitioner. Due to the algorithms iterative nature, wire-length results can be further improved by increasing the number of iterations.Further, we provide empirical evidence that large circuits benefit most from 3-D technology and that even a small number of layers can provide significant wire-length improvements.

REFERENCES

• 1: Alexander, M. J., Cohoon, J. P., Colflesh, J. L., Karro, J., Peters, E. L., and Robins, G. 1996. Placement and routing for three-dimensional FPGAS. In Proceedings of the 4th Canadian Workshop on Field-Programmable Devices. 11--18.
• 2: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 3: Antreich, K. J., Johannes, F. M., and Kirsch, F. H. 1982. A new approach for solving the placement problem using force models. In 1982 IEEE International Symposium on Circuits and Systems. 481--486.
• 4: Franc Brglez, A D&T Special Report on ACM/SIGDA Design Automation Benchmarks: Catalyst or Anathema?, IEEE Design & Test, v.10 n.3, p.87-91, July 1993
• 5: Chang, R.-I. and Hsiao, P.-Y. 1993. Force directed self-organizing map and its application to VLSI cell placement. In 1993 IEEE International Conference on Neural Networks. 103--109.
• 6: Chiricescu, S. M. S. A. and Vai, M. M. 1998. A three-dimensional FPGA with an integrated memory for in-application reconfiguration data. In 1998 IEEE International Symposium on Circuits and Systems. Vol. 2. 232--235.
• 7: Jo Depreitere , Henk Neefs , Herwig Van Marck , Jan Van Campenhout , Roel Baets , Bart Dhoedt , Hugo Thienpont , Irina Veretennicoff, An Optoelectronic 3-D Field Programmable Gate Array, Proceedings of the 4th International Workshop on Field-Programmable Logic and Applications: Field-Programmable Logic, Architectures, Synthesis and Applications, p.352-360, September 07-09, 1994
• 8: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: Goto, S. 1981. An efficient algorithm for the two-dimensional placement problem in electrical circuit layout. IEEE Trans. Circuits Syst. CAS-28, 1 (Jan.), 12--18.
• 11: Hanan, M. 1966. On Steiner's problem with rectilinear distance. SIAM J. Appl. Mathem. 14, 2 (Mar.), 255--265.
• 12: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 13: Kleinhans, J. M., Sigl, G., Johannes, F. M., and Antreich, K. J. 1991. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. Computer-Aided Des. 10, 3 (Mar.), 356--365.
• 14: Koford, J. S. 1998. Method and system for improving a placement of cells using energetic placement units alternating contraction and expansion operations. United States Patent 5754444.
• 15: Miriam Leeser , Waleed M. Meleis , Mankuan M. Vai , Silviu Chiricescu , Weidong Xu , Paul M. Zavracky, Rothko: A Three-Dimensional FPGA, IEEE Design & Test, v.15 n.1, p.16-23, January 1998 [doi>10.1109/54.655178]
• 16: Frank Thomson Leighton , Arnold L Rosenberg, Three dimensional circuit layouts, SIAM Journal on Computing, v.15 n.3, p.793-813, August 1986 [doi>10.1137/0215057]
• 17: Stefan Thomas Obenaus , Ted H. Szymanski, Placements Benchmarks for 3-D VLSI, Proceedings of the IFIP TC10/WG10.5 Tenth International Conference on Very Large Scale Integration: Systems on a Chip, p.447-455, December 01-04, 1999
• 18: Obenaus, S. T. H. 2000. Fast placement algorithms for grids in two and three dimensions. Ph.D. thesis, McGill University.
• 19: Ohmura, M. 1998. An initial placement algorithm for 3-D VLSI. In 1998 IEEE International Symposium on Circuits and Systems. Vol. 6. 195--198.
• 20: Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277121]
• 21: Reber, M. and Tielert, R. 1986. Benefits of vertically stacked integrated circuits for sequential logic. In 1996 IEEE International Symposium on Circuits and Systems. 121--124.
• 22: K. Shahookar , P. Mazumder, VLSI cell placement techniques, ACM Computing Surveys (CSUR), v.23 n.2, p.143-220, June 1991 [doi>10.1145/103724.103725]
• 23: Tanprasert, T. 2000. Analytical 3-D placement that reserves routing space. In 2000 IEEE International Symposium on Circuits and Systems. Vol. 3. 69--72.
• 24: Tia, T.-S. and Liu, C. 1993. A new performance driven macro-cell placement algorithm. In European Design Automation Conference. 66--71.
• 25: Chao Chi Tong , Chuan-lin Wu, Routing in a Three-Dimensional Chip, IEEE Transactions on Computers, v.44 n.1, p.106-117, January 1995 [doi>10.1109/12.368006]
• 26: Tsay, R.-S. and Kuh, E. 1991. A unified approach to partitioning and placement. IEEE Trans. Circuits Syst. 38, 5 (May), 521--533.
• 27: Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, Proud: a fast sea-of-gates placement algorithm, Proceedings of the 25th ACM/IEEE conference on Design automation, p.318-323, June 12-15, 1988, Atlantic City, New Jersey, United States
• 28: Ueda, K., Kitazawa, H., and Harada, I. 1985. CHAMP: Chip floor plan for hierachical VLSI layout design. IEEE Trans. Computer-Aided Design CAD-4, 1 (Jan.), 12--22.
• 29: Jens Vygen, Algorithms for large-scale flat placement, Proceedings of the 34th annual conference on Design automation, p.746-751, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266360]
• 30: G. J. Wipfler , M. Wiesel , D. A. Mlynski, A combined force and cut algorithm for hierarchical VLSI layout, Proceedings of the 19th conference on Design automation, p.671-677, January 1982

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance

Keywords:
3-D VLSI, 3-D integrated circuits, Placement