[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2463209.2488920acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
research-article

Taming the complexity of coordinated place and route

Published: 29 May 2013 Publication History

Abstract

IC performance, power dissipation, size, and signal integrity are now dominated by interconnects. However, with ever-shrinking standard cells, blind minimization of interconnect during placement causes routing failures. Hence, we develop Coordinated Place-and-Route (CoPR) with (i) a Lightweight Incremental Routing Estimation (LIRE) frequently invoked during placement, (ii) placement techniques that address three types of routing congestion, and (iii) an interface to congestion estimation that supports new types of incrementality. LIRE comprehends routing obstacles and non-uniform routing capacities, and relies on a cache-friendly, fully-incremental routing algorithm. Our implementation extends and improves our winning entry at the ICCAD 2012 Contest.

References

[1]
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, 2001.
[2]
L. Dagum and R. Menon, "OpenMP: An Industry Standard API for Shared-memory Programming," Computational Science and Engineering 1998, pp. 46--55.
[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", ICCAD 2011, pp. 74--79.
[4]
J. Hu, J. A. Roy and I. L. Markov, "Completing High-quality Global Routes", ISPD 2010, pp. 35--41.
[5]
M.-K. Hsu, S. Chou, T.-H. Lin and Y.-W. Chang, "Routability-driven Analytical Placement for Mixed-size Circuit Designs", ICCAD 2011, pp. 80--84.
[6]
L. Hsu, R. Iyer, S. Makineni, S. Reinhardt and D. Newell, "Exploring the Cache Design Space for Large Scale CMPs," Computer Architecture News 2005, pp. 24--33.
[7]
International Technology Roadmap for Semiconductors (ITRS).
[8]
M.-C. Kim, J. Hu, D.-J. Lee and I. L. Markov, "A SimPLR Method for Routability-driven Placement", ICCAD 2011, pp. 67--73.
[9]
M.-C. Kim, D.-J. Lee and I. L. Markov, "SimPL: An Effective Placement Algorithm", TCAD 31(1) (2012), pp. 50--60.
[10]
B. Korte, D. Rautenbach and J. Vygen, "BonnTools: Mathematical Innovation for Layout and Timing Closure of Systems on a Chip", Proc. IEEE 95(3) (2007), pp. 555--572.
[11]
Z. Li, C. J. Alpert, G.-J. Nam, C. Sze, N. Viswanathan and N. Y. Zhou, "Guiding a Physical Design Closure System to Produce Easier-to-route Designs with More Predictable Timing", DAC 2012, pp. 465--470.
[12]
W.-H. Liu, W.-C. Kao, Y.-L. Li, K.-Y. Chao, "Multi-threaded Collision-aware Global Routing with Bounded-length Maze Routing", DAC 2010, pp.200--205.
[13]
W.-H. Liu, Y.-L. Li, C.-K. Kok,"A Fast Maze-free Routing Congestion Estimator With Hybrid Unilateral Monotonic Routing", ICCAD 2012, pp.713--719.
[14]
M. Pan, Y. Xu, Y. Zhang and C. Chu, "FastRoute: An Efficient and High-quality Global Router", VLSI Design 2012, 18 pages.
[15]
S. K. Raman, V. Pentkovski and J. Keshava, "Implementing Streaming SIMD Extensions on the Pentium III Processor", Micro 20(4)(2000), pp. 47--57.
[16]
P. N. Parakh, R. B. Brown and K. A. Sakallah, "Congestion Driven Quadratic Placement, DAC 1998, pp. 275--278.
[17]
J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert and I. L. Markov, "CRISP: Congestion Reduction by Iterated Spreading during Placement", ICCAD 2009, pp. 357--362.
[18]
N. Viswanathan, C. J. Alpert, C. Sze, Z. Li, G.-J. Nam and J. A. Roy, "The ISPD-2011 Routability-driven Placement Contest and Benchmark Suite", ISPD 2011, pp. 141--146.
[19]
N. Viswanathan, C. J. Alpert, C. Sze, Z. Li, Y. Wei, "The DAC 2012 Routability-driven Placement Contest and Benchmark Suite", DAC 2012, pp. 774--782.
[20]
N. Viswanathan, C. J. Alpert, C. Sze, Z. Li and Y. Wei, "ICCAD-2012 CAD Contest in Design Hierarchy Aware Routability-driven Placement and Benchmark Suite", ICCAD 2012, pp. 345--348. cad_contest.cs.nctu.edu.tw/CAD-contest-at-ICCAD2012/problems/p2/p2.html
[21]
Y. Wei, C. Sze, N. Viswanathan, Z. Li, C. J. Alpert, L. N. Reddy, A. D. Huber, G. E. Terez, D. Keller and S. S. Sapatnekar, "GLARE: Global and Local Wiring Aware Routability Evaluation", DAC 2012, pp. 768--773.
[22]
J. Westra and P. Groeneveld, "Is Probabilistic Congestion Estimation Worthwhile?" SLIP 2005, pp. 99--106.
[23]
J. Y. Yen, "An Algorithm for Finding Shortest Routes From All Source Nodes to a Given Destination in General Networks", Proc. Quarterly of Applied Mathematics 27 (1970), pp.526--530.
[24]
Y. Zhang and C. Chu, "CROP: Fast and Effective Congestion Refinement of Placement", ICCAD 2009, pp. 344--350.
[25]
Y. Zhang and C. Chu, "GDRouter: Interleaved Global Routing and Detailed Routing for Ultimate Routability", DAC 2012, pp. 597--602.

Cited By

View all
  • (2021)OptiPlace: optimized placement solution for mixed-size designsAnalog Integrated Circuits and Signal Processing10.1007/s10470-021-01864-5Online publication date: 13-May-2021
  • (2019)Routability-driven Placement for Mixed-size Designs using Design-hierarchy and Pin Information2019 International Conference on Automation, Computational and Technology Management (ICACTM)10.1109/ICACTM.2019.8776791(424-430)Online publication date: Apr-2019
  • (2017)An integrated-spreading-based macro-refining algorithm for large-scale mixed-size circuit designsProceedings of the 36th International Conference on Computer-Aided Design10.5555/3199700.3199766(496-503)Online publication date: 13-Nov-2017
  • Show More Cited By

Recommendations

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

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 2013

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

DAC '13
Sponsor:

Acceptance Rates

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

Upcoming Conference

DAC '25
62nd ACM/IEEE Design Automation Conference
June 22 - 26, 2025
San Francisco , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)1
Reflects downloads up to 03 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2021)OptiPlace: optimized placement solution for mixed-size designsAnalog Integrated Circuits and Signal Processing10.1007/s10470-021-01864-5Online publication date: 13-May-2021
  • (2019)Routability-driven Placement for Mixed-size Designs using Design-hierarchy and Pin Information2019 International Conference on Automation, Computational and Technology Management (ICACTM)10.1109/ICACTM.2019.8776791(424-430)Online publication date: Apr-2019
  • (2017)An integrated-spreading-based macro-refining algorithm for large-scale mixed-size circuit designsProceedings of the 36th International Conference on Computer-Aided Design10.5555/3199700.3199766(496-503)Online publication date: 13-Nov-2017
  • (2017)Fence-aware detailed-routability driven placement2017 ACM/IEEE International Workshop on System Level Interconnect Prediction (SLIP)10.1109/SLIP.2017.7974905(1-7)Online publication date: 27-Jun-2017
  • (2017)An integrated-spreading-based macro-refining algorithm for large-scale mixed-size circuit designs2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2017.8203818(496-503)Online publication date: Nov-2017
  • (2016)Ripple 2.0ACM Transactions on Design Automation of Electronic Systems10.1145/292598922:1(1-26)Online publication date: 2-Sep-2016
  • (2016)Eh?PlacerACM Transactions on Design Automation of Electronic Systems10.1145/289938121:3(1-27)Online publication date: 19-Apr-2016
  • (2016)Negotiation-based track assignment considering local nets2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2016.7428041(378-383)Online publication date: Jan-2016
  • (2015)Closing the Gap between Global and Detailed PlacementProceedings of the 2015 Symposium on International Symposium on Physical Design10.1145/2717764.2717776(149-156)Online publication date: 29-Mar-2015
  • (2015)Region-Based and Panel-Based Algorithms for Unroutable Placement RecognitionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.239443234:4(502-514)Online publication date: Apr-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media