More Web Proxy on the site http://driver.im/

article

Congestion reduction during placement with provably good approximation bound

Authors:

M. SarrafzadehAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 8, Issue 3

Pages 316 - 333

https://doi.org/10.1145/785411.785414

Published: 01 July 2003 Publication History

Abstract

This paper presents a novel method to reduce routing congestion during placement stage. The proposed approach is used as a post-processing step in placement. Congestion reduction is based on local improvement on the existing layout. However, the approach has a global view of the congestion over the entire design. It uses integer linear programming (ILP) to formulate the problem of conflicts between multiple congested regions, and performs local improvement according to the solution of the ILP problem. The approximation algorithm of the formulated ILP problem is studied and good approximation bounds are given and proved. Experiments show that the proposed approach can effectively alleviate the congestion of global routing results. The low computational complexity of the proposed approach indicates its scalability on large designs.

References

[1]

Cheng, C. E. 1994. "RISA: Accurate and Efficient Placement Routability Modeling". In International Conference on Computer-Aided Design, pages 690--695.

[2]

Caldwell, A. E., Kahng, A. B., and Markov, I. L. 2000. "Can Recursive Bisection Alone Produce Routable Placements?" In Design Automation Conference, pages 477--482.

[3]

Cong, J. and Madden, P. 1998. "Performance Driven Multi-Layer General Area Routing for PCB/MCM Designs." In Design Automation Conference, pages 356--361.

[4]

Dunlop, A. E. and Kernighan, B. W. 1985. "A Procedure for Placement of Standard Cell VLSI Circuits." IEEE Trans. Comput. Aided Design, 4, 1, 92--98.

[5]

ERLAB(a). "IBM-PLACE benchmark." http://er.cs.ucla.edu/benchmarks/ibm-place/.

[6]

ERLAB(b). "Labyrinth." http://www.cs.ucla.edu/&tilde;kastner/labyrinth/.

[7]

Kahng, A. B., Mantik, S., and Stroobandt, D. 2000. "Requirements for Models of Achievable Routing." In International Symposium on Physical Des. pages 4--11.

[8]

Kleinhans, J. M., Sigl, G., Johannes, F. M., and Antreich, K. J. "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization." IEEE Trans. Comput. Aided Des. 10, 3, 365--365.

[9]

Lou, J., Krishnamoorthy, S., and Sheng, H. S. 2001. "Estimating Routing Congestion using Probabilistic Analysis." In International Symposium on Physical Design, pages 112--117.

[10]

Mayrhofer, S. and Lauther, U. 1990. "Congestion-Driven Placement Using a New Multi-partitioning Heuristic." In International Conference on Computer-Aided Design, pages 332--335.

[11]

Parakh, P. N., Brown, R. B., and Sakallah, K. A. 1998. "Congestion Driven Quadratic Placement." In Design Automation Conference, pages 275--278.

[12]

Sun, W. J. and Sechen, C. 1995. "Efficient and Effective Placement for Very Large Circuits." IEEE Trans. Comput. Aided Des. 14, 3, 349--359.

[13]

Tsay, R. S. and Chang, S. C. 1992. "Early Wirability Checking and 2-D Congestion-Driven Circuit Placement." In International Conference on ASIC. pages 50--53.

[14]

Wang, M., Yang, X., Eguro, K., and Sarrafzadeh, M. 2000a. "Multi-Center Congestion Estimation and Minimization During Placement." In International Symposium on Physical Design, pages 147--152.

[15]

Wang, M., Yang, X., and Sarrafzadeh, M. 2000b. "Congestion Minimization During Top-Down Placement." IEEE Trans. Comput. Aided Des. 19, 10, 1140--1148.

[16]

Wang, M., Yang, X., and Sarrafzadeh, M. 2000c. "Dragon2000: Fast Standard-cell Placement for Large Circuits." In International Conference on Computer-Aided Design, pages 260--263.

[17]

Yang, X., Kastner, R., and Sarrafzadeh, M. 2001. "Congestion Estimation During Top-down Placement." In International Symposium on Physical Design, pages 164--169.

Cited By

Fan SZhang SLiu JCao NGuo XLi JZhang X(2022)Power Converter Circuit Design Automation Using Parallel Monte Carlo Tree SearchACM Transactions on Design Automation of Electronic Systems10.1145/354953828:2(1-33)Online publication date: 24-Dec-2022
https://dl.acm.org/doi/10.1145/3549538
Yang ZHe JLu AHou TCao D(2020)The Application of Negative Design to Design More Desirable Virtual Screening LibraryJournal of Medicinal Chemistry10.1021/acs.jmedchem.9b01476Online publication date: 13-Jan-2020
https://doi.org/10.1021/acs.jmedchem.9b01476
Bobba SChakraborty AThomas OBatude PMicheli G(2013)Cell transformations and physical design techniques for 3D monolithic integrated circuitsACM Journal on Emerging Technologies in Computing Systems10.1145/24916759:3(1-28)Online publication date: 8-Oct-2013
https://dl.acm.org/doi/10.1145/2491675
Show More Cited By

Index Terms

Congestion reduction during placement with provably good approximation bound
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Routability-Driven Blockage-Aware Macro Placement
DAC '14: Proceedings of the 51st Annual Design Automation Conference

We present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro ...
Routability-driven placement for hierarchical mixed-size circuit designs
DAC '13: Proceedings of the 50th Annual Design Automation Conference

A wirelength-driven placer without considering routability could introduce irresolvable routing-congested placements. Therefore, it is desirable to develop an effective routability-driven placer for modern mixed-size designs employing hierarchical ...
Routability driven white space allocation for fixed-die standard-cell placement
ISPD '02: Proceedings of the 2002 international symposium on Physical design

The use of white space in fixed-die standard-cell placement is an effective way to improve routability. In this paper, we present a white space allocation approach that dynamically assigns white space according to the congestion distribution of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 8, Issue 3

July 2003

127 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/785411

Issue’s Table of Contents

Copyright © 2003 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 July 2003

Published in TODAES Volume 8, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
535
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fan SZhang SLiu JCao NGuo XLi JZhang X(2022)Power Converter Circuit Design Automation Using Parallel Monte Carlo Tree SearchACM Transactions on Design Automation of Electronic Systems10.1145/354953828:2(1-33)Online publication date: 24-Dec-2022
https://dl.acm.org/doi/10.1145/3549538
Yang ZHe JLu AHou TCao D(2020)The Application of Negative Design to Design More Desirable Virtual Screening LibraryJournal of Medicinal Chemistry10.1021/acs.jmedchem.9b01476Online publication date: 13-Jan-2020
https://doi.org/10.1021/acs.jmedchem.9b01476
Bobba SChakraborty AThomas OBatude PMicheli G(2013)Cell transformations and physical design techniques for 3D monolithic integrated circuitsACM Journal on Emerging Technologies in Computing Systems10.1145/24916759:3(1-28)Online publication date: 8-Oct-2013
https://dl.acm.org/doi/10.1145/2491675
Bobba SChakraborty AThomas OBatude PErnst TFaynot OPan DDe Micheli G(2011)CELONCELProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950889(336-343)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950889
Bobba SChakraborty AThomas OBatude PErnst TFaynot OPan DDe Micheli G(2011)CELONCEL: Effective design technique for 3-D monolithic integration targeting high performance integrated circuits16th Asia and South Pacific Design Automation Conference (ASP-DAC 2011)10.1109/ASPDAC.2011.5722210(336-343)Online publication date: Jan-2011
https://doi.org/10.1109/ASPDAC.2011.5722210
Ahmadinia AAngermeier JFekete SKamphans TKoch DMajer MSchweer NTeich JTessars Cvan der Veen J(2010)ReCoNodes—Optimization Methods for Module Scheduling and Placement on Reconfigurable Hardware DevicesDynamically Reconfigurable Systems10.1007/978-90-481-3485-4_10(199-221)Online publication date: 10-Feb-2010
https://doi.org/10.1007/978-90-481-3485-4_10
Fudos IKavousianos XMarkouzis DTsiatouhas Y(2008)Placement and Routing in Computer Aided Design of Standard Cell Arrays by Exploiting the Structure of the Interconnection GraphComputer-Aided Design and Applications10.3722/cadaps.2008.325-3375:1-4(325-337)Online publication date: Jan-2008
https://doi.org/10.3722/cadaps.2008.325-337
Samanta TGhosal PRahaman HDasgupta P(2007)Minimum-Congestion Placement for Y-interconnectsProceedings of the IEEE Computer Society Annual Symposium on VLSI10.1109/ISVLSI.2007.66(73-80)Online publication date: 9-Mar-2007
https://dl.acm.org/doi/10.1109/ISVLSI.2007.66
Saeedi MZamani MJahanian A(2007)Evaluation, prediction and reduction of routing congestionMicroelectronics Journal10.1016/j.mejo.2007.07.12238:8-9(942-958)Online publication date: Aug-2007
https://doi.org/10.1016/j.mejo.2007.07.122
(2007)Congestion Optimization During PlacementRouting Congestion in VLSI Circuits: Estimation and Optimization10.1007/0-387-48550-3_5(145-188)Online publication date: 2007
https://doi.org/10.1007/0-387-48550-3_5
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents