Article

Simultaneous block and I/O buffer floorplanning for flip-chip design

Authors:

Chih-Yang Peng,

Wen-Chang Chao,

Jyh-Herng WangAuthors Info & Claims

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

Pages 213 - 218

https://doi.org/10.1145/1118299.1118357

Published: 24 January 2006 Publication History

Abstract

The flip-chip package gives the highest chip density of any packaging method to support the pad-limited ASIC design. One of the most important characteristics of flip-chip designs is that the input/output buffers could be placed anywhere inside a chip. In this paper, we first introduce the floorplanning problem for the flip-chip design and formulate it as assigning the positions of input/output buffers and first-stage/last-stage blocks so that the path length between blocks and bump balls as well as the delay skew of the paths are simultaneously minimized. We then present a hierarchical method to solve the problem. We first cluster a block and its corresponding buffers to reduce the problem size. Then, we go into iterations of the alternating and interacting global optimization step and the partitioning step. The global optimization step places blocks based on simulated annealing using the B*-tree representation to minimize a given cost function. The partitioning step dissects the chip into two subregions, and the blocks are divided into two groups and are placed in respective subregions. The two steps repeat until each subregion contains at most a given number of blocks, defined by the ratio of the total block area to the chip area. At last, we refine the floorplan by perturbing blocks inside a subregion as well as in different subregions. Compared with the B*-tree based floorplanner alone, our method is more efficient and obtains significantly better results, with an average cost of only 51.8% of that obtained by using the B*-tree alone, based on a set of real industrial flip-chip designs provided by leading companies.

References

[1]

S. N. Adya, I. L. Markov, and P. G. Villarrubia, "On whitespace in mixed-size placement and physical synthesis," Proc. of IEEE/ACM Int. Conf. on Computer-Aided Design, pp. 311--318, 2003.

Digital Library

[2]

A. R. Agnihotri, M. C. Yildiz, A. Khatkhate, A. Mathur, S. Ono, and P. H. Madden, "Fractical cut: improved recursive bisection placement," Proc. of IEEE/ACM Int. Conf. on Computer-Aided Design, pp. 307--310, 2003.

Digital Library

[3]

P. H. Buffet, J. Natonio, R. A. Proctor, Yu H. Sun, and G. Yasar, "Methodology for I/O cell placement and checking in ASIC designs using area-array power grid," Proc. of IEEE Custom Integrated Circuits Conf., pp. 125--128, 2000.

[4]

B*-tree: http://cc.ee.ntu.edu.tw/~ywchang/research.html.

[5]

A. E. Caldwell, A. B. Kahng, and I. L. Markov, "Can recursive bisection alone produce routable placement?," Proc. of ACM/IEEE Design Automation Conf., pp. 477--482, 2000.

Digital Library

[6]

H. H. Chan, S. N. Adya, and I. L. Markov, "Are floorplan representations important in digital design?" Proc. of ACM International Symposium on Physical Design, pp. 129--136, 2005.

Digital Library

[7]

T. Chan, J. Cong, and K. Sze, "Multilevel generalized force-directed method for circuit placement," Proc. of ACM International Symposium on Physical Design, 2005.

Digital Library

[8]

C. C. Chang, J. Cong, and X. Yuan, "Multilevel placement for large-scale mixed-size IC designs," Proc. of ACM/IEEE Asia and South Pacific Design Automation Conf., pp. 325--330, 2003.

Digital Library

[9]

Y.-C. Chang, Y-W. Chang, G.-M. Wu, and S.-W. Wu, "B*-Trees: a new representation for non-slicing floorplans," Proc. of ACM/IEEE Design Automation Conf., pp. 458--463, 2000.

Digital Library

[10]

J. Con, G. Nataneli, M. Romesis, and J. R. Shinnerl, "An area-optimality study of floorplanning," Proc. of ACM International Symposium on Physical Design, pp. 78--83, April 2004.

Digital Library

[11]

P. Dehkordi and D. Bouldin, "Design for packageability: the impact of bonding technology on the size and layout of VLSI dies," Proc. Multichip Module Conf., pp. 153--159, 1993.

[12]

H. Eisenmann and F. M. Johannes, "Generic global placement and floorplanning," Proc. of ACM/IEEE Design Automation Conf., pp. 269--274, 1998.

Digital Library

[13]

FengShui Placer. http://vlsicad.cs.binghamton.edu/software.html.

[14]

P.-N. Guo, C.-K. Cheng, and T. Yoshimura, "An O-tree representation of non-slicing floorplan and its applications," Proc. of ACM/IEEE Design Automation Conf., pp. 268--273, 1999.

Digital Library

[15]

H.-Y. Hsieh and T.-C. Wang, Simple yet effective algorithms for block and I/O buffer placement in flip-chip designs, Proc. of IEEE International Symposium on Circuits and Systems, pp. 1879--1882, May 2005.

[16]

A. B. Kahng and Q. Wang, "Implementation and extensibility of an analytic placer," Proc. of ACM International Symposium on Physical Design, pp. 18--25, April 2004.

Digital Library

[17]

A. Khatkhate, C. Li, A. R. Agnihotri, M. C. Yildiz, S. Ono, C.-K. Koh, and P. H. Madden, "Recursive bisection based mixed block placement," Proc. of ACM International Symposium on Physical Design, pp. 84--89, April 2004.

Digital Library

[18]

J. M. Kleinhans, G. Sigl, F. M. Johannes, K. J. Antreich, "GORDIAN: VLSI placement by quadratic programming and slicing optimization," IEEE Trans. Computer-Aided Design, pp. 356--365, 1991.

Digital Library

[19]

J. N. Kozhaya, S. R. Nassif, F. N. Najm, "I/O buffer placement methodology for ASICs," Proc. of IEEE International Conference on Electronics, Circuits and System, pp. 245--248, 2001.

[20]

H.-C. Lee, Y.-W. Chang, J.-M. Hsu, and H. Yang, "Multilevel floorplanning/placement for large-scale modules using B*-trees," Proc. of ACM/IEEE Design Automation Conf., Anaheim, CA, June 2003.

Digital Library

[21]

J.-M. Lin and Y.-W. Chang, "TCG: A transitive closure graph based representation for non-slicing floorplans," Proc. of ACM/IEEE Design Automation Conf., pp. 764--769, Las Vegas, NV, June 2001.

Digital Library

[22]

mGP: Multilevel Global Placement. http://ballade.cs.ucla.edu/mGP/.

[23]

Parquet: Fixed-Outline Floorplanner, http://vlsicad.eecs.umich.edu/BK/parquet/

[24]

N. Viswanathan and C. C.-N. Chu, "FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model," Proc. of ACM International Symposium on Physical Design, pp. 26--33, April 2004.

Digital Library

[25]

M. Wang, X. Yang, and M. Sarrafzadeh, "Dragon2000: standard-cell placement tool for large industry circuits," Proc. of IEEE/ACM Int. Conf. on Computer-Aided Design, pp. 260--263, June 2000.

Digital Library

[26]

H. Zhou and J. Wang, "ACG-Adjacent constraint graph for general floorplans," Proc. of IEEE Int. Conf. on Computer Design, pp. 572--575, October 2004.

Digital Library

Cited By

Yan J(2016)Performance-Driven Assignment of Buffered I/O Signals in Area-I/O Flip-Chip DesignsACM Transactions on Design Automation of Electronic Systems10.1145/281864221:2(1-24)Online publication date: 28-Jan-2016
https://dl.acm.org/doi/10.1145/2818642
Ho YChang Y(2013)Multiple chip planning for chip-interposer codesignProceedings of the 50th Annual Design Automation Conference10.1145/2463209.2488767(1-6)Online publication date: 29-May-2013
https://dl.acm.org/doi/10.1145/2463209.2488767
Chong AChun H(2013)Unified Padring Design FlowProceedings of the 2013 Fifth International Conference on Computational Intelligence, Communication Systems and Networks10.1109/CICSYN.2013.72(418-423)Online publication date: 5-Jun-2013
https://dl.acm.org/doi/10.1109/CICSYN.2013.72
Show More Cited By

Index Terms

Simultaneous block and I/O buffer floorplanning for flip-chip design
1. Hardware

Recommendations

Simultaneous floor plan and buffer-block optimization

As technology advances and the number of interconnections among modules rapidly increases, timing closure, and design convergence are the most important concerns. Hence, it is desirable to consider interconnect optimization as early as possible. ...
Area-I/O flip-chip routing for chip-package co-design
ICCAD '08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design

The area-I/O flip-chip package provides a high chip-density solution to the demand of more I/O's in VLSI designs; it can achieve smaller package size, shorter wirelength, and better signal and power integrity. In this paper, we introduce the routing ...
Integrating buffer planning with floorplanning for simultaneous multi-objective optimization
ASP-DAC '04: Proceedings of the 2004 Asia and South Pacific Design Automation Conference

As the process technology advances into the deep submicron era, interconnect plays a dominant role in determining circuit performance and signal integrity. Buffer insertion is one of the most effective and popular techniques to reduce interconnect delay ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

January 2006

998 pages

ISBN:0780394518

General Chair:
Fumiyasu Hirose
Cadence Design Systems, Japan

Sponsors

IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

IEEE Press

Publication History

Published: 24 January 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
320
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yan J(2016)Performance-Driven Assignment of Buffered I/O Signals in Area-I/O Flip-Chip DesignsACM Transactions on Design Automation of Electronic Systems10.1145/281864221:2(1-24)Online publication date: 28-Jan-2016
https://dl.acm.org/doi/10.1145/2818642
Ho YChang Y(2013)Multiple chip planning for chip-interposer codesignProceedings of the 50th Annual Design Automation Conference10.1145/2463209.2488767(1-6)Online publication date: 29-May-2013
https://dl.acm.org/doi/10.1145/2463209.2488767
Chong AChun H(2013)Unified Padring Design FlowProceedings of the 2013 Fifth International Conference on Computational Intelligence, Communication Systems and Networks10.1109/CICSYN.2013.72(418-423)Online publication date: 5-Jun-2013
https://dl.acm.org/doi/10.1109/CICSYN.2013.72
Chong AChun H(2013)Unified Padring Design Flow - New Developments and ResultsProceedings of the 2013 1st International Conference on Artificial Intelligence, Modelling and Simulation10.1109/AIMS.2013.84(462-466)Online publication date: 3-Dec-2013
https://dl.acm.org/doi/10.1109/AIMS.2013.84
Lee HChang YGroeneveld PSciuto DHassoun S(2012)A chip-package-board co-design methodologyProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228557(1082-1087)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228557
Liu NLiu SYoshimura T(2012)Wirelength driven I/O buffer placement for flip-chip with timing-constrained2012 IEEE Asia Pacific Conference on Circuits and Systems10.1109/APCCAS.2012.6419114(631-634)Online publication date: Dec-2012
https://doi.org/10.1109/APCCAS.2012.6419114
Zhi-Wei Chen Jin-Tai Yan (2011)Timing-constrained I/O buffer placement for flip-chip designs2011 Design, Automation & Test in Europe10.1109/DATE.2011.5763102(1-6)Online publication date: Mar-2011
https://doi.org/10.1109/DATE.2011.5763102
Zeng Wang Yuchun Ma Sheqin Dong Yu Wang Xianlong Hong (2010)Incremental I/O planning with white space redistribution for flip-chip design2010 International Conference on Communications, Circuits and Systems (ICCCAS)10.1109/ICCCAS.2010.5581856(866-870)Online publication date: Jul-2010
https://doi.org/10.1109/ICCCAS.2010.5581856
Lin KHsu HLee RChen H(2010)Area-I/O RDL routing for chip-package codesign considering regional assignment2010 IEEE Electrical Design of Advanced Package & Systems Symposium10.1109/EDAPS.2010.5683021(1-4)Online publication date: Dec-2010
https://doi.org/10.1109/EDAPS.2010.5683021
Wang CMak WWakabayashi K(2009)Signal skew aware floorplanning and bumper signal assignment technique for flip-chipProceedings of the 2009 Asia and South Pacific Design Automation Conference10.5555/1509633.1509722(341-346)Online publication date: 19-Jan-2009
https://dl.acm.org/doi/10.5555/1509633.1509722
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten