Article

Free access

Floorplan area minimization using Lagrangian relaxation

Authors:

F. Y. Young,

Chris C. N. Chu,

W. S. Luk,

Y. C. WongAuthors Info & Claims

ISPD '00: Proceedings of the 2000 international symposium on Physical design

Pages 174 - 179

https://doi.org/10.1145/332357.332396

Published: 01 May 2000 Publication History

PDF eReader

References

[1]

M. Kang and W. W.M. Dai. General Floorplanning with L-shaped, T-shaped and Soft Blocks Based on Bounded Slicing Grid Structure. IEEE Asia and South Pacific Design Automation Conference, pages 265-270, 1997.

Google Scholar

[2]

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.

Crossref

Google Scholar

[3]

M.S. Bazaraa and H.D. Sherali and C.M. Sherry. Nonlinear Programming: Theory and Algorithms. John Wiley & Sons, Inc., second edition, 1997.

Google Scholar

[4]

H. Murata and Ernest S. Kuh. Sequence-Pair Based Placement Method for Hard/Soft/Pre-placed Modules. International Symposium on Physical Design, pages 167-172, 1998.

Digital Library

Google Scholar

[5]

S. Nakatake, K. Fujiyoushi, H. Murata, and Y. Kajitani. Module Placement on BSG-Structure and I C Layout Applications. Proceedings IEEE International Conference on Computer-Aided Design, pages 484-491, 1996.

Digital Library

Google Scholar

[6]

Peichen Pan and C.L. Liu. Area Minimization for General Floorplans. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 606-609, 1992.

Digital Library

Google Scholar

[7]

L. Stockmeyer. Optimal Orientations of Cells in Slicing Floorplan Designs. Information and Control, 59:91-101, 1983.

Digital Library

Google Scholar

[8]

Ting-Chi Wang and D.F. Wong. An Optimal Algorithm for Floorplan Area Optimization. Proceedings of the A CM/IEEE Design Automation Conference, pages 180-186, 1990.

Digital Library

Google Scholar

[9]

Ting-Chi Wang and D.F. Wong. Optimal Floorplan Area Optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2(8):992-1001, 1992.

Google Scholar

[10]

D.F. Wong and C.L. Liu. A New Algorithm for Floorplan Design. Proceedings of the 23rd A CM/IEEE Design Automation Conference, pages 101-107, 1986.

Digital Library

Google Scholar

Cited By

View all

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
Balasa FMohamed S(2017)WIP: Optimization algorithms: A key component of EDA education2017 IEEE International Conference on Microelectronic Systems Education (MSE)10.1109/MSE.2017.7945083(45-46)Online publication date: May-2017
https://doi.org/10.1109/MSE.2017.7945083
Lee HChang YYang H(2007)MB∗-TreeIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2007.89136826:8(1430-1444)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1109/TCAD.2007.891368
Show More Cited By

Floorplan area minimization using Lagrangian relaxation
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Floorplan area minimization using Lagrangian relaxation
ICCAD '00: Proceedings of the 2000 international conference on Computer-aided design

Floorplan area minimization is an important problem because many modules have shape flexibilities during the floorplanning stage. Area minimization in general non-slicing floorplan is a complicated problem. Many previous works have attempted to tackle ...
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 ...
A revisit to floorplan optimization by Lagrangian relaxation
ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISPD '00: Proceedings of the 2000 international symposium on Physical design

May 2000

215 pages

ISBN:1581131917

DOI:10.1145/332357

Chairmen:
Manfred Wiesel,
Dwight Hill
Synopsys, Mountain View, CA

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

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISPD00

Sponsor:

SIGDA

ISPD00: International Symposium on Physical Design 2000

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
533
Total Downloads

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

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Balasa FMohamed S(2017)WIP: Optimization algorithms: A key component of EDA education2017 IEEE International Conference on Microelectronic Systems Education (MSE)10.1109/MSE.2017.7945083(45-46)Online publication date: May-2017
https://doi.org/10.1109/MSE.2017.7945083
Lee HChang YYang H(2007)MB∗-TreeIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2007.89136826:8(1430-1444)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1109/TCAD.2007.891368
Natale MBini E(2007)Optimizing the FPGA Implementation of HRT SystemsProceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium10.1109/RTAS.2007.25(22-31)Online publication date: 3-Apr-2007
https://dl.acm.org/doi/10.1109/RTAS.2007.25
Peyran OZeng ZZhuang W(2006)Area optimization of delay-optimized structures using intrinsic constraint graphsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2004.82812423:6(888-906)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2004.828124
Jiang IChang YJou JChao K(2006)Simultaneous floor plan and buffer-block optimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2004.82658223:5(694-703)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2004.826582
Chu CYoung E(2006)Nonrectangular shaping and sizing of soft modules for floorplan-design improvementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2003.81989623:1(71-79)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2003.819896
Chiu-Wing Sham Young E(2004)Area reduction on interconnect optimized floorplan using deadspace utilizationThe 2004 47th Midwest Symposium on Circuits and Systems, 2004. MWSCAS '04.10.1109/MWSCAS.2004.1354023(1_445-1_448)Online publication date: 2004
https://doi.org/10.1109/MWSCAS.2004.1354023
Lee HChang YHsu JYang HGetreu IFix LLavagno L(2003)Multilevel floorplanning/placement for large-scale modules using B*-treesProceedings of the 40th annual Design Automation Conference10.1145/775832.776037(812-817)Online publication date: 2-Jun-2003
https://dl.acm.org/doi/10.1145/775832.776037
Jiang IChang YJou JChao KYasuura H(2003)Simultaneous floorplanning and buffer block planningProceedings of the 2003 Asia and South Pacific Design Automation Conference10.1145/1119772.1119858(431-434)Online publication date: 21-Jan-2003
https://dl.acm.org/doi/10.1145/1119772.1119858
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Floorplan area minimization using Lagrangian relaxation

Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization

A revisit to floorplan optimization by Lagrangian relaxation