Article

Free access

Area minimization for hierarchical floorplans

Authors:

C. L. LiuAuthors Info & Claims

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

Pages 436 - 440

Published: 06 November 1994 Publication History

Abstract

Two results are presented in this paper. First we settle the open problem on the complexity of the area minimization problem for hierarchical floorplans by showing it to be N P-complete. We then present a pseudo-polynomial area minimization algorithm for hierarchical floorplans of order-5. The algorithm is based on a new algorithm for determining the set of nonredundant realizations of a wheel. The new algorithm for wheels has time cost O(k²logk) and space cost O(k²) if each of the (five) blocks in a wheel has at mostkrealizations—a reduction by a factor of k in both costs in comparison with previous algorithms. The area minimization algorithm was implemented. Our experimental results show that the algorithm is indeed very fast.

References

[1]

C.-H. Chen and I.G. Tollis, "Area optimization of spiral floorplans," Technical Report, The University of Texas at Dallas, 1992.

[2]

K. Chong and S. Sahni, "Optimal realizations of floorplans," in IEEE Trans. on Computer-Aided Design, vol. CAD-12, no. 6, pp. 793-801, 1993.

[3]

W.-M. Dai and E.S. Kuh, "Simultaneous floor planning and global routing for hierarchical building block layout," in IEEE Trans. on Computer-Aided Design, vol. CAD-6, no. 5, pp. 828-837, 1987.

[4]

M. L. Fredman, "How good is the information theory bound in sorting?," in Theoretical Computer Science 1, pp. 355- 361, 1976.

[5]

M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-compIeteness. Freeman, San Francisco, 1979.

Digital Library

[6]

T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout. John Wiley & Sons, New York, 1990.

Digital Library

[7]

T. Lengauer and R. Muller, "Robust and accurate hierarchical floorplanning with integrated global wiring," in IEEE Trans. on Computer-Aided Design, vol. CAD-12, no. 6, pp. 802-809, 1993.

[8]

R.H.J.M. Otten, "Automatic floorplan design," in Proc. 19th A CM/IEEE Design Automation Conf., 1982, pp. 261- 267.

Digital Library

[9]

P. Pan and C. L. Liu, "Area minimization for general floorplans," in Digest Int'I. Conf. on Computer-Aided Design, 1992, pp. 606-609.

Digital Library

[10]

L. Stockmeyer, "Optimal orientations of cells in slicing floorplan designs," in Info. and Control, vol. 59, pp. 91- 101, 1983.

Digital Library

[11]

K. J. Supowit and E. A. Slutz, "Placement algorithms for custom VLSI," in Computer Aided Design, vol. 16, no. 1, pp. 45-50, 1984.

[12]

Ting-Chi Wang and D.F. Wong, "Optimal floorplan area optimization," in IEEE Trans. on Computer-Aided Design, vol. CAD-11, no. 8, pp. 992-1002, 1992.

[13]

S. Wimer, I. Koren, and I. Cederbaum, "Optimal aspect ratios of building blocks in VLSI," in IEEE Trans. on Computer-Aided Design, vol. 8, no 2, pp. 139-145, 1989.

Digital Library

[14]

D.F. Wong and P.S. Sakhamuri, "Efficient floorplan area optimization," in Proc. 26th A CM//IEEE Design Automation Conf., 1989, pp. 586-589.

Digital Library

[15]

K. H. Yeap and M. Sarrafzadeh, "An integrated algorithm for optimal floorplan sizing and enumeration," in European Design Automation Conf., 1993, pp. 29-33.

[16]

G. Zimmermann, "A new area and shape function estimation technique for VLSI layouts," in Proc. 25th A CM//IEEE Design Automation Conf., 1988, pp. 60-65.

Digital Library

Cited By

Yamanouchi TTamakashi KKambe TRutenbar ROtten R(1997)Hybrid floorplanning based on partial clustering and module restructuringProceedings of the 1996 IEEE/ACM international conference on Computer-aided design10.5555/244522.244863(478-483)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.5555/244522.244863
Dasgupta PSur-Kolay SBhattacharya BRudell R(1995)A unified approach to topology generation and area optimization of general floorplansProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225150(712-715)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225150
Shi WRudell R(1995)An optimal algorithm for area minimization of slicing floorplansProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225096(480-484)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225096
Show More Cited By

Index Terms

Area minimization for hierarchical floorplans
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Area minimization for hierarchical floorplans

In this paper we study the area-minimization problem for hierarchical floorplans. We settle an open problem on the complexity of the area-minimization problem for hierarchical floorplans by showing it to be NP-complete (even for balanced hierarchical ...
Area minimization for floorplans

In this paper we study the area minimization problem in floorplanning (also known as the floorplan sizing problem). For a given floorplan, the problem is to select a layout alternative for each subcircuit on a chip so as to minimize the chip area. Two ...
An optimal algorithm for area minimization of slicing floorplans
ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

The traditional algorithm of Stockmeyer for area minimization of slicing floorplans has time (and space) complexity O(n^2) in the worst case, or O(n\log n) for balanced slicing. For more than a decade, it is considered the best possible. In this paper, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

November 1994

771 pages

ISBN:0897916905

Chairmen:
Jochen A. G. Jess
Eindhoven Univ. of Technology, Eindhoven, The Netherlands
,
Richard Rudell
Synopsys, Inc., Mountain View, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 06 November 1994

Check for updates

Qualifiers

Article

Conference

ICCAD '94

Sponsor:

SIGDA
IEEE-CS

ICCAD '94: International Conference on Computer Aided Design

November 6 - 10, 1994

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
194
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)6

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yamanouchi TTamakashi KKambe TRutenbar ROtten R(1997)Hybrid floorplanning based on partial clustering and module restructuringProceedings of the 1996 IEEE/ACM international conference on Computer-aided design10.5555/244522.244863(478-483)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.5555/244522.244863
Dasgupta PSur-Kolay SBhattacharya BRudell R(1995)A unified approach to topology generation and area optimization of general floorplansProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225150(712-715)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225150
Shi WRudell R(1995)An optimal algorithm for area minimization of slicing floorplansProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225096(480-484)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225096
Murata HFujiyoshi KNakatake SKajitani YRudell R(1995)Rectangle-packing-based module placementProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225094(472-479)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225094

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents