A revisit to floorplan optimization by Lagrangian relaxation

Chuan Lin*, Hai Zhou, Chris Chu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

With the advent of deep sub-micron (DSM) era, floorplanning has become increasingly important in physical design process. In this paper we clarify a misunderstanding in using Lagrangian relaxation for the minimum area floorplanning problem. We show that the problem is not convex and its optimal solution cannot be obtained by solving its Lagrangian dual problem. We then propose a modified convex formulation and solve it using min-cost flow technique and trust region method. Experimental results under module aspect ratio bound [0.5,2.0] show that the running time of our floorplanner scales well with the problem size in MCNC benchmark. Compared with the floorplanner in [27], our floorplanner is 9.5X faster for the largest case "ami49". It also generates a floorplan with smaller deadspace for almost all test cases. In addition, since the generated floorplan has an aspect ratio closer to 1, it is more friendly to packaging. Our floorplanner is also amicable to including interconnect cost and other physical design metrics.

Original languageEnglish (US)
Title of host publicationProceedings of the 2006 International Conference on Computer-Aided Design, ICCAD
Pages164-171
Number of pages8
DOIs
StatePublished - Dec 1 2006
Event2006 International Conference on Computer-Aided Design, ICCAD - San Jose, CA, United States
Duration: Nov 5 2006Nov 9 2006

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Other

Other2006 International Conference on Computer-Aided Design, ICCAD
CountryUnited States
CitySan Jose, CA
Period11/5/0611/9/06

Keywords

  • Floorplan
  • Lagrangian relaxation

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'A revisit to floorplan optimization by Lagrangian relaxation'. Together they form a unique fingerprint.

  • Cite this

    Lin, C., Zhou, H., & Chu, C. (2006). A revisit to floorplan optimization by Lagrangian relaxation. In Proceedings of the 2006 International Conference on Computer-Aided Design, ICCAD (pp. 164-171). [4110169] (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). https://doi.org/10.1109/ICCAD.2006.320081