skip to main content
10.1145/1120725.1120899acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

Floorplanning for 3-D VLSI design

Published: 18 January 2005 Publication History

Abstract

In this paper we present a floorplanning algorithm for 3-D ICs. The problem can be formulated as that of packing a given set of 3-D rectangular blocks while minimizing a suitable cost function. Our algorithm is based on a generalization of the classical 2-D slicing floorplans to 3-D slicing floorplans. A new encoding scheme of slicing floorplans (2-D/3-D) and its associated set of moves form the basis of the new simulated annealing based algorithm. The bestknown algorithm for packing 3-D rectangular blocks is based on simulated annealing using sequence-triple floorplan representation. Experimental results show that our algorithm produces packing results on average 3% better than the sequence-triple-based algorithm under the same annealing parameters, and our algorithm runs much faster (17 times for problems containing 100 blocks) than the sequence-triple. Moreover, our algorithm can be extended to consider various types of placement constraints and thermal distribution while the existing sequence-triple-based algorithm does not have such capabilities. Finally, when specializing to 2-D problems, our algorithm is a new 2-D slicing floorplanning algorithm. We are excited to report the surprising results that our new 2-D floorplanner has produced slicing floorplans for the two largest MCNC benchmarks ami33 and ami49 which have the smallest areas (among all slicing/nonslicing floorplanning algorithms) ever reported in the literature.

References

[1]
K. Banerjee, S. J. Souri, P. Kapur, and K. C. Saraswat. 3-D ICs: a novel chip design for improving deep submicrometer interconnect performance and systems-on-chip integration. Proc. of the IEEE, 89(5):602--633, May 2001.
[2]
A. Fan, A. Rahman, and R. Reif. Copper wafer bonding. Electrochem. Solid State Lett., 2:534C536, 1999.
[3]
M. Chan and P. K. Ko. Development of a viable 3d integrated circuit technology. Science in China, 44(4):241--248, August 2001.
[4]
Ralph H. J. M. Otten. Automatic floorplan design. Proc. of DAC, pages 261--267, 1982.
[5]
D. F. Wong and C. L. Liu. A new algorithm for floorplan design. Proc. of DAC, pages 101--107, 1986.
[6]
H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. Rectangle-packing-based module placement. Proc. of ICCAD, pages 472--479, 1995.
[7]
X. Hong et al. Corner block list: An effective and efficient topological representation of non-slicing floorplan. Proc. of ICCAD, pages 8--11, 2000.
[8]
Evangeline F. Y. Yong, Chris C. N. Chu, and Zion C. S. Twin binary sequences: A nonredundant representation for general nonslicing floorplan. IEEE TCAD of Integrated Circuits and Systems, 22(4):457--469, April 2003.
[9]
Y. Pang, C. K. Cheng, and T. Yoshimura. An enhanced perturbing algorithm for floorplan design using the O-tree representation. Proc. of ISPD, pages 168--173, 2000.
[10]
Hiroyuki Yamazaki et al. The 3d-packing by meta data structure and packing heuristics. IEICE Trans. Fundamentals, E83-A(4):639--645, April 2000.
[11]
Evangeline F. Y. Yong, D. F. Wong, and H. H. Yang. Slicing floorplans with boundary constraints. IEEE TCAD of Integrated Circuits and Systems, 18(9):1385--1389, September 1999.
[12]
Evangeline F. Y. Yong, D. F. Wong, and H. H. Yang. Slicing Floorplans with Range Constraint. IEEE TCAD of Integrated Circuits and Systems, 19(2):272--278, February 2000.
[13]
Kaustav Banerjee et al. On thermal effects in deep submicron vlsi interconnects. Proc. of DAC, pages 885--891, 1999.
[14]
Wei Huang et al. Compact thermal modeling for temperature-aware design. Proc. of DAC, pages 878--883, 2004.
[15]
D. Chen, E. Li, E. Rosenbaum, and S. M. Kang. Interconnect thermal modeling for accurate simulation of circuit timing and reliability. IEEE TCAD of Integrated Circuits and Systems, 19(2):197--205, February 2000.
[16]
X. Tang and D. F. Wong. Fast-sp: A fast algorithm for block placement based on sequence pair. Proc. of ASPDAC, pages 521--526, 2001.
[17]
S. Zhou, S. Dong, X. Hong, Y. Cai, and C. K. Cheng. ECBL: An extended corner block list with solution space including optimum placement. Proc. of ISPD, pages 156--161, 2001.
[18]
C. Zhuang, K. Sakanushi, L. Jin, and Y. Kajitani. An enhanced Q-sequence augmented with empty-room-insertion and parenthesis trees. Proc. of DATE, pages 61--68, 2002.

Cited By

View all
  1. Floorplanning for 3-D VLSI design

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference
    January 2005
    1495 pages
    ISBN:0780387376
    DOI:10.1145/1120725
    • General Chair:
    • Ting-Ao Tang
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 18 January 2005

    Permissions

    Request permissions for this article.

    Check for updates

    Qualifiers

    • Article

    Conference

    ASPDAC05
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 466 of 1,454 submissions, 32%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)24
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 09 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Multi-Objective Optimization in 3D FloorplanningElectronics10.3390/electronics1309169613:9(1696)Online publication date: 27-Apr-2024
    • (2023)Learning Based 2D Irregular Shape PackingACM Transactions on Graphics10.1145/361834842:6(1-16)Online publication date: 5-Dec-2023
    • (2022)A Comprehensive Analysis in Recent Advances in 3D VLSI Floorplan RepresentationsAdvances in VLSI and Embedded Systems10.1007/978-981-19-6780-1_20(243-265)Online publication date: 1-Dec-2022
    • (2019)A Non-Slicing 3-D Floorplan Representation for Monolithic 3-D IC Design20th International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2019.8697605(323-328)Online publication date: Mar-2019
    • (2018)Co-synthesis of floorplanning and powerplanning in 3D ICs for multiple supply voltage designs2018 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE.2018.8342221(1339-1344)Online publication date: Mar-2018
    • (2018)Three-dimensional Floorplan Representations by Using Corner Links and Partial OrderACM Transactions on Design Automation of Electronic Systems10.1145/328917924:1(1-33)Online publication date: 21-Dec-2018
    • (2017)Routability-Driven TSV-Aware Floorplanning Methodology for Fixed-Outline 3-D ICsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.269590036:11(1856-1868)Online publication date: Nov-2017
    • (2017)Hypergraphs and extremal optimization in 3D integrated circuit design automationAdvanced Engineering Informatics10.1016/j.aei.2017.06.00433:C(491-501)Online publication date: 1-Aug-2017
    • (2016)3D floorplan representations: Corner links and partial order2016 IEEE International 3D Systems Integration Conference (3DIC)10.1109/3DIC.2016.7970023(1-5)Online publication date: Nov-2016
    • (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
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media