Article

A study of tighter lower bounds in LP relaxation based placement

Authors:

Qingzhou (Ben) Wang,

Devang Jariwala,

John LillisAuthors Info & Claims

GLSVLSI '05: Proceedings of the 15th ACM Great Lakes symposium on VLSI

Pages 498 - 502

https://doi.org/10.1145/1057661.1057780

Published: 17 April 2005 Publication History

Get Access

Abstract

Placement strategies for cell-based designs which use a linear programming (LP) relaxation are widely believed to have certain weaknesses. Among these is the phenomenon that the relaxed placement produced by the LP-solver often has excessive cell overlap; this makes the relaxed solution quite distant from a legal one and raises questions about the value of the relaxed solution. An implication of this phenomenon is that, while the objective function value (HPWL) yielded by the LP is a valid lower bound on the achievable wire-length, it is quite distant from known upper bounds produced by quality placement tools - i.e., the lower bounds appear to be loose. In this paper we experiment with some straightforward generalizations of the basic LP-formulation aimed at tightening the lower bound. We show that this approach has an interesting dual effect: in addition to tightening lower bounds, it also results in a quantifiably better cell distribution than the simpler LP-formulation. Based on this idea, we have developed a placer which employs the Relaxation Based Local Search framework. Experimental results are reported for PEKO and MCNC FPGA benchmarks.

References

[1]

C.-C. Chang, J. Cong, M. Romesis, and M. Xie. Optimality and scalability study of existing placement algorithms. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 23(4):537--549, 2004.

Digital Library

Google Scholar

[2]

H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In Proceedings of the 35th annual conference on Design automation, pages 269--274, 1998.

Digital Library

Google Scholar

[3]

S.-W. Hur and J. Lillis. Relaxation and clustering in a local search framework: application to linear placement. In Proceedings of the 36th ACM/IEEE conference on Design automation, pages 360--366, 1999.

Digital Library

Google Scholar

[4]

S. W. Hur and J. Lillis. Mongrel: hybrid techniques for standard cell placement. In Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, pages 165--170, 2000.

Digital Library

Google Scholar

[5]

M. A. B. Jackson and E. S. Kuh. Performance-driven placement of cell based ic's. In Proceedings of the 26th ACM/IEEE conference on Design automation, pages 370--375, 1989.

Digital Library

Google Scholar

[6]

J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. Gordian: Vlsi placement by quadratic programming and slicing optimization. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 10(3):356--365, 1991.

Google Scholar

[7]

A. Marquardt, V. Betz, and J. Rose. Timing-driven placement for fpgas. In Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, pages 203--213, 2000.

Digital Library

Google Scholar

[8]

http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html.

Google Scholar

[9]

http://www.ilog.com/products/cplex/.

Google Scholar

Cited By

View all

Li XLillis J(2009)A Method for improved final placement employing branch-and-bound with hierarchical placement encoding and tightened bounds2009 1st Asia Symposium on Quality Electronic Design10.1109/ASQED.2009.5206249(304-312)Online publication date: Jul-2009
https://doi.org/10.1109/ASQED.2009.5206249
Li CKoh C(2007)Recursive Function Smoothing of Half-Perimeter Wirelength for Analytical PlacementProceedings of the 8th International Symposium on Quality Electronic Design10.1109/ISQED.2007.133(829-834)Online publication date: 26-Mar-2007
https://dl.acm.org/doi/10.1109/ISQED.2007.133
Cong JRomesis MShinnerl JSze KXie M(2007)Locality and Utilization in Placement SuboptimalityModern Circuit Placement10.1007/978-0-387-68739-1_2(13-36)Online publication date: 2007
https://doi.org/10.1007/978-0-387-68739-1_2
Show More Cited By

Index Terms

A study of tighter lower bounds in LP relaxation based placement
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

An LP-based methodology for improved timing-driven placement
ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference

A method for timing driven placement is presented. The core of the approach is optimal timing-driven relaxed placement based on a linear programming (LP) formulation. The formulation captures all topological paths in a linear sized LP and thus, ...
Asynchronous circuit placement by lagrangian relaxation
ICCAD '14: Proceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design

Recent asynchronous VLSI circuit placement approach tries to leverage synchronous placement tools as much as possible by manual loop-breaking and creation of virtual clocks. However, this approach produces an exponential number of explicit timing ...
On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems
Approximation and online algorithms

Enumerative approaches to solving optimization problems, such as branch and bound, require a subroutine that produces a lower bound on the value of the optimal solution. In the domain of scheduling problems the requisite lower bound has typically been ...

Comments

Information & Contributors

Information

Published In

GLSVLSI '05: Proceedings of the 15th ACM Great Lakes symposium on VLSI

April 2005

518 pages

ISBN:1595930574

DOI:10.1145/1057661

General Chair:
John Lach
University of Virginia
,
Program Chairs:
Gang Qu
University of Maryland, College Park
,
Yehea Ismail
Northwestern University

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: 17 April 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

GLSVLSI05

Sponsor:

GLSVLSI05: Great Lakes Symposium on VLSI 2005

April 17 - 19, 2005

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25

Sponsor:
sigda

Great Lakes Symposium on VLSI 2025

June 30 - July 2, 2025

New Orleans , LA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
240
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li XLillis J(2009)A Method for improved final placement employing branch-and-bound with hierarchical placement encoding and tightened bounds2009 1st Asia Symposium on Quality Electronic Design10.1109/ASQED.2009.5206249(304-312)Online publication date: Jul-2009
https://doi.org/10.1109/ASQED.2009.5206249
Li CKoh C(2007)Recursive Function Smoothing of Half-Perimeter Wirelength for Analytical PlacementProceedings of the 8th International Symposium on Quality Electronic Design10.1109/ISQED.2007.133(829-834)Online publication date: 26-Mar-2007
https://dl.acm.org/doi/10.1109/ISQED.2007.133
Cong JRomesis MShinnerl JSze KXie M(2007)Locality and Utilization in Placement SuboptimalityModern Circuit Placement10.1007/978-0-387-68739-1_2(13-36)Online publication date: 2007
https://doi.org/10.1007/978-0-387-68739-1_2
Kahng AReda SHutton MDambre J(2006)A tale of two netsProceedings of the 2006 international workshop on System-level interconnect prediction10.1145/1117278.1117282(17-24)Online publication date: 4-Mar-2006
https://dl.acm.org/doi/10.1145/1117278.1117282

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

An LP-based methodology for improved timing-driven placement

Asynchronous circuit placement by lagrangian relaxation

On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations