Gravity
- 1 July 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Design Automation of Electronic Systems
- Vol. 8 (3) , 298-315
- https://doi.org/10.1145/785411.785413
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.Keywords
This publication has 9 references indexed in Scilit:
- Placement Benchmarks for 3-D VLSIPublished by Springer Nature ,2000
- Rothko: a three-dimensional FPGAIEEE Design & Test of Computers, 1998
- Routing in a three-dimensional chipIEEE Transactions on Computers, 1995
- An optoelectronic 3-D Field Programmable Gate ArrayPublished by Springer Nature ,1994
- VLSI cell placement techniquesACM Computing Surveys, 1991
- GORDIAN: VLSI placement by quadratic programming and slicing optimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Three-Dimensional Circuit LayoutsSIAM Journal on Computing, 1986
- CHAMP: Chip Floor Plan for Hierarchical VLSI Layout DesignIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- An efficient algorithm for the two-dimensional placement problem in electrical circuit layoutIEEE Transactions on Circuits and Systems, 1981