research-article

Closing the Gap between Global and Detailed Placement: Techniques for Improving Routability

Authors:

Chuan-Chia Huang,

Sean Shih-Ying Liu,

Hung-Ming ChenAuthors Info & Claims

ISPD '15: Proceedings of the 2015 Symposium on International Symposium on Physical Design

Pages 149 - 156

https://doi.org/10.1145/2717764.2717776

Published: 29 March 2015 Publication History

Abstract

Improving routability during both global and detailed routing stage has become a critical problem in modern VLSI design. In this work, we propose a placement framework that offers a complete coverage solution in considering both global and detailed routing congestion. A placement migration strategy is proposed, which improves detailed routing congestion while preserving the placement integrity that is optimized for global routability. Using the benchmarks released from ISPD2014 Contest, practical design rules in advanced node design are considered in our placement framework. Evaluation on routability of our placement framework is conducted using commercial router provided by the 2014 ISPD Contest organizers. Experimental results show that the proposed methodologies can effectively improve placement solutions for both global and detailed router.

References

[1]

X. He, W.-K. Chow, and E. F. Young. Srp: simultaneous routing and placement for congestion refinement. In Proceedings of the International Symposium on Physical Design, pages 108--113, 2013.

Digital Library

[2]

X. He, T. Huang, W.-K. Chow, J. Kuang, K.-C. Lam, W. Cai, and E. F. Young. Ripple 2.0: High quality routability-driven placement via global router integration. In Design Automation Conference, pages 1--6. IEEE, 2013.

Digital Library

[3]

X. He, T. Huang, L. Xiao, H. Tian, G. Cui, and E. F. Young. Ripple: an effective routability-driven placer by iterative cell movement. In Proceedings of the International Conference on Computer-Aided Design, pages 74--79, 2011.

Digital Library

[4]

M.-K. Hsu, Y.-F. Chen, C.-C. Huang, T.-C. Chen, and Y.-W. Chang. Routability-driven placement for hierarchical mixed-size circuit designs. In Proceedings of the Design Automation Conference, page 151, 2013.

Digital Library

[5]

M.-K. Hsu, S. Chou, T.-H. Lin, and Y.-W. Chang. Routability-driven analytical placement for mixed-size circuit designs. In Proceedings of the International Conference on Computer-Aided Design, pages 80--84, 2011.

Digital Library

[6]

J. Hu, M.-C. Kim, and I. L. Markov. Taming the complexity of coordinated place and route. In Design Automation Conference, page 150, 2013.

Digital Library

[7]

A. Kennings, N. K. Darav, and L. Behjat. Detailed placement accounting for technology constraints. In International Conference on Very Large Scale Integration (VLSI-SoC), pages 1--6, 2014.

[8]

M.-C. Kim, J. Hu, D.-J. Lee, and I. L. Markov. A SimPLR method for routability-driven placement. In Proceedings of the International Conference on Computer-Aided Design, pages 67--73, 2011.

Digital Library

[9]

M.-C. Kim, D.-J. Lee, and I. L. Markov. SimPL: an algorithm for placing VLSI circuits. Communication of the ACM, 56(6):105--113, June 2013.

Digital Library

[10]

M.-C. Kim, N. Viswanathan, C. J. Alpert, I. L. Markov, and S. Ramji. MAPLE: Multilevel Adaptive Placement for Mixed-Size Designs. In Proceedings of the International Symposium on Physical Design, pages 193--200, 2012.

Digital Library

[11]

W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao. Multi-threaded collision-aware global routing with bounded-length maze routing. In Proceedings of the Design Automation Conference, pages 200--205, 2010.

Digital Library

[12]

W.-H. Liu, Y.-L. Li, and C.-K. Koh. A fast maze-free routing congestion estimator with hybrid unilateral monotonic routing. In Proceedings of the International Conference on Computer-Aided Design, pages 713--719, 2012.

Digital Library

[13]

T. Luo, H. Ren, C. J. Alpert, and D. Z. Pan. Computational geometry based placement migration. In Proceedings of the International Conference on Computer-Aided Design, pages 41--47, 2005.

Digital Library

[14]

H. Ren, D. Z. Pan, C. J. Alpert, and P. Villarrubia. Diffusion-Based Placement Migration. In Proceedings of the Design Automation Conference, pages 515--520, 2005.

Digital Library

[15]

J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert, and I. L. Markov. Crisp: congestion reduction by iterated spreading during placement. In Proceedings of the International Conference on Computer-Aided Design, pages 357--362, 2009.

Digital Library

[16]

P. Spindler, U. Schlichtmann, and F. M. Johannes. Abacus: fast legalization of standard cell circuits with minimal movement. In Proceedings of the International Symposium on Physical Design, pages 47--53, 2008.

Digital Library

[17]

P. Spindler, U. Schlichtmann, and F. M. Johannes. Kraftwerk2 - A Fast Force-Directed Quadratic Placement Approach Using an Accurate Net Model. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(8):1398--1411, Aug. 2008.

Digital Library

[18]

Y. Wei, C. Sze, N. Viswanathan, Z. Li, C. J. Alpert, L. Reddy, A. D. Huber, G. E. Tellez, D. Keller, and S. S. Sapatnekar. Glare: global and local wiring aware routability evaluation. In Design Automation Conference, pages 768--773, 2012.

Digital Library

[19]

V. Yutsis, I. S. Bustany, D. Chinnery, J. R. Shinnerl, and W.-H. Liu. Ispd 2014 benchmarks with sub-45nm technology rules for detailed-routing-driven placement. In Proceedings of the International Symposium on Physical Design, pages 161--168, 2014.

Digital Library

[20]

Y. Zhang and C. Chu. Crop: fast and effective congestion refinement of placement. In Proceedings of the International Conference on Computer-Aided Design, pages 344--350, 2009.

Digital Library

Cited By

Huang YLin CLiang WChen H(2021)Learning Based Placement Refinement to Reduce DRC Short Violations2021 International Symposium on VLSI Design, Automation and Test (VLSI-DAT)10.1109/VLSI-DAT52063.2021.9427321(1-4)Online publication date: 19-Apr-2021
https://doi.org/10.1109/VLSI-DAT52063.2021.9427321
Zeng WDavoodi ATopaloglu R(2020)Explainable DRC Hotspot Prediction with Random Forest and SHAP Tree Explainer2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE48585.2020.9116488(1151-1156)Online publication date: Mar-2020
https://doi.org/10.23919/DATE48585.2020.9116488
Liou SLiu SSun RChen HSwartz WLienig J(2020)Timing Driven Partition for Multi-FPGA Systems with TDM AwarenessProceedings of the 2020 International Symposium on Physical Design10.1145/3372780.3375558(111-118)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3372780.3375558
Show More Cited By

Index Terms

Closing the Gap between Global and Detailed Placement: Techniques for Improving Routability
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

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

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '15: Proceedings of the 2015 Symposium on International Symposium on Physical Design

March 2015

204 pages

ISBN:9781450333993

DOI:10.1145/2717764

General Chair:
Azadeh Davoodi
University of Wisconsin - Madison
,
Program Chair:
Evangeline Young
The Chinese University of Hong Kong

Copyright © 2015 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 the author(s) 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Ministry of Science and Technology of Taiwan

Conference

ISPD'15

Sponsor:

SIGDA

ISPD'15: International Symposium on Physical Design

March 29 - April 1, 2015

California, Monterey, USA

Acceptance Rates

ISPD '15 Paper Acceptance Rate 14 of 37 submissions, 38%;

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

21
Total Citations
View Citations
404
Total Downloads

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

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang YLin CLiang WChen H(2021)Learning Based Placement Refinement to Reduce DRC Short Violations2021 International Symposium on VLSI Design, Automation and Test (VLSI-DAT)10.1109/VLSI-DAT52063.2021.9427321(1-4)Online publication date: 19-Apr-2021
https://doi.org/10.1109/VLSI-DAT52063.2021.9427321
Zeng WDavoodi ATopaloglu R(2020)Explainable DRC Hotspot Prediction with Random Forest and SHAP Tree Explainer2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE48585.2020.9116488(1151-1156)Online publication date: Mar-2020
https://doi.org/10.23919/DATE48585.2020.9116488
Liou SLiu SSun RChen HSwartz WLienig J(2020)Timing Driven Partition for Multi-FPGA Systems with TDM AwarenessProceedings of the 2020 International Symposium on Physical Design10.1145/3372780.3375558(111-118)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3372780.3375558
Park DLee DKang IHoltz CGao SLin BCheng C(2020)Grid-based Framework for Routability Analysis and Diagnosis with Conditional Design RulesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.2977066(1-1)Online publication date: 2020
https://doi.org/10.1109/TCAD.2020.2977066
Zhu ZChen JZhu WChang Y(2020)Mixed-cell-height Legalization Considering Technology and Region ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.2976674(1-1)Online publication date: 2020
https://doi.org/10.1109/TCAD.2020.2976674
Kang IPark DHan CCheng CHu S(2018)Fast and precise routability analysis with conditional design rulesProceedings of the 20th System Level Interconnect Prediction Workshop10.1145/3225209.3225210(1-8)Online publication date: 23-Jun-2018
https://dl.acm.org/doi/10.1145/3225209.3225210
Darav NBustany IKennings AWestwick DBehjat L(2018)Eh?LegalizerACM Transactions on Design Automation of Electronic Systems10.1145/315821523:4(1-25)Online publication date: 9-May-2018
https://dl.acm.org/doi/10.1145/3158215
Chen LHuang CChang YChen H(2018)A learning-based methodology for routability prediction in placement2018 International Symposium on VLSI Design, Automation and Test (VLSI-DAT)10.1109/VLSI-DAT.2018.8373272(1-4)Online publication date: Apr-2018
https://doi.org/10.1109/VLSI-DAT.2018.8373272
Huang CLee HLin BYang SChang CChen SChang YChen TBustany I(2018)NTUplace4dr: A Detailed-Routing-Driven Placer for Mixed-Size Circuit Designs With Technology and Region ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.271266537:3(669-681)Online publication date: Mar-2018
https://doi.org/10.1109/TCAD.2017.2712665
Datta PMukherjee S(2018)GPSAT: A SAT based Global Placement for Large Scale Mixed-size Designs2018 International Conference on Intelligent Autonomous Systems (ICoIAS)10.1109/ICoIAS.2018.8493948(77-81)Online publication date: Mar-2018
https://doi.org/10.1109/ICoIAS.2018.8493948
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