skip to main content
research-article

Constraint-driven floorplan repair

Published: 03 October 2008 Publication History

Abstract

In this work, we propose a new and efficient approach to the floorplan repair problem, where violated design constraints are satisfied by applying small changes to an existing rough floorplan. Such a floorplan can be produced by a human designer, a scalable placement algorithm, or result from engineering adjustments to an existing floorplan. In such cases, overlapping modules must be separated, and others may need to be repositioned to satisfy additional requirements. Our algorithmic framework uses an expressive graph-based encoding of constraints which can reflect fixed-outline, region, proximity and alignment constraints. By tracking the implications of existing constraints, we resolve violations by imposing gradual modifications to the floorplan, in an attempt to preserve the characteristics of its initial design. Empirically, our approach is effective at removing overlaps and repairing violations that may occur when design constraints are acquired and imposed dynamically.

References

[1]
Adya, S. N. and Markov, I. L. 2003. Fixed-outline floorplanning: Enabling hierarchical Design. In IEEE Trans. VLSI Syst. 11, 6, 1120--1135.
[2]
Brenner, U., Pauli, A., and Vygen, J. 2004. Almost optimum placement legalization by minimum cost flow and dynamic programming. In Proceedings of the 2004 International Symposium on Physical Design (Phoenix, AZ). ACM, New York. 2--9.
[3]
Chang, C., Cong, J., and Yuan, X. 2003. Multi-level placement for large-scale mixed-size IC designs. In Proceedings of ASP-DAC, 325--330.
[4]
Cong, J., Romesis, M., and Shinnerl, J. R. 2005a. Fast floorplanning by look-ahead enabled recursive bipartitioning. In Proceedings of ASP-DAC, pp. 1119--1122.
[5]
Cong, J., Romesis, M., and Shinnerl, J. R. 2005b. Robust mixed-size placement under tight white-space constraints. In Proceedings of ICCAD, pp. 165--172.
[6]
Cong, J. and Xie, M. 2006. A robust detailed placement for mixed-size IC designs. In Proceedings of ASP-DAC, pp. 188--194.
[7]
Kahng, A. B., Reda, S., and Wang, Q. 2005. Architecture and details of a high quality, large-scale analytical placer. In Proceedings of ICCAD, pp. 891--898.
[8]
Khatkhate, A., Li, C., Agnihotri, A. R., Yildiz, M. C., Ono, S., Koh, C.-K., and Madden, P. H. 2004. Recursive bisection-based mixed block placement. In Proceedings of the 2004 International Symposium on Physical Design (Phoenix, AZ). ACM, New York, 84--89.
[9]
Moffitt, M. D., Ng, A. N., Markov, I. L., and Pollack, M. E. 2006. Constraint-driven floorplan repair. In Proceedings of DAC, pp. 1103--1108.
[10]
Moffitt, M. D., and Pollack., M. E. 2006. Optimal rectangle packing: a meta-CSP approach. In Proceedings of ICAPS, pp. 93--102.
[11]
Nag, S. and Chaudhary, K. 1999. Post-placement residual-overlap removal with minimal movement. In Proceedings of DATE, pp. 581--586.
[12]
Ren, H., Pan, D. Z. Alpert, C. J., and Villarrubia, P. 2005. Diffusion-based placement migration. In Proceedings of DAC, pp. 515--520.
[13]
Roy, J. A., Adya, S. N., Papa, D. A., and Markov., I. L. 2006. Min-cut floorplacement. In IEEE Trans. CAD 25, 7, 1313--1326.
[14]
Yao, B., Chen, H., Cheng, C.-K., and Graham, R. 2003. Floorplan representations: Complexity and connections. In ACM Trans. Des. Automat. Elect. Syst. 8, 1, 55--80.
[15]
Young, E., Ho, M. L., and Chu, C. 2002. A unified method to handle different kinds of placement constraints in floorplan design. In Proceedings of ASP-DAC, pp. 661--670.

Cited By

View all
  • (2015)Progress and Challenges in VLSI Placement ResearchProceedings of the IEEE10.1109/JPROC.2015.2478963103:11(1985-2003)Online publication date: Nov-2015
  • (2014)Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of BitsSIAM Journal on Computing10.1137/12087914243:2(477-496)Online publication date: Jan-2014
  • (2013)Fully Dynamic Evaluation of Sequence PairIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2013.224464232:6(894-904)Online publication date: 1-Jun-2013
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems
ACM Transactions on Design Automation of Electronic Systems  Volume 13, Issue 4
September 2008
328 pages
ISSN:1084-4309
EISSN:1557-7309
DOI:10.1145/1391962
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: 03 October 2008
Accepted: 01 May 2008
Revised: 01 June 2007
Received: 01 December 2006
Published in TODAES Volume 13, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Floorplanning
  2. constraints
  3. legalization

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2015)Progress and Challenges in VLSI Placement ResearchProceedings of the IEEE10.1109/JPROC.2015.2478963103:11(1985-2003)Online publication date: Nov-2015
  • (2014)Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of BitsSIAM Journal on Computing10.1137/12087914243:2(477-496)Online publication date: Jan-2014
  • (2013)Fully Dynamic Evaluation of Sequence PairIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2013.224464232:6(894-904)Online publication date: 1-Jun-2013
  • (2012)Progress and challenges in VLSI placement researchProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429441(275-282)Online publication date: 5-Nov-2012
  • (2012)Scalable hierarchical floorplanning for fast physical prototyping of systems-on-chipProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160957(187-192)Online publication date: 25-Mar-2012
  • (2012)Assembling 2-D Blocks Into 3-D ChipsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2011.217464031:2(228-241)Online publication date: 1-Feb-2012
  • (2012)Nutzung von klassischen IP-Blöcken in 3D-SchaltkreisenEntwurf integrierter 3D-Systeme der Elektronik10.1007/978-3-642-30572-6_9(145-174)Online publication date: 12-Sep-2012
  • (2011)Assembling 2D blocks into 3D chipsProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960417(81-88)Online publication date: 27-Mar-2011
  • (2011)Chip PlanningVLSI Physical Design: From Graph Partitioning to Timing Closure10.1007/978-90-481-9591-6_3(55-92)Online publication date: 27-Jan-2011

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