research-article

Detailed routing by sparse grid graph and minimum-area-captured path search

Authors:

Evangeline F. Y. YoungAuthors Info & Claims

ASPDAC '19: Proceedings of the 24th Asia and South Pacific Design Automation Conference

Pages 754 - 760

https://doi.org/10.1145/3287624.3287678

Published: 21 January 2019 Publication History

Abstract

Different from global routing, detailed routing takes care of many detailed design rules and is performed on a significantly larger routing grid graph. In advanced technology nodes, it becomes the most complicated and time-consuming stage. We propose Dr. CU, an efficient and effective detailed router, to tackle the challenges. To handle a 3D detailed routing grid graph of enormous size, a set of two-level sparse data structures is designed for runtime and memory efficiency. For handling the minimum-area constraint, an optimal correct-by-construction path search algorithm is proposed. Besides, an efficient bulk synchronous parallel scheme is adopted to further reduce the runtime usage. Compared with the first place of ISPD 2018 Contest, our router improves the routing quality by up to 65% and on average 39%, according to the contest metric. At the same time, it achieves 80--93% memory reduction, and 2.5--15X speed-up.

References

[1]

Y. Zhang and C. Chu, "RegularRoute: An efficient detailed router applying regular routing patterns," IEEE TVLSI, vol. 21, no. 9, pp. 1655--1668, 2013.

Digital Library

[2]

S. Mantik, G. Posser, W.-K. Chow, Y. Ding, and W.-H. Liu, "ISPD 2018 initial detailed routing contest and benchmarks," in Proc. ISPD, 2018, pp. 140--143.

Digital Library

[3]

J. A. Roy and I. L. Markov, "High-performance routing at the nanometer scale," IEEE TCAD, vol. 27, no. 6, pp. 1066--1077, 2008.

Digital Library

[4]

Y. Xu, Y. Zhang, and C. Chu, "FastRoute 4.0: global router with efficient via minimization," in Proc. ASPDAC, 2009, pp. 576--581.

Digital Library

[5]

M. Cho, K. Lu, K. Yuan, and D. Z. Pan, "BoxRouter 2.0: A hybrid and robust global router with layer assignment for routability," ACM TODAES, vol. 14, no. 2, p. 32, 2009.

Digital Library

[6]

M. M. Ozdal and M. D. Wong, "Archer: A history-based global routing algorithm," IEEE TCAD, vol. 28, no. 4, pp. 528--540, 2009.

Digital Library

[7]

T.-H. Wu, A. Davoodi, and J. T. Linderoth, "GRIP: Global routing via integer programming," IEEE TCAD, vol. 30, no. 1, pp. 72--84, 2011.

Digital Library

[8]

M. Gester, D. Müller, T. Nieberg, C. Panten, C. Schulte, and J. Vygen, "BonnRoute: Algorithms and data structures for fast and good vlsi routing," ACM TODAES, vol. 18, no. 2, p. 32, 2013.

Digital Library

[9]

W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao, "NCTU-GR 2.0: Multithreaded collision-aware global routing with bounded-length maze routing," IEEE TCAD, vol. 32, no. 5, pp. 709--722, 2013.

Digital Library

[10]

F.-Y. Chang, R.-S. Tsay, W.-K. Mak, and S.-H. Chen, "MANA: A shortest path maze algorithm under separation and minimum length nanometer rules," IEEE TCAD, vol. 32, no. 10, pp. 1557--1568, 2013.

Digital Library

[11]

M. Ahrens, M. Gester, N. Klewinghaus, D. Müller, S. Peyer, C. Schulte, and G. Tellez, "Detailed routing algorithms for advanced technology nodes," IEEE TCAD, vol. 34, no. 4, pp. 563--576, 2015.

[12]

M. M. Ozdal, "Detailed-routing algorithms for dense pin clusters in integrated circuits," IEEE TCAD, vol. 28, no. 3, pp. 340--349, 2009.

Digital Library

[13]

T. Nieberg, "Gridless pin access in detailed routing," in Proc. DAC, 2011, pp. 170--175.

Digital Library

[14]

X. Xu, Y. Lin, V. Livramento, and D. Z. Pan, "Concurrent pin access optimization for unidirectional routing," in Proc. DAC, 2017, p. 20.

Digital Library

[15]

Q. Ma, H. Zhang, and M. D. Wong, "Triple patterning aware routing and its comparison with double patterning aware routing in 14nm technology," in Proc. DAC, 2012, pp. 591--596.

Digital Library

[16]

Y.-H. Lin, B. Yu, D. Z. Pan, and Y.-L. Li, "Triad: A triple patterning lithography aware detailed router," in Proc. ICCAD, 2012, pp. 123--129.

Digital Library

[17]

Z. Liu, C. Liu, and E. F. Young, "An effective triple patterning aware grid-based detailed routing approach," in Proc. DATE, 2015, pp. 1641--1646.

Digital Library

[18]

Y. Ding, C. Chu, and W.-K. Mak, "Self-aligned double patterning-aware detailed routing with double via insertion and via manufacturability consideration," IEEE TCAD, vol. 37, no. 3, pp. 657--668, 2018.

[19]

Y.-H. Su and Y.-W. Chang, "VCR: Simultaneous via-template and cut-template-aware routing for directed self-assembly technology," in Proc. ICCAD, 2016, pp. 49:1--49:8.

Digital Library

[20]

C. Albrecht, "Global routing by new approximation algorithms for multicommodity flow," IEEE TCAD, vol. 20, no. 5, pp. 622--632, 2001.

Digital Library

[21]

E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, no. 1, pp. 269--271, 1959.

Digital Library

[22]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms. MIT press, 2009.

Digital Library

[23]

C.J. Alpert, D. P. Mehta, and S. S. Sapatnekar, Eds., Handbook of algorithms for physical design automation. CRC press, 2008.

Digital Library

[24]

L. G. Valiant, "A bridging model for parallel computation," Communications of the ACM, vol. 33, no. 8, pp. 103--111, 1990.

Digital Library

[25]

E. W. Dijkstra, "Solution of a problem in concurrent programming control," Communications of the ACM, vol. 8, no. 9, p. 569, 1965.

Digital Library

[26]

A. Guttman, "R-trees: A dynamic index structure for spatial searching," in Proc. SIGMOD, 1984, pp. 47--57.

Digital Library

[27]

Boost geometry library. {Online}. Available: https://www.boost.org/doc/libs/1_67_0/libs/geometry/doc/html/

Cited By

Pan YZhou ZSheikholeslam SIvanov A(2024)VioNet: A Hierarchical Detailed Routing Wire-Short Violation Predictor Based on a Convolutional Neural NetworkIEEE Design & Test10.1109/MDAT.2023.331467241:2(65-74)Online publication date: Apr-2024
https://doi.org/10.1109/MDAT.2023.3314672
Du XWang CZhong RYan JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)HubRouterProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669557(78558-78579)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669557
Qiu YXing YZheng XGao PCai SXiong X(2023)Progress of Placement Optimization for Accelerating VLSI Physical DesignElectronics10.3390/electronics1202033712:2(337)Online publication date: 9-Jan-2023
https://doi.org/10.3390/electronics12020337
Show More Cited By

Detailed routing by sparse grid graph and minimum-area-captured path search
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

ISPD 2018 Initial Detailed Routing Contest and Benchmarks
ISPD '18: Proceedings of the 2018 International Symposium on Physical Design

In advanced technology nodes, detailed routing becomes the most complicated and runtime consuming stage. To spur detailed routing research, ISPD 2018 initial detailed routing contest is hosted and it is the first ISPD contest on detailed routing ...
ISPD 2019 Initial Detailed Routing Contest and Benchmark with Advanced Routing Rules
ISPD '19: Proceedings of the 2019 International Symposium on Physical Design

Detailed routing becomes the most complicated and runtime consuming stage in the physical design flow as technology nodes advance. Due to the inaccessibility of advanced routing rules and industrial designs, it is hard to conduct detailed routing ...
Mixed-cell-height detailed placement considering complex minimum-implant-area constraints
ICCAD '17: Proceedings of the 36th International Conference on Computer-Aided Design

Mixed-cell-height circuits have prevailed in advanced technology to address various design needs. Along with device scaling, complex minimum-implant-area (MIA) constraints arise as an emerging challenge in modern circuit designs, adding to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPDAC '19: Proceedings of the 24th Asia and South Pacific Design Automation Conference

January 2019

794 pages

ISBN:9781450360074

DOI:10.1145/3287624

General Chair:
Toshiyuki Shibuya
Fujitsu Laboratories

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

SIGDA: ACM Special Interest Group on Design Automation

In-Cooperation

IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IEEE CAS
IEEE CEDA
IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Research Grants Council, University Grants Committee

Conference

ASPDAC '19

Sponsor:

SIGDA

ASPDAC '19: 24th Asia and South Pacific Design Automation Conference

January 21 - 24, 2019

Tokyo, Japan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
602
Total Downloads

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

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pan YZhou ZSheikholeslam SIvanov A(2024)VioNet: A Hierarchical Detailed Routing Wire-Short Violation Predictor Based on a Convolutional Neural NetworkIEEE Design & Test10.1109/MDAT.2023.331467241:2(65-74)Online publication date: Apr-2024
https://doi.org/10.1109/MDAT.2023.3314672
Du XWang CZhong RYan JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)HubRouterProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669557(78558-78579)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669557
Qiu YXing YZheng XGao PCai SXiong X(2023)Progress of Placement Optimization for Accelerating VLSI Physical DesignElectronics10.3390/electronics1202033712:2(337)Online publication date: 9-Jan-2023
https://doi.org/10.3390/electronics12020337
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
Chen YSu MDing HWeng SLin ZBai X(2023)High-correlation 3D routability estimation for congestion-guided global routingThe Journal of Supercomputing10.1007/s11227-023-05553-080:3(3114-3141)Online publication date: 29-Aug-2023
https://doi.org/10.1007/s11227-023-05553-0
Zhuang ZLiu GHo TYu BGuo WBolchini CO'Connor IVerbauwhede IWille R(2022)TRADERProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3540029(766-771)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3540029
Zhuang ZLiu GHo TYu BGuo W(2022)TRADER: A Practical Track-Assignment-Based Detailed Router2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774774(766-771)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774774
Posser GYoung EHeld SLi YPan DBehjat LYang S(2022)Challenges and Approaches in VLSI RoutingProceedings of the 2022 International Symposium on Physical Design10.1145/3505170.3511477(185-192)Online publication date: 13-Apr-2022
https://dl.acm.org/doi/10.1145/3505170.3511477
Lin YQu TLu ZSu YWei Y(2022)Asynchronous Reinforcement Learning Framework and Knowledge Transfer for Net-Order Exploration in Detailed RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.311750541:9(3132-3142)Online publication date: Sep-2022
https://doi.org/10.1109/TCAD.2021.3117505
Huang HChen WCai ZHuang JChen J(2022)An Efficient Global Router for Large-scale Congestion-driven Routing2022 IEEE 16th International Conference on Solid-State & Integrated Circuit Technology (ICSICT)10.1109/ICSICT55466.2022.9963327(1-3)Online publication date: 25-Oct-2022
https://doi.org/10.1109/ICSICT55466.2022.9963327
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.

Figures

Tables

Media

View Table of Conten