research-article

Incremental Layer Assignment for Timing Optimization

Authors:

Salim Chowdhury,

David Z. PanAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 22, Issue 4

Article No.: 75, Pages 1 - 25

https://doi.org/10.1145/3083727

Published: 13 June 2017 Publication History

Abstract

With VLSI technology nodes scaling into the nanometer regime, interconnect delay plays an increasingly critical role in timing. For layer assignment, most works deal with via counts or total net delays, ignoring critical paths of each net and resulting in potential timing issues. In this article, we propose an incremental layer assignment framework targeting delay optimization in timing the critical path of each net. A set of novel techniques are presented: self-adaptive quadruple partition based on K × K division benefits the runtime; semidefinite programming is utilized for each partition; and the sequential mapping algorithm guarantees integer solutions while satisfying edge capacities; additionally, concurrent mapping offers a global view of assignment and post delay optimization reduces the path timing violations. The effectiveness of our work is verified by ISPD’08 benchmarks.

References

[1]

Jianchang Ao, Sheqin Dong, Song Chen, and Satoshi Goto. 2013. Delay-driven layer assignment in global routing under multi-tier interconnect structure. In ACM International Symposium on Physical Design (ISPD’13). 101--107.

Digital Library

[2]

Brian Borchers. 1999. CSDP, A C library for semidefinite programming. Optimization Methods and Software 11 (1999), 613--623.

[3]

Rohit Chandra. 2001. Parallel Programming in OpenMP. Morgan Kaufmann.

[4]

James Hsueh-Chung Chen, Theodorus E. Standaert, Emre Alptekin, Terry A. Spooner, and Vamsi Paruchuri. 2014. Interconnect performance and scaling strategy at 7 nm node. In IEEE International Interconnect Technology Conference (IITC’14). 93--96.

[5]

Jason Cong and Bin Liu. 2012. A metric for layout-friendly microarchitecture optimization in high-level synthesis. In ACM/IEEE Design Automation Conference (DAC’12). 1239--1244.

Digital Library

[6]

Ke-Ren Dai, Wen-Hao Liu, and Yih-Lang Li. 2009. Efficient simulated evolution based rerouting and congestion-relaxed layer assignment on 3-D global routing. In IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC’09). 570--575.

[7]

Peng Du, Shih-Hung Weng, Xiang Hu, and Chung-Kuan Cheng. 2011. Power grid sizing via convex programming. In International Conference on ASIC (ASICON’11). 337--340.

[8]

Ananda D. Gunawardena, S. K. Jain, and Larry Snyder. 1991. Modified iterative methods for consistent linear systems. Linear Algebra Applications 154 (1991), 123--143.

[9]

Gurobi Optimization Inc. 2016. Gurobi Optimizer Reference Manual. http://www.gurobi.com.

[10]

Chin-Hsiung Hsu, Huang-Yu Chen, and Yao-Wen Chang. 2008. Multi-layer global routing considering via and wire capacities. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD’08). 350--355.

[11]

Meng-Kai Hsu, Nitesh Katta, Homer Yen-Hung Lin, Keny Tzu-Hen Lin, King Ho Tam, and Ken Chung-Hsing Wang. 2014. Design and manufacturing process co-optimization in nano-technology. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD’14). 574--581.

Digital Library

[12]

Jiang Hu and Sachin S. Sapatnekar. 2001. A survey on multi-net global routing for integrated circuits. Integration, the VLSI Journal 31, 1 (2001), 1--49.

[13]

Andrew B. Kahng, Bao Liu, and Sheldon X.-D. Tan. 2006. Efficient decoupling capacitor planning via convex programming methods. In ACM International Symposium on Physical Design (ISPD’06). 102--107.

Digital Library

[14]

Yukihide Kohira, Tomomi Matsui, Yoko Yokoyama, Chikaaki Kodama, Atsushi Takahashi, Shigeki Nojima, and Satoshi Tanaka. 2015. Fast mask assignment using positive semidefinite relaxation in LELECUT triple patterning lithography. In IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC’15). 665--670.

[15]

Tsung-Hsien Lee and Ting-Chi Wang. 2008. Congestion-constrained layer assignment for via minimization in global routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) 27, 9 (2008), 1643--1656.

Digital Library

[16]

Tsung-Hsien Lee and Ting-Chi Wang. 2010. Simultaneous antenna avoidance and via optimization in layer assignment of multi-layer global routing. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD’10). 312--318.

[17]

Derong Liu, Bei Yu, Salim Chowdhury, and David Z. Pan. 2016. Incremental layer assignment for critical path timing. In ACM/IEEE Design Automation Conference (DAC’16). 85:1--85:6.

Digital Library

[18]

Derong Liu, Bei Yu, Salim Chowdhury, and David Z. Pan. 2017. TILA-S: Timing-driven incremental layer assignment avoiding slew violations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) (2017).

[19]

Wen-Hao Liu and Yih-Lang Li. 2011. Negotiation-based layer assignment for via count and via overflow minimization. In IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC’11). 539--544.

[20]

Vinicius Livramento, Derong Liu, Salim Chowdhury, Bei Yu, Xiaoqing Xu, David Z. Pan, Jose Luis Guntzel, and Luiz C. V. dos Santos. 2017. Incremental layer assignment driven by an external signoff timing engine. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) (2017).

[21]

Gi-Joon Nam, Cliff Sze, and Mehmet Yildiz. 2008. The ISPD global routing benchmark suite. In ACM International Symposium on Physical Design (ISPD’08). 156--159.

Digital Library

[22]

Maurice Queyranne. 1986. Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems. Operations Research Letters 4, 5 (1986), 231--234.

Digital Library

[23]

Daohang Shi, Edward Tashjian, and Azadeh Davoodi. 2016. Dynamic planning of local congestion from varying-size vias for global routing layer assignment. In IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC’16). 372--377.

[24]

Lieven Vandenberghe and Stephen Boyd. 1996. Semidefinite programming. SIAM Review (SIREV) 38, 1 (1996), 49--95.

Digital Library

[25]

Lieven Vandenberghe, Stephen Boyd, and Abbas El Gamal. 1997. Optimal wire and transistor sizing for circuits with non-tree topology. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD’97). 252--259.

[26]

Bei Yu, Derong Liu, Salim Chowdhury, and David Z. Pan. 2015a. TILA: Timing-driven incremental layer assignment. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD’15). 110--117.

[27]

Bei Yu, Kun Yuan, Duo Ding, and David Z. Pan. 2015b. Layout decomposition for triple patterning lithography. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) 34, 3 (March 2015), 433--446.

Cited By

Liu GZhang XGuo WHuang XLiu WChao KWang T(2022)Timing-Aware Layer Assignment for Advanced Process Technologies Considering via PillarsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.310029641:6(1957-1970)Online publication date: Jun-2022
https://doi.org/10.1109/TCAD.2021.3100296
Zhang XZhuang ZLiu GHuang XLiu WGuo WWang TDi Natale GFummi F(2020)MiniDelayProceedings of the 23rd Conference on Design, Automation and Test in Europe10.5555/3408352.3408484(586-591)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.5555/3408352.3408484
Zhang XZhuang ZLiu GHuang XLiu WGuo WWang T(2020)MiniDelay: Multi-Strategy Timing-Aware Layer Assignment for Advanced Technology Nodes2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE48585.2020.9116269(586-591)Online publication date: Mar-2020
https://doi.org/10.23919/DATE48585.2020.9116269
Show More Cited By

Index Terms

Incremental Layer Assignment for Timing Optimization
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Delay-driven layer assignment in global routing under multi-tier interconnect structure
ISPD '13: Proceedings of the 2013 ACM International symposium on Physical Design

A multilayer routing system usually adopts multiple interconnect configuration with different wire sizes and thicknesses. Since thicker layers of metal lead to fatter wires with smaller resistance, the layer assignment of nets has a large impact on the ...
Novel Airgap Insertion and Layer Reassignment for Timing Optimization Guided by Slack Dependency
ISPD '24: Proceedings of the 2024 International Symposium on Physical Design

BEOL with airgap technology is an alternative metallization option with promising performance, electrical yield and reliability to explore at 2nm node and beyond. Airgaps form cavities in inter-metal dielectrics (IMD) between interconnects. The ultra-low ...
Robust layer assignment for via optimization in multi-layer global routing
ISPD '09: Proceedings of the 2009 international symposium on Physical design

In this paper, we study a layer assignment problem which arises during multi-layer global routing. Our layer assignment problem takes the total wire overflow and the maximum wire overflow of a given 2D global routing solution to form the wire congestion ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 22, Issue 4

October 2017

430 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3097980

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2017 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 13 June 2017

Accepted: 01 March 2017

Revised: 01 January 2017

Received: 01 October 2016

Published in TODAES Volume 22, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF SRC, NSFC, Oracle, and the Chinese University of Hong Kong (CUHK) Direct Grant for Research

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
244
Total Downloads

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

Reflects downloads up to 24 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu GZhang XGuo WHuang XLiu WChao KWang T(2022)Timing-Aware Layer Assignment for Advanced Process Technologies Considering via PillarsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.310029641:6(1957-1970)Online publication date: Jun-2022
https://doi.org/10.1109/TCAD.2021.3100296
Zhang XZhuang ZLiu GHuang XLiu WGuo WWang TDi Natale GFummi F(2020)MiniDelayProceedings of the 23rd Conference on Design, Automation and Test in Europe10.5555/3408352.3408484(586-591)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.5555/3408352.3408484
Zhang XZhuang ZLiu GHuang XLiu WGuo WWang T(2020)MiniDelay: Multi-Strategy Timing-Aware Layer Assignment for Advanced Technology Nodes2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE48585.2020.9116269(586-591)Online publication date: Mar-2020
https://doi.org/10.23919/DATE48585.2020.9116269
Liu DYu BChowdhury SPan D(2018)TILA-S: Timing-Driven Incremental Layer Assignment Avoiding Slew ViolationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.265222137:1(231-244)Online publication date: Jan-2018
https://doi.org/10.1109/TCAD.2017.2652221

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.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents