On the complexity of graph cuboidal dual problems for 3-D floorplanning of integrated circuit design

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of graph cuboidal dual problems for 3-D floorplanning of integrated circuit design

Full text

Pdf (589 KB)

Source

Great Lakes Symposium on VLSI archive
Proceedings of the 19th ACM Great Lakes symposium on VLSI table of contents

Boston Area, MA, USA

SESSION: Emerging technology and post-CMOS table of contents

Pages 257-262

Year of Publication: 2009

ISBN:978-1-60558-522-2

Authors

Renshen Wang	University of California, San Diego, La Jolla, CA, USA
Chung-Kuan Cheng	University of California, San Diego, La Jolla, CA, USA

Sponsors

ACM: Association for Computing Machinery
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 22, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1531542.1531604 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.