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

research-article

Ripple 2.0: high quality routability-driven placement via global router integration

Authors:

Evangeline F. Y. YoungAuthors Info & Claims

DAC '13: Proceedings of the 50th Annual Design Automation Conference

Article No.: 152, Pages 1 - 6

https://doi.org/10.1145/2463209.2488922

Published: 29 May 2013 Publication History

Abstract

Due to a significant mismatch between the objectives of wirelength and routing congestion, the routability issue is becoming more and more important in VLSI design. In this paper, we present a high quality placer Ripple 2.0 to solve the routability-driven placement problem. We will study how to make use of the routing path information in cell spreading and relieve congestion with tangled logic in detail. Several techniques are proposed, including (1) lookahead routing analysis with pin density consideration, (2) routing path-based cell inflation and spreading and (3) robust optimization on congested cluster. With the official evaluation protocol, Ripple 2.0 outperforms the top contestants on the ICCAD 2012 Contest benchmark suite.

References

[1]

C. Alpert, Z. Li, M. Moffitt, G. Nam, J. Roy, and G. Tellez, "What makes a design difficult to route," in ISPD, pp. 7--12, ACM, 2010.

Digital Library

[2]

J. Roy and I. Markov, "Seeing the forest and the trees: Steiner wirelength optimization in placement," TCAD, vol. 26, no. 4, pp. 632--644, 2007.

Digital Library

[3]

N. Viswanathan and et al, "The ispd-2011 routability-driven placement contest and benchmark suite," in ISPD, pp. 141--146, ACM, 2011.

Digital Library

[4]

H. Shojaei, A. Davoodi, and J. Linderoth, "Congestion analysis for global routing via integer programming," in ICCAD, pp. 256--262, IEEE, 2010.

Digital Library

[5]

Y. Wei and et al, "Glare: Global and local wiring aware routability evaluation," in DAC, pp. 768--773, ACM, 2012.

Digital Library

[6]

K. Tsota, C. Koh, and V. Balakrishnan, "Guiding global placement with wire density," in ICCAD, pp. 212--217, IEEE, 2008.

Digital Library

[7]

A. Kahng and Q. Wang, "Implementation and extensibility of an analytic placer," TCAD, vol. 24, no. 5, pp. 734--747, 2005.

Digital Library

[8]

Z. Jiang and et al, "Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs," in DAC, pp. 167--172, 2008.

Digital Library

[9]

Y. Chuang and et al, "Design-hierarchy aware mixed-size placement for routability optimization," in ICCAD, pp. 663--668, IEEE, 2010.

Digital Library

[10]

P. Spindler and F. Johannes, "Fast and accurate routing demand estimation for efficient routability-driven placement," in DATE, pp. 1--6, IEEE, 2007.

Digital Library

[11]

X. He, T. Huang, L. Xiao, H. Tian, G. Cui, and E. Young, "Ripple: An effective routability-driven placer by iterative cell movement," in ICCAD, pp. 74--79, 2011.

Digital Library

[12]

M. Kim, J. Hu, D. Lee, and I. Markov, "A simplr method for routability-driven placement," in ICCAD, pp. 67--73, IEEE Press, 2011.

Digital Library

[13]

X. Yang, B. Choi, and M. Sarrafizadeh, "Routability-driven white space allocation for fixed-die standard-cell placement," TCAD, vol. 22, no. 4, pp. 410--419, 2003.

Digital Library

[14]

C. Li, M. Xie, C. Koh, J. Cong, and P. Madden, "Routability-driven placement and white space allocation," TCAD, vol. 26, no. 5, pp. 858--871, 2007.

Digital Library

[15]

U. Brenner and A. Rohe, "An effective congestion-driven placement framework," TCAD, vol. 22, no. 4, pp. 387--394, 2003.

Digital Library

[16]

J. Roy and et al, "CRISP: congestion reduction by iterated spreading during placement," in ICCAD, pp. 357--362, ACM, 2009.

Digital Library

[17]

W. Hou and et al, "A new congestion-driven placement algorithm based on cell inflation," in ASP-DAC, pp. 605--608, IEEE, 2001.

Digital Library

[18]

M. Pan and C. Chu, "Ipr: an integrated placement and routing algorithm," in DAC, pp. 59--62, 2007.

Digital Library

[19]

M. Pan and C. Chu, "Fastroute: A step to integrate global routing into placement," in ICCAD, pp. 464--471, ACM, 2006.

Digital Library

[20]

J. Hu and et al, "Completing high-quality global routes," in ISPD, pp. 35--41,2010.

Digital Library

[21]

M. Hsu, S. Chou, T. Lin, and Y. Chang, "Routability-driven analytical placement for mixed-size circuit designs," in ICCAD, pp. 80--84, IEEE, 2011.

Digital Library

[22]

Y. Zhang and C. Chu, "Crop: Fast and effective congestion refinement of placement," in ICCAD, pp. 344--350, IEEE, 2009.

Digital Library

[23]

T. Jindal and et al, "Detecting tangled logic structures in vlsi netlists," in Design Automation Conference (DAC), 2010 47th ACM/IEEE, pp. 603--608, IEEE, 2010.

Digital Library

[24]

P. Spindler and et al, "Kraftwerk2: A fast force-directed quadratic placement approach using an accurate net model," TCAD, 27(8), pp. 1398--1411, 2008.

Digital Library

[25]

M. Kim, D. Lee, and I. Markov, "simpl: an effective placement algorithm," TCAD, vol. 31, no. 1, pp. 50--60, 2012.

Digital Library

[26]

M. Pan, N. Vishwanathan, and C. Chu, "An efficient and effective detailed placement algorithm," in ICCAD, pp. 48--55, IEEE Computer Society, 2005.

Digital Library

[27]

X. He, W.-K. Chow, and E. F. Young, "Srp: Simultaneous routing and placement for congestion refinement," in ISDP, ACM, March, 2013.

Digital Library

[28]

G. Nam and J. Cong, Modern circuit placement: best practices and results. Springer Publishing Company, Incorporated, 2007.

Digital Library

[29]

W. Liu, W. Kao, Y. Li, and K. Chao, "Multi-threaded collision-aware global routing with bounded-length maze routing," in DAC, pp. 200--205, ACM, 2010.

Digital Library

[30]

N. Viswanathan and et al, "Iccad-2012 cad contest in design hierarchy aware routability-driven placement and benchmark suite," in ICCAD, pp. 345--348, 2012.

Digital Library

Cited By

Kim HKim TThapliyal HDeMara RPartin-Vaisband IKatkoori S(2023)Placement Legalization Amenable to Mixed-cell-height Standard Cells Integrating into State-of-the-art Commercial EDA ToolProceedings of the Great Lakes Symposium on VLSI 202310.1145/3583781.3590278(321-326)Online publication date: 5-Jun-2023
https://dl.acm.org/doi/10.1145/3583781.3590278
Hyun DKoh SJung YKim TShin Y(2023)Routability Optimization of Extreme Aspect Ratio Design through Non-uniform Placement Utilization and Selective Flip-flop StackingACM Transactions on Design Automation of Electronic Systems10.1145/357338728:4(1-19)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3573387
Chai ZZhao YLiu WLin YWang RHuang R(2023)CircuitNet: An Open-Source Dataset for Machine Learning in VLSI CAD Applications With Improved Domain-Specific Evaluation Metric and Learning StrategiesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.328797042:12(5034-5047)Online publication date: Dec-2023
https://doi.org/10.1109/TCAD.2023.3287970
Show More Cited By

Index Terms

Ripple 2.0: high quality routability-driven placement via global router integration
1. Hardware

Recommendations

Ripple 2.0: Improved Movement of Cells in Routability-Driven Placement

Routability is one of the most important problems in high-performance circuit designs. From the viewpoint of placement design, two major factors cause routing congestion: (i) interconnections between cells and (ii) connections on macro blockages. In ...
Ripple: A Robust and Effective Routability-Driven Placer

The significant mismatch between the objective of wirelength and routing congestion makes the routability issue even more important in placement. In this paper, we describe a routability-driven placer called Ripple. Each step, including global placement,...
FastPlace 2.0: an efficient analytical placer for mixed-mode designs
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

In this paper, we present FastPlace 2.0 - an extension to the efficient analytical standard-cell placer - FastPlace [15], to address the mixed-mode placement problem. The main contributions of our work are: (1) Extensions to the global placement ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '13: Proceedings of the 50th Annual Design Automation Conference

May 2013

1285 pages

ISBN:9781450320719

DOI:10.1145/2463209

Copyright © 2013 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

EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CEDA

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

DAC '13

Sponsor:

EDAC
SIGDA

DAC '13: The 50th Annual Design Automation Conference 2013

May 29 - June 7, 2013

Texas, Austin

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
406
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim HKim TThapliyal HDeMara RPartin-Vaisband IKatkoori S(2023)Placement Legalization Amenable to Mixed-cell-height Standard Cells Integrating into State-of-the-art Commercial EDA ToolProceedings of the Great Lakes Symposium on VLSI 202310.1145/3583781.3590278(321-326)Online publication date: 5-Jun-2023
https://dl.acm.org/doi/10.1145/3583781.3590278
Hyun DKoh SJung YKim TShin Y(2023)Routability Optimization of Extreme Aspect Ratio Design through Non-uniform Placement Utilization and Selective Flip-flop StackingACM Transactions on Design Automation of Electronic Systems10.1145/357338728:4(1-19)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3573387
Chai ZZhao YLiu WLin YWang RHuang R(2023)CircuitNet: An Open-Source Dataset for Machine Learning in VLSI CAD Applications With Improved Domain-Specific Evaluation Metric and Learning StrategiesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.328797042:12(5034-5047)Online publication date: Dec-2023
https://doi.org/10.1109/TCAD.2023.3287970
Liu SPu YLiao PWu HZhang RChen ZLv WLin YYu B(2023)FastGR: Global Routing on CPU–GPU With Heterogeneous Task Graph SchedulerIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.321766842:7(2317-2330)Online publication date: Jul-2023
https://doi.org/10.1109/TCAD.2022.3217668
Chen JKuang JZhao GHuang DYoung E(2023)PROS 2.0: A Plug-In for Routability Optimization and Routed Wirelength Estimation Using Deep LearningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.316825942:1(164-177)Online publication date: Jan-2023
https://doi.org/10.1109/TCAD.2022.3168259
Jiang XGuo ZChai ZZhao YLin YWang RHuang R(2023)Invited Paper: Accelerating Routability and Timing Optimization with Open-Source AI4EDA Dataset CircuitNet and Heterogeneous Platforms2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323938(1-9)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323938
Zheng SZou LXu PLiu SYu BWong M(2023)Lay-Net: Grafting Netlist Knowledge on Layout-Based Congestion Prediction2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323800(1-9)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323800
Liu JYoung E(2023)EDGE: Efficient DAG-based Global Routing Engine2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247702(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247702
Qiu YXing YCai SLi XXiong X(2023)Lutplace: An Improved Lookup Table-Based Placement for Routability2023 China Semiconductor Technology International Conference (CSTIC)10.1109/CSTIC58779.2023.10219242(1-3)Online publication date: 26-Jun-2023
https://doi.org/10.1109/CSTIC58779.2023.10219242
Liu SLiao PZhang RChen ZLv WLin YYu BBolchini CO'Connor IVerbauwhede IWille R(2022)FastGRProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3540028(760-765)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3540028
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents