Article

A revisit to floorplan optimization by Lagrangian relaxation

Authors:

Chris ChuAuthors Info & Claims

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

Pages 164 - 171

https://doi.org/10.1145/1233501.1233535

Published: 05 November 2006 Publication History

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 flooplanner 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.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Application. Prentice Hall, 1993.

Digital Library

[2]

M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear programming: theory and algorithms. John Wiley & Sons, Inc., second edition, 1997.

[3]

S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004.

Digital Library

[4]

Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu. B*-trees: A new representation for non-slicing floorplans. In DAC, pages 458--463, 2000.

Digital Library

[5]

C.-P. Chen, C. C. N. Chu, and D. F. Wong. Fast and exact simultaneous gate and wire sizing by lagrangian relaxation. IEEE TCAD, 18(7):1014--1025, July 1999.

Digital Library

[6]

T.-C. Chen and Y.-W. Chang. Modern floorplanning based on fast simulated annealing. In ISPD, pages 104--112, 2005.

Digital Library

[7]

A. V. Goldberg. An efficient implementation of a scaling minimum-cost flow algorithm. Journal of Algorithms, 22:1--29, 1997.

Digital Library

[8]

G. H. Golub and C. F. van Loan. Matrix Computations. Johns Hopkins, 3rd edition, 1996.

[9]

P.-N. Guo, C.-K. Cheng, and T. Yoshimura. An O-tree representation of non-slicing floorplan and its applications. In DAC, pages 268--273, 1999.

Digital Library

[10]

X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu. Corner block list: An effective and efficient topological representation of non-slicing floorplan. In ICCAD, pages 8--12, 2000.

Digital Library

[11]

M. Kang and W. W. M. Dai. General floorplanning with l-shaped, t-shaped and soft blocks based on bounded slicing grid structure. In ASP-DAC, pages 265--270, 1997.

[12]

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

Digital Library

[13]

D. G. Luenberger. Linear and nonlinear programming. Addison-Wesley, Reading, Massachusetts, 1984.

[14]

T.-S. Moh, T.-S. Chang, and S. L. Hakimi. Globally optimal floorplanning for a layout problem. IEEE Transaction on Circuit and Systems - I: Fundamental Theory and Applications, 43(9):713--720, 1996.

[15]

H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. Rectangle-packing based module placement. In ICCAD, pages 472--479, 1995.

Digital Library

[16]

H. Murata and E. S. Kuh. Sequence-pair based placement method for hard/soft/pre-placed modules. In ISPD, pages 167--172, 1998.

Digital Library

[17]

S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani. Module placement on BSG-structure and IC layout applications. In ICCAD, pages 484--493, 1996.

Digital Library

[18]

J. Nocedal and S. J. Wright. Numerical optimization. Springer Series in Operations Research, Springer Verlag, 1999.

[19]

R. H. J. M. Otten. Automatic floorplan design. In DAC, pages 261--267, 1982.

Digital Library

[20]

P. Pan and C. L. Liu. Area minimization for floorplans. IEEE TCAD, 14(1):123--132, January 1995.

Digital Library

[21]

K. Sakanushi and Y. Kajitani. The quarter-state sequence (qsequence) to represent the floorplan and applications to layout optimization. In IEEE APCCAS, pages 829--832, 2000.

[22]

L. Stockmeyer. Optimal orientations of cells in slicing floorplan designs. Information and Control, 59:91--101, 1983.

Digital Library

[23]

T.-C. Wang and D. F Wong. An optimal algorithm for floorplan area optimization. In DAC, pages 180--186, 1990.

Digital Library

[24]

T.-C. Wang and D. F. Wong. Optimal floorplan area optimization. IEEE TCAD, 2(8):992--1001, 1992.

[25]

D. F. Wong and C. L. Liu. A new algorithm for floorplan design. In DAC, pages 101--107, 1986.

Digital Library

[26]

B. Yao, H. Chen, C. K. Cheng, and R. Graham. Revisiting floorplan representation. In ISPD, pages 138--143, 2001.

Digital Library

[27]

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, 20(5):687--692, May 2001.

Digital Library

[28]

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, 22(4):457--469, April 2003.

Digital Library

[29]

H. Zhou and J. Wang. Acg-adjacent constraint graph for general floorplans. In ICCD, pages 572--575, 2004.

Digital Library

Cited By

Pui CYoung E(2020)Lagrangian Relaxation-Based Time-Division Multiplexing Optimization for Multi-FPGA SystemsACM Transactions on Design Automation of Electronic Systems10.1145/337755125:2(1-23)Online publication date: 3-Feb-2020
https://dl.acm.org/doi/10.1145/3377551
Wang RShah NHu JKoh C(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
https://dl.acm.org/doi/10.1145/2160916.2160957
Yan JChu CHu JKoh C(2012)Optimal slack-driven block shaping algorithm in fixed-outline floorplanningProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160956(179-186)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160956
Show More Cited By

Index Terms

A revisit to floorplan optimization by Lagrangian relaxation
1. Applied computing
  1. Physical sciences and engineering
    1. Engineering
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

An enhanced congestion-driven floorplanner

In this paper, a rectilinear-based congestion-driven floorplanning algorithm is presented to enhance the wire congestion and the CPU runtime. The proposed algorithm contains two stages, including the simulated-annealing (SA) based approach with the ...
Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization

Optimization problems whose objective function and constraints are quadratic polynomials are called quadratically constrained quadratic programs (QCQPs). QCQPs are NP-hard in general and are important in optimization theory and practice. There have been ...
Floorplan and placement algorithms in very large scale integrated (VLSI) circuit designs

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2006

147 pages

ISBN:1595933891

DOI:10.1145/1233501

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

Copyright © 2006 ACM.

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]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

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

6
Total Citations
View Citations
263
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pui CYoung E(2020)Lagrangian Relaxation-Based Time-Division Multiplexing Optimization for Multi-FPGA SystemsACM Transactions on Design Automation of Electronic Systems10.1145/337755125:2(1-23)Online publication date: 3-Feb-2020
https://dl.acm.org/doi/10.1145/3377551
Wang RShah NHu JKoh C(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
https://dl.acm.org/doi/10.1145/2160916.2160957
Yan JChu CHu JKoh C(2012)Optimal slack-driven block shaping algorithm in fixed-outline floorplanningProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160956(179-186)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160956
Lu YZhou HShang LZeng X(2009)Multicore parallel min-cost flow algorithm for CAD applicationsProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1630124(832-837)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1629911.1630124
He ODong SBian JGoto SCheng CNassif SRoychowdhury J(2008)A novel fixed-outline floorplanner with zero deadspace for hierarchical designProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509473(16-23)Online publication date: 10-Nov-2008
https://dl.acm.org/doi/10.5555/1509456.1509473
Wang JZhou HNassif SRoychowdhury J(2008)Linear constraint graph for floorplan optimization with soft blocksProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509472(9-15)Online publication date: 10-Nov-2008
https://dl.acm.org/doi/10.5555/1509456.1509472

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