Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Hierarchical partitioning of VLSI floorplans by staircases

Published: 02 February 2007 Publication History

Abstract

This article addresses the problem of recursively bipartitioning a given floorplan F using monotone staircases. At each level of the hierarchy, a monotone staircase from one corner of F to its opposite corner is identified, such that (i) the two parts of the bipartition are nearly equal in area (or in the number of blocks), and (ii) the number of nets crossing the staircase is minimal. The problem of area-balanced bipartitioning is shown to be NP-hard, and a maxflow-based heuristic is proposed. Such a hierarchy may be useful to repeater placement in deep-submicron physical design, and also to global routing.

References

[1]
Burman, S., Chen, H., and Sherwani, N. 1991. Improved global routing using Δ-geometry. In Proceedings of the 29th Annual Allerton Conference on Communication, Computing, and Control.
[2]
Chang, C.-C., Cong, J., Pan, Z., and Yun, X. 2003. Multilevel global placement with congestion control. IEEE Trans. Comput.-Aid. Des. Integrat. Circ. Syst. 22, 4 (Apr.), 395--409.
[3]
Chu, C. C. N. and Wong, D. F. 1997. Closed form solution to simultaneous buffer insertion/sizing and wire sizing. In Proceedings of the International Symposium on Physical Design. 192--197.
[4]
Cong, J. 1997. Challenges and opportunities for design innovations in nanometer technologies. In Frontier in Semiconductor Research: A Collection of SRC Working Papers. Semiconductor Research Corporation. http://www.src.org/prg_mgmt/frontier.dgw.
[5]
Cong, J., He, L., Koh, C. K., and Madden, P. H. 1996. Performance optimization of VLSI interconnect layout. Integration, VLSI J. 21, 1--94.
[6]
Cong, J., Kong, T., and Pan, D. Z. 1999a. Buffer block planning for interconnect-driven floorplanning. In IEEE/ACM Digest of Technical Papers, International Conference on Computer Aided Design (ICCAD). 358--363.
[7]
Cong, J., Kong, T., and Pan, D. Z. 1999b. Interconnect delay estimation models for synthesis and design planning. In Proceedings of the Asia and South Pacific Design Automation Conference. 97--100.
[8]
Das, S., Sur-Kolay, S., and Bhattacharya, B. B. 2004. Manhattan-diagonal routing in channels and switchboxes. ACM Trans. Des. Automat. Electon. Syst. 9, 1, 75--104.
[9]
Dasgupta, P. S., Pan, P., Nandy, S. C., and Bhattacharya, B. B. 2002. Monotone bipartitioning problem in a planar point set with applications to VLSI. ACM Trans. Des. Automat. Electron. Syst. 7, 2, 231--248.
[10]
Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to Theory of NP-Completeness. W. H. Freeman and Co., New York, NY.
[11]
Guruswamy, M. and Wong, D. F. 1988. Channel routing order for building-block layout with rectilinear modules. In IEEE/ACM Digest of Technical Papers, International Conference on Computer-Aided Design (ICCAD). 184--187.
[12]
King, V., Rao, S., and Tarjan, R. E. 1995. A faster deterministic maxflow algorithm. J. Algorithm. 17, 3, 447--474.
[13]
Majumder, S. 1996. Routing driven floorplan partitioning using staircase channel. M.S. thesis. Indian Statistical Institute, Kolkata, India.
[14]
Majumder, S., Nandy, S. C., and Bhattacharya, B. B. 2004. On finding a staircase channel with minimum crossing nets in a VLSI floorplan. J. Circ. Syst. Comput. 13, 5, 1019--1038.
[15]
Majumder, S., Sur-Kolay, S., Bhattacharya, B. B., and Nandy, S. C. 2001. Area(number)-balanced hierarchy of staircase channels with minimum crossing nets. In Proceedings of the International Symposium on Circuits and Systems (ISCAS, Sydney, Australia). Vol. V. 395--398.
[16]
Nandy, S. C. and Bhattacharya, B. B. 2003. On finding an empty staircase polygon of largest area (width) in a planar point-set. Computat. Geom. Theor. Appl. 26, 143--171.
[17]
Okamoto, T. and Cong, J. 1996. Interconnect layout optimization by simultaneous steiner tree construction and buffer insertion. In Proceedings of the ACM/SIGDA Physical Design Workshop. 1--6.
[18]
Papadimitriou, C. H. and Steiglitz, K. 1982. Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, Englewood Cliffs, NJ.
[19]
Sarkar, P. and Koh, C. K. 2001. Routability-driven repeater block planning for interconnect-centric floorplanning. IEEE Trans. Comput.-Aid. Des. Integrat. Circ. Syst. 20, 660--671.
[20]
Sherwani, N. 1993. Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers, Boston, MA.
[21]
Sun, R., Gupta, R., and Liu, C. 1996. Congestion-balanced placement for FPGAs. In Proceedings of the 5th Physical Design Workshop. 163--168.
[22]
Sur-Kolay, S. 1991. Studies on nonslicible floorplans in VSLI layout design. PH.D thesis, Jadavpur University, Calcutta, India.
[23]
Sur-Kolay, S. and Bhattacharya, B. B. 1991. The cycle structure of channel graphs in non-sliceable floorplans and a unified algorithm for feasible routing order. In Proceedings of the International Conference on Computer Design (ICCD). IEEE Computer Society Press, Los Alamitos, CA, 524--529.
[24]
Yang, H. H. and Wong, D. F. 1996. Efficient network flow based min-cut balanced partitioning. IEEE Trans. Comput.-Aid. Des. Integrat. Circ. Syst. 15, 1533--1540.

Cited By

View all
  • (2015)A New Method for Defining Monotone Staircases in VLSI Floorplans2015 IEEE Computer Society Annual Symposium on VLSI10.1109/ISVLSI.2015.47(107-112)Online publication date: Jul-2015
  • (2015)Constrained floorplans in 2D and 3DTheoretical Computer Science10.1016/j.tcs.2015.07.063607:P3(320-336)Online publication date: 23-Nov-2015
  • (2014)Global Routing Using Monotone Staircases with Minimal BendsProceedings of the 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems10.1109/VLSID.2014.70(369-374)Online publication date: 5-Jan-2014
  • Show More Cited By

Recommendations

Reviews

I-Lun Tseng

The partitioning of floorplans is an important topic in the field of very large-scale integration (VLSI) physical design automation. Proper partitioning of floorplans can lead to not only efficient insertion of repeaters, but also efficient global and channel routing. As a result, the quality of physical layouts can be improved and the design time can be reduced. In this paper, a floorplan is defined to contain a number of rectangular blocks, and each of those blocks may have associated nets. An ms-cut is a monotone staircase that partitions rectangular blocks of a floorplan into two groups, and the monotone staircase cuts those blocks from the floorplan's bottom-left corner to the floorplan's top-right corner; the staircase does not go down or go left when it cuts the floorplan. Since a floorplan can have many different ms-cuts, there are a variety of problems with regard to the partitioning of a floorplan with ms-cuts. A number of floorplan partitioning problems are discussed in the paper. The min-cut problem P c is to find an ms-cut that minimizes the number of nets crossing the two partitions. The number-balance problem P n is to find an ms-cut that balances the numbers of rectangular blocks for the two partitions, whereas the area-balance problem P A is to find an ms-cut that balances the areas of the two partitions. Furthermore, there is the number-balanced min-cut problem P nc and the area-balanced min-cut problem P Ac ; the two problems consider the number of crossing nets as well as one of the balancing factors. Before this paper was published, it had already been proven that problems P c and P n are polynomial time solvable. The paper goes one step further and attacks other floorplan partitioning problems: it proves that P A and P Ac are nondeterministic polynomial time (NP) hard, and conjectures that P nc is also NP hard. Furthermore, the paper proposes a heuristic for solving these difficult problems. The heuristic is based on a max-flow min-cut method, and is capable of partitioning (or bi-partitioning) a floorplan hierarchically. The paper discusses a number of floorplan partitioning problems. These problems are clearly presented and are interesting. The heuristic proposed for solving some of these problems is flexible and efficient. Moreover, partitioning a floorplan using monotone staircase cuts can be beneficial to other VLSI physical design processes. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems
ACM Transactions on Design Automation of Electronic Systems  Volume 12, Issue 1
January 2007
194 pages
ISSN:1084-4309
EISSN:1557-7309
DOI:10.1145/1188275
Issue’s Table of Contents
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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication History

Published: 02 February 2007
Published in TODAES Volume 12, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Floorplanning
  2. NP-completeness
  3. balanced bipartitioning
  4. global routing
  5. network flow

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)A New Method for Defining Monotone Staircases in VLSI Floorplans2015 IEEE Computer Society Annual Symposium on VLSI10.1109/ISVLSI.2015.47(107-112)Online publication date: Jul-2015
  • (2015)Constrained floorplans in 2D and 3DTheoretical Computer Science10.1016/j.tcs.2015.07.063607:P3(320-336)Online publication date: 23-Nov-2015
  • (2014)Global Routing Using Monotone Staircases with Minimal BendsProceedings of the 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems10.1109/VLSID.2014.70(369-374)Online publication date: 5-Jan-2014
  • (2013)STAIRoute: Global routing using monotone staircase channels2013 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI.2013.6654628(90-95)Online publication date: Aug-2013
  • (2012)A faster hierarchical balanced bipartitioner for VLSI floorplans using monotone staircase cutsProceedings of the 16th international conference on Progress in VLSI Design and Test10.1007/978-3-642-31494-0_37(327-336)Online publication date: 1-Jul-2012

View Options

Login options

Full Access

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