Simultaneous Timing Driven Tree Surgery in Routing with Machine Learning-based Acceleration
Pages 261 - 266
Abstract
In global routing, both timing and routability are critical criterions to measure the performance of a design. However, these two objectives naturally conflict with each other during routing. In this paper, a tree surgery technique is presented to adjust routing tree topologies in global routing to fix timing. We formulate the problem as a quadratic program(QP), which adjusts routing topologies of all the nets from a global perspective and takes congestion into consideration to trade off timing and routability objectives. We also apply machine learning-based techniques to accelerate our algorithm, which offers a fast and effective way to solve the problem. Experimental results on ICCAD~2015 benchmarks show that our algorithms can achieve 10.12% timing improvement with no significant degradation in routability and wirelength. With machine learning-based acceleration (MLA), our results can be obtained in almost negligible runtime.
References
[1]
Charles J Alpert, Andrew B Kahng, CN Sze, and Qinke Wang. 2006. Timing-driven steiner trees are (practically) free Proceedings of the 43rd annual Design Automation Conference. ACM, 389--392.
[2]
Yen-Jung Chang, Yu-Ting Lee, Jhih-Rong Gao, Pei-Ci Wu, and Ting-Chi Wang. 2010. NTHU-route 2.0: a robust global router for modern designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Vol. 29, 12 (2010), 1931--1944.
[3]
Genjie Chen, Peishan Tu, and Evangeline FY Young. 2017. SALT: Provably Good Routing Topology by a Novel Steiner Shallow-Light Tree Algorithm. In Proceedings of the 2017 IEEE/ACM international conference on Computer-aided design. ACM.
[4]
Minsik Cho and David Z Pan. 2007. BoxRouter: a new global router based on box expansion and progressive ILP. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Vol. 26, 12 (2007), 2130--2143.
[5]
Minsik Cho, David Z Pan, Hua Xiang, and Ruchir Puri. 2006. Wire density driven global routing for CMP variation and timing Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design. ACM, 487--492.
[6]
Chris Chu and Yiu-Chung Wong. 2008. FLUTE: Fast lookup table based rectilinear steiner minimal tree algorithm for VLSI design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Vol. 27, 1 (2008), 70--83.
[7]
Jiang Hu and Sachin S Sapatnekar. 2000. A timing-constrained algorithm for simultaneous global routing of multiple nets Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design. IEEE Press, 99--103.
[8]
Jin Hu, Greg Schaeffer, and Vibhor Garg. 2015. TAU 2015 contest on incremental timing analysis. In Computer-Aided Design (ICCAD), 2015 IEEE/ACM International Conference on. IEEE, 882--889.
[9]
Tsung-Wei Huang and Martin DF Wong. 2015. OpenTimer: A high-performance timing analysis tool Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE Press, 895--902.
[10]
IBM. 2017. CPLEX. (2017). https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/ tempurl
[11]
Tong Jing, Xianlong Hong, Haiyun Bao, Yici Cai, Jingyu Xu, Chungkuan Cheng, and Jun Gu. 2003. UTACO: a unified timing and congestion optimizing algorithm for standard cell global routing. In Proceedings of the 2003 Asia and South Pacific Design Automation Conference. ACM, 834--839.
[12]
Andrew B Kahng. 2015. New game, new goal posts: A recent history of timing closure Proceedings of the 52nd Annual Design Automation Conference. ACM, 4.
[13]
Myung-Chul Kim, Jin Hu, Jiajia Li, and Natarajan Viswanathan. 2015. Iccad-2015 cad contest in incremental timing-driven placement and benchmark suite Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE Press, 921--926.
[14]
Andy Liaw, Matthew Wiener, et almbox. . 2002. Classification and regression by randomForest. R news Vol. 2, 3 (2002), 18--22.
[15]
Wen-Hao Liu, Wei-Chun Kao, Yih-Lang Li, and Kai-Yuan Chao. 2013 a. NCTU-GR 2.0: multithreaded collision-aware global routing with bounded-length maze routing. IEEE Transactions on computer-aided design of integrated circuits and systems Vol. 32, 5 (2013), 709--722.
[16]
Wen-Hao Liu, Cheng-Kok Koh, and Yih-Lang Li. 2013 b. Optimization of placement solutions for routability Design Automation Conference (DAC), 2013 50th ACM/EDAC/IEEE. IEEE, 1--9.
[17]
Michael D Moffitt. 2008. MaizeRouter: Engineering an effective global router. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Vol. 27, 11 (2008), 2017--2026.
[18]
Min Pan, Yue Xu, Yanheng Zhang, and Chris Chu. 2012. FastRoute: An efficient and high-quality global router. VLSI Design Vol. 2012 (2012), 14.
[19]
Ahmed Youssef, Zhen Yang, Mohab Anis, Shawki Areibi, Anthony Vannelli, and Mohamed Elmasry. 2010. A power-efficient multipin ILP-based routing technique. IEEE Transactions on Circuits and Systems I: Regular Papers Vol. 57, 1 (2010), 225--235.
Index Terms
- Simultaneous Timing Driven Tree Surgery in Routing with Machine Learning-based Acceleration
Recommendations
Timing-Constrained Flexibility-Driven Routing Tree Construction
As the complexity of VLSI circuits increases, the routability problem becomes more and more important in modern VLSI design. In general, the flexibility improvement of the edges in a routing tree has been exploited to release the routing congestion and ...
Timing-constrained congestion-driven global routing
ASP-DAC '04: Proceedings of the 2004 Asia and South Pacific Design Automation ConferenceIt is well known that congestion control becomes more and more important in modern grid-based routing process. In this paper, a timing-constrained congestion-driven global routing approach is proposed to obtain initial congestion-driven global routing ...
Clock-Tree-Aware Incremental Timing-Driven Placement
Special Section on New Physical Design Techniques for the Next Generation Integration Technology and Regular PapersThe increasing impact of interconnections on overall circuit performance makes timing-driven placement (TDP) a crucial step toward timing closure. Current TDP techniques improve critical paths but overlook the impact of register placement on clock tree ...
Comments
Information & Contributors
Information
Published In
May 2018
533 pages
ISBN:9781450357241
DOI:10.1145/3194554
- General Chair:
- Deming Chen,
- Program Chairs:
- Houman Homayoun,
- Baris Taskin
Copyright © 2018 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
- IEEE CEDA
- IEEE CASS
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 May 2018
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- the Research Grants Council of the Hong Kong Special Administrative Region China
Conference
GLSVLSI '18
Sponsor:
Acceptance Rates
GLSVLSI '18 Paper Acceptance Rate 48 of 197 submissions, 24%;
Overall Acceptance Rate 312 of 1,156 submissions, 27%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 102Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)1
Reflects downloads up to 07 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in