More Web Proxy on the site http://driver.im/

article

Gravity: Fast placement for 3-D VLSI

Authors:

Stefan Thomas Obenaus,

Ted H. SzymanskiAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 8, Issue 3

Pages 298 - 315

https://doi.org/10.1145/785411.785413

Published: 01 July 2003 Publication History

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]

Alpert, C. J. 1998. The ISPD98 circuit benchmark suite. In Proceedings of the International Symposium on Physical Design. 85--90.

[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]

Brglez, F. 1993. ACM/SIGDA design automation benchmarks: Catalyst or anathema? IEEE Des. Test Comput. 10, 3 (Sept.), 87--91.

[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]

Depreitere, J., Neefs, H., Van Marck, H., Van Campenhout, J., Baets, R., Dhoedt, B., Thienpont, H., and Veretennicoff, I. 1994. An optoelectronic 3-D field programmable gate array. In Field-programmable logic: architectures, synthesis, and applications : 4th International Workshop on Field-Programmable Logic and Applications. Lecture notes in computer science, vol. 849. 352--360.

[8]

Eisenmann, H. and Johannes, F. M. 1998. Generic global placement and floorplanning. In Proceedings of the 35th ACM/IEEE Design Automation Conference. 269--274.

[9]

Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability. W. H. Freeman and Company, New York.

[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]

Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. 1997. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the 34th ACM/IEEE Design Automation Conference. 526--529.

[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]

Leeser, M., Meleis, W. M., Vai, M. M., Chiricescu, S., Xu, W., and Zavracky, P. M. 1998. Rothko: A three-dimensional FPGA. IEEE Designs and Test of Computers 15, 1 (Jan.), 16--23.

[16]

Leighton, F. T. and Rosenberg, A. L. 1986. Three-dimensional circuit layouts. SIAM J. Comput. 15, 3 (Aug.), 793--813.

[17]

Obenaus, S. T. and Szymanski, T. H. 1999. Placement benchmarks for 3-D VLSI. In VLSI: Systems on a Chip, L. M. Silveira, S. Devadas, and R. Reis, Eds. Kluwer Academic Publishing, 447--455.

[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]

Parakh, P. N., Brown, R. B., and Sakallah, K. A. 1998. Congestion driven quadratic placement. In Proceedings of the 35th ACM/IEEE Design Automation Conference. 275--278.

[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]

Shahookar, K. and Mazumder, P. 1991. VLSI cell placement techniques. ACM Comput. Surveys 23, 2 (June), 143--220.

[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]

Tong, C. C. and Wu, C. 1995. Routing in a three-dimensional chip. IEEE Trans. Comput. 44, 1 (Jan.), 106--117.

[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]

Tsay, R.-S., Kuh, E. S., and Hsu, C.-P. 1988. PROUD: A fast sea-of-gates placement algorithm. In Proceedings of the 25th ACM/IEEE Design Automation Conference. 318--323.

[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]

Vygen, J. 1997. Algorithms for large-scale flat placement. In Proceedings of the 34th ACM/IEEE Design Automation Conference. 746--751.

[30]

Wipfler, G. J., Wiesel, M., and Mlynski, D. A. 1982. A combined force and cut algorithm for hierachical VLSI layout. In Proceedings of the 19th ACM/IEEE Design Automation Conference. 671--677.

Cited By

TAYU STAKAHASHI TKOBAYASHI EUENO S(2016)On the Three-Dimensional Channel RoutingIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E99.A.1813E99.A:10(1813-1821)Online publication date: 2016
https://doi.org/10.1587/transfun.E99.A.1813
Pangracious VMarrakchi ZMehrez HPangracious VMarrakchi ZMehrez H(2015)Three-Dimensional Integration: A More Than Moore TechnologyThree-Dimensional Design Methodologies for Tree-based FPGA Architecture10.1007/978-3-319-19174-4_2(13-41)Online publication date: 26-Jun-2015
https://doi.org/10.1007/978-3-319-19174-4_2
Sui WDong SBian JBahar RLombardi FAtienza DBrunvand E(2010)Wirelength-driven force-directed 3D FPGA placementProceedings of the 20th symposium on Great lakes symposium on VLSI10.1145/1785481.1785582(435-440)Online publication date: 16-May-2010
https://dl.acm.org/doi/10.1145/1785481.1785582
Show More Cited By

Index Terms

Gravity: Fast placement for 3-D VLSI
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

Placement of 3D ICs with thermal and interlayer via considerations
DAC '07: Proceedings of the 44th annual Design Automation Conference

Thermal problems and limitations on interlayer via densities are important design constraints on three-dimensional integrated circuits (3D ICs), and need to be considered during global and detailed placement. Analytical and partitioning-based techniques ...
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 ...
Thermal via placement in 3D ICs
ISPD '05: Proceedings of the 2005 international symposium on Physical design

As thermal problems become more evident, new physical design paradigms and tools are needed to alleviate them. Incorporating thermal vias into integrated circuits (ICs) is a promising way of mitigating thermal issues by lowering the thermal resistance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 8, Issue 3

July 2003

127 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/785411

Issue’s Table of Contents

Copyright © 2003 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 July 2003

Published in TODAES Volume 8, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
727
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

TAYU STAKAHASHI TKOBAYASHI EUENO S(2016)On the Three-Dimensional Channel RoutingIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E99.A.1813E99.A:10(1813-1821)Online publication date: 2016
https://doi.org/10.1587/transfun.E99.A.1813
Pangracious VMarrakchi ZMehrez HPangracious VMarrakchi ZMehrez H(2015)Three-Dimensional Integration: A More Than Moore TechnologyThree-Dimensional Design Methodologies for Tree-based FPGA Architecture10.1007/978-3-319-19174-4_2(13-41)Online publication date: 26-Jun-2015
https://doi.org/10.1007/978-3-319-19174-4_2
Sui WDong SBian JBahar RLombardi FAtienza DBrunvand E(2010)Wirelength-driven force-directed 3D FPGA placementProceedings of the 20th symposium on Great lakes symposium on VLSI10.1145/1785481.1785582(435-440)Online publication date: 16-May-2010
https://dl.acm.org/doi/10.1145/1785481.1785582
Pavlidis VFriedman E(2010)Physical Design Issues in 3-D Integrated TechnologiesVLSI-SoC: Design Methodologies for SoC and SiP10.1007/978-3-642-12267-5_1(1-21)Online publication date: 2010
https://doi.org/10.1007/978-3-642-12267-5_1
Pavlidis VFriedman E(2009)Interconnect-Based Design Methodologies for Three-Dimensional Integrated CircuitsProceedings of the IEEE10.1109/JPROC.2008.200747397:1(123-140)Online publication date: Jan-2009
https://doi.org/10.1109/JPROC.2008.2007473
Yuh PYang CChang Y(2007)Placement of defect-tolerant digital microfluidic biochips using the T-tree formulationACM Journal on Emerging Technologies in Computing Systems10.1145/1295231.12952343:3(13-es)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1145/1295231.1295234
Zhou LWakayama CShi C(2007)CASCADE: A Standard Supercell Design Methodology With Congestion-Driven Placement for Three-Dimensional Interconnect-Heavy Very Large-Scale Integrated CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2006.88826626:7(1270-1282)Online publication date: Jul-2007
https://doi.org/10.1109/TCAD.2006.888266
Yan HLi ZHong XZhou Q(2007)Unified Quadratic Programming Approach For 3-D Mixed Mode Placement2007 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.2007.378300(3411-3414)Online publication date: May-2007
https://doi.org/10.1109/ISCAS.2007.378300
Tayu SUeno S(2007)On the Complexity of Three-Dimensional Channel Routing (Extended Abstract)2007 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.2007.378297(3399-3402)Online publication date: May-2007
https://doi.org/10.1109/ISCAS.2007.378297
Li JMiyashita H(2007)Efficient Thermal Via Planning for Placement of 3D Integrated Circuits2007 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.2007.378242(145-148)Online publication date: May-2007
https://doi.org/10.1109/ISCAS.2007.378242
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents