Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper discusses the impact of migrating from 2-D to 3-D on floorplanning and placement. By looking at a basic formulation of graph cuboidal dual problem, we show that the 3-D case and the 3-layer 2.5-D case are fundamentally more difficult than the 2-D case in terms of computational complexity. By comparison among these cases, the intrinsic complexity in 3-D floorplan structures is revealed in the hard-deciding relations between topological connections and geometrical contacts. The results show future challenges for physical design and CAD of 3-D integrated circuits.

REFERENCES

• 1: Jayaram Bhasker , Sartaj Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph, Proceedings of the 23rd ACM/IEEE Design Automation Conference, p.108-114, July 1986, Las Vegas, Nevada, United States
• 2: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 3: Yangdong (Steven) Deng , Wojciech Maly, Physical Design of the "2.5D" Stacked System, Proceedings of the 21st International Conference on Computer Design, p.211, October 13-15, 2003
• 4: Brent Goplen , Sachin Spatnekar, Placement of 3D ICs with thermal and interlayer via considerations, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278637]
• 5: Goos Kant , Xin He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoretical Computer Science, v.172 n.1-2, p.175-193, Feb. 10, 1997 [doi>10.1016/S0304-3975(95)00257-X]
• 6: Krzysztof Kozminski , Edwin Kinnen, An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits., Proceedings of the 21st Design Automation Conference, p.655-656, June 25-27, 1984, Albuquerque, New Mexico, United States
• 7: D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput. Volume 11, Issue 2, pages 329--343, 1984.
• 8: Sung Kyu Lim, Physical Design for 3D System on Package, IEEE Design & Test, v.22 n.6, p.532-539, November 2005 [doi>10.1109/MDT.2005.149]
• 9: G.-M. Wu, J.-M. Lin, and Y.-W. Chang. An algorithm for dynamically reconfigurable FPGA placement. IEEE ICCD, pages 501 -- 504, 2001.
• 10: H. Yamazaki, K. Sakanushi, S. Nakatake, and Y. Kajitani. The 3D-packing by meta data structure and packing heuristics. IEICE Trans. Fundamentals, pages 639--645, Apr. 2000.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
3-D integrated circuits, computational complexity, cuboidal dual