research-article

Linear constraint graph for floorplan optimization with soft blocks

Authors:

Hai ZhouAuthors Info & Claims

ICCAD '08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design

Pages 9 - 15

Published: 10 November 2008 Publication History

Abstract

In this paper, we propose the Linear Constraint Graph (LCG) as an efficient general floorplan representation. For n blocks, an LCG has at most 2n+3 vertices and at most 6n+2 edges. Operations with direct geometric meanings are developed to perturb the LCGs. We apply the LCGs to the floorplan optimization with soft blocks to leverage its advantage in terms of the sizes of the graphs, which will improve the efficiency of solving a complex mathematical program in the inner loop of the optimization that decide the block shapes without introducing overlaps to the non-slicing floorplans. Experimental results confirm that the LCGs are effective and efficient.

References

[1]

F. Y. Young, C. C. N. Chu, W. S. Luk, and Y. C. Wong, "Handling soft modules in general non-slicing floorplan using Lagrangian relaxation," IEEE TCAD, vol. 20, no. 5, pp. 687--692, May 2001.

Digital Library

[2]

E. F. Y. Young, C. C. N. Chu, and M. L. Ho, "Placement constraints in floorplan design," IEEE TVLSI, vol. 12, no. 7, pp. 735--745, July 2004.

Digital Library

[3]

C. Lin, H. Zhou, and C. Chu, "A revisit to floorplan optimization by Lagrangian relaxation," in ICCAD, 2006, pp. 164--171.

Digital Library

[4]

X. Tang, R. Tian, and M. D. F. Wong, "Minimizing wire length in floorplanning," IEEE TCAD, vol. 25, no. 9, pp. 1744--1753, Sept. 2006.

Digital Library

[5]

H.-C. Lee, Y.-W. Chang, and H. H. Yang, "MB*-Tree: A multilevel floorplanner for large-scale building-module design," IEEE TCAD, vol. 26, no. 8, pp. 1430--1444, Aug. 2007.

Digital Library

[6]

T. Ohtsuki, N. Sugiyama, and H. Kawanishi, "An optimization technique for integrated circuit layout design," in Proc. ICCST, Kyoto, Japan, 1970, pp. 67--68.

[7]

R. H. Otten, "What is floorplan?" in ISPD, 2000, pp. 201--206.

Digital Library

[8]

F. Y. Young, C. C. N. Chu, and Z. C. Shen, "Twin Binary Sequences: A non-redundant representation for general non-slicing floorplan," IEEE TCAD, vol. 22, no. 4, pp. 457--469, Apr. 2003.

Digital Library

[9]

J.-M. Lin and Y.-W. Chang, "TCG: A transitive closure graph-based representation for non-slicing floorplans," in DAC, 2001, pp. 764--769.

Digital Library

[10]

H. Zhou and J. Wang, "ACG-adjacent constraint graph for general floorplans," in ICCD, 2004, pp. 572--575.

Digital Library

[11]

J. Wang and H. Zhou, "Interconnect estimation without packing via ACG floorplans," in ASP-DAC, 2005, pp. 1152 -- 1155.

Digital Library

[12]

H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE TCAD, vol. 15, no. 12, pp. 1518--1524, Dec. 1996.

Digital Library

[13]

C. Lin, "Incremental mixed-signal layout generation concepts," Ph.D. dissertation, Eindhoven University of Technology, Eindhoven, The Netherlands, 2002.

[14]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. MIT Press, 2001.

Digital Library

[15]

CS2 version 4.3, "Andrew Goldberg's network optimization library," http://www.avglab.com/andrew/soft.html.

[16]

S. N. Adya and I. L. Markov, "Fixed-outline floorplanning: Enabling hierarchical design," IEEE TVLSI, vol. 11, no. 6, pp. 1120--1135, Dec. 2003.

Digital Library

Cited By

Cannon SMiracle SRandall DIndyk P(2015)Phase transitions in random dyadic tilings and rectangular dissectionsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722233(1573-1589)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722233
Tsao HChou PHuang SChang YLin MChen DLiu DPhillips JHu AGraeb H(2011)A corner stitching compliant B*-tree representation and its applications to analog placementProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132444(507-511)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132444
Wang JZhou HWakabayashi K(2009)Exploring adjacency in floorplanningProceedings of the 2009 Asia and South Pacific Design Automation Conference10.5555/1509633.1509726(367-372)Online publication date: 19-Jan-2009
https://dl.acm.org/doi/10.5555/1509633.1509726

Linear constraint graph for floorplan optimization with soft blocks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Constraint-driven floorplan repair
DAC '06: Proceedings of the 43rd annual Design Automation Conference

Floorplanning algorithms have traditionally underperformed experienced designers, even when relatively simple interconnect metrics are concerned. However, the sheer scale of modern systems on chip makes an all-manual design flow infeasible. In this ...
Graph-Based Techniques for Hierarchical Floorplan Area Optimization
Area optimization of floorplan designs

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design

November 2008

855 pages

ISBN:9781424428205

General Chair:
Sani R. Nassif
IBM Austin Research Lab, Austin Texas
,
Program Chair:
Jaijeet Roychowdhury
Univ. of Minnesota, Minneapolis, MN

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE Council on Electronic Design Automation (CEDA)
IEEE CASS/CANDE

Publisher

IEEE Press

Publication History

Published: 10 November 2008

Check for updates

Qualifiers

Research-article

Conference

ASE08

Sponsor:

SIGDA

ASE08: The International Conference on Computer-Aided Design

November 10 - 13, 2008

California, San Jose

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
145
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cannon SMiracle SRandall DIndyk P(2015)Phase transitions in random dyadic tilings and rectangular dissectionsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722233(1573-1589)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722233
Tsao HChou PHuang SChang YLin MChen DLiu DPhillips JHu AGraeb H(2011)A corner stitching compliant B*-tree representation and its applications to analog placementProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132444(507-511)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132444
Wang JZhou HWakabayashi K(2009)Exploring adjacency in floorplanningProceedings of the 2009 Asia and South Pacific Design Automation Conference10.5555/1509633.1509726(367-372)Online publication date: 19-Jan-2009
https://dl.acm.org/doi/10.5555/1509633.1509726

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