tutorial

TILA: Timing-Driven Incremental Layer Assignment

Authors:

Salim Chowdhury,

David Z. PanAuthors Info & Claims

ICCAD '15: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design

Pages 110 - 117

Published: 02 November 2015 Publication History

Abstract

As VLSI technology scales to deep submicron and beyond, interconnect delay greatly limits the circuit performance. The traditional 2D global routing and subsequent net by net assignment of available empty tracks on various layers lacks a global view for timing optimization. To overcome the limitation, this paper presents a timing driven incremental layer assignment tool, TILA, to reassign layers among routing segments of critical nets and non-critical nets. Lagrangian relaxation techniques are proposed to iteratively provide consistent layer/via assignments. Modeling via min-cost flow for layer shuffling avoids using integer programming and yet guarantees integer solutions via uni-modular property of the inherent model. In addition, multiprocessing of K x K partitions of the whole chip provides run time speed up. Certain parameters introduced in the models provide trade-off between timing optimization and via count. Experimental results in both ISPD'08 and industry benchmark suites demonstrate the effectiveness of the proposed incremental algorithms.

References

[1]

J. H.-C. Chen, T. E. Standaert, E. Alptekin, T. A. Spooner, and V. Paruchuri, "Interconnect performance and scaling strategy at 7 nm node," in IEEE International Interconnect Technology Conference (IITC), 2014, pp. 93--96.

[2]

J. Cong, "An interconnect-centric design flow for nanometer technologies," Proceedings of the IEEE, vol. 89, no. 4, pp. 505--528, 2001.

[3]

M. Cho and D. Z. Pan, "BoxRouter: a new global router based on box expansion and progressive ILP," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 26, no. 12, pp. 2130--2143, 2007.

Digital Library

[4]

J. Roy and I. Markov, "High-performance routing at the nanometer scale," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 27, no. 6, pp. 1066--1077, 2008.

Digital Library

[5]

T.-H. Wu, A. Davoodi, and J. T. Linderoth, "GRIP: Global routing via integer programming," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 30, no. 1, pp. 72--84, 2011.

Digital Library

[6]

M. D. Moffitt, "MaizeRouter: Engineering an effective global router," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 27, no. 11, pp. 2017--2026, 2008.

Digital Library

[7]

C.-H. Hsu, H.-Y. Chen, and Y.-W. Chang, "Multilayer global routing with via and wire capacity considerations," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 29, no. 5, pp. 685--696, 2010.

Digital Library

[8]

Y.-J. Chang, Y.-T. Lee, J.-R. Gao, P.-C. Wu, and T.-C. Wang, "NTHU-Route 2.0: a robust global router for modern designs," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 29, no. 12, pp. 1931--1944, 2010.

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 Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 32, no. 5, pp. 709--722, 2013.

Digital Library

[10]

"ITRS," http://www.itrs.net.

[11]

M.-K. Hsu, N. Katta, H. Y.-H. Lin, K. T.-H. Lin, K. H. Tam, and K. C.-H. Wang, "Design and manufacturing process co-optimization in nano-technology," in IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2014, pp. 574--581.

Digital Library

[12]

Z. Li, C. J. Alpert, S. Hu, T. Muhmud, S. T. Quay, and P. G. Villarrubia, "Fast interconnect synthesis with layer assignment," in ACM International Symposium on Physical Design (ISPD), 2008, pp. 71--77.

Digital Library

[13]

S. Hu, Z. Li, and C. J. Alpert, "A polynomial time approximation scheme for timing constrained minimum cost layer assignment," in IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2008, pp. 112--115.

Digital Library

[14]

S. Hu, Z. Li, and C. J. Alpert, "A faster approximation scheme for timing driven minimum cost layer assignment," in ACM International Symposium on Physical Design (ISPD), 2009, pp. 167--174.

Digital Library

[15]

T.-H. Lee and T.-C. Wang, "Congestion-constrained layer assignment for via minimization in global routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 27, no. 9, pp. 1643--1656, 2008.

Digital Library

[16]

K.-R. Dai, W.-H. Liu, and Y.-L. Li, "NCTU-GR: efficient simulated evolution-based rerouting and congestion-relaxed layer assignment on 3-D global routing," IEEE Transactions on Very Large Scale Integration Systems (TVLSI), vol. 20, no. 3, pp. 459--472, 2012.

Digital Library

[17]

W.-H. Liu and Y.-L. Li, "Negotiation-based layer assignment for via count and via overflow minimization," in IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC), 2011, pp. 539--544.

Digital Library

[18]

J. Ao, S. Dong, S. Chen, and S. Goto, "Delay-driven layer assignment in global routing under multi-tier interconnect structure," in ACM International Symposium on Physical Design (ISPD), 2013, pp. 101--107.

Digital Library

[19]

T.-H. Lee and T.-C. Wang, "Simultaneous antenna avoidance and via optimization in layer assignment of multi-layer global routing," in IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2010, pp. 312--318.

Digital Library

[20]

O. Coudert, J. Cong, S. Malik, and M. Sarrafzadeh, "Incremental CAD," in IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2000, pp. 236--244.

Digital Library

[21]

C. Albrecht, "Efficient incremental clock latency scheduling for large circuits," in IEEE/ACM Proceedings Design, Automation and Test in Eurpoe (DATE), 2006, pp. 1--6.

Digital Library

[22]

H.-Y. Chang, I.-R. Jiang, and Y.-W. Chang, "Timing ECO optimization via Bézier curve smoothing and fixability identification," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 31, no. 12, pp. 1857--1866, 2012.

Digital Library

[23]

S. K. Karandikar, C. J. Alpert, M. C. Yildiz, P. Villarrubia, S. Quay, and T. Mahmud, "Fast electrical correction using resizing and buffering," in IEEE/ACM Asia and South Pacific Design Automation Conference (ASPDAC), 2007, pp. 553--558.

Digital Library

[24]

S. Roy, P. M. Mattheakis, L. Masse-Navette, and D. Z. Pan, "Clock tree resynthesis for multi-corner multi-mode timing closure," in ACM International Symposium on Physical Design (ISPD), 2014, pp. 69--76.

Digital Library

[25]

J. A. Roy and I. L. Markov, "ECO-system: Embracing the change in placement," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 26, no. 12, pp. 2173--2185, 2007.

Digital Library

[26]

T. Luo, D. A. Papa, Z. Li, C. N. Sze, C. J. Alpert, and D. Z. Pan, "Pyramids: an efficient computational geometry-based approach for timing-driven placement," in IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2008, pp. 204--211.

Digital Library

[27]

Y. Zhang and C. Chu, "GDRouter: Interleaved global routing and detailed routing for ultimate routability," in ACM/IEEE Design Automation Conference (DAC), 2012, pp. 597--602.

Digital Library

[28]

C.-H. Hsu, H.-Y. Chen, and Y.-W. Chang, "Multi-layer global routing considering via and wire capacities," in IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2008, pp. 350--355.

Digital Library

[29]

N. J. Naclerio, S. Masuda, and K. Nakajima, "The via minimization problem is NP-complete," IEEE Transactions on Computers, vol. 38, no. 11, pp. 1604--1608, 1989.

Digital Library

[30]

A. P. Ruszczyński, Nonlinear Optimization. Princeton university press, 2006, vol. 13.

Digital Library

[31]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall/Pearson, 2005.

Digital Library

[32]

R. G. Michael and S. J. David, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979.

Digital Library

[33]

M. Queyranne, "Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems," Operations Research Letters, vol. 4, no. 5, pp. 231--234, 1986.

Digital Library

[34]

A. D. Gunawardena, S. Jain, and L. Snyder, "Modified iterative methods for consistent linear systems," Linear Algebra and its Applications, vol. 154, pp. 123--143, 1991.

[35]

"LEMON," http://lemon.cs.elte.hu/trac/lemon.

[36]

"OpenMP," http://www.openmp.org/.

[37]

G.-J. Nam, C. Sze, and M. Yildiz, "The ISPD global routing benchmark suite," in ACM International Symposium on Physical Design (ISPD), 2008, pp. 156--159.

Digital Library

Cited By

Liu DYu BLivramento VChowdhury SDing DVo HSharma APan D(2019)Synergistic Topology Generation and Route Synthesis for On-Chip Performance-Critical Signal GroupsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.283442438:6(1147-1160)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TCAD.2018.2834424
Liu DZhao ZWang ZYing ZChen RPan D(2018)OPERONProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196084(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196084
Liu DLivramento VChowdhury SDing DVo HSharma APan D(2017)StreakProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062321(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062321
Show More Cited By

Index Terms

TILA: Timing-Driven Incremental Layer Assignment
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

Recommendations

TILA: Timing-driven incremental layer assignment
2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
As VLSI technology scales to deep submicron and beyond, interconnect delay greatly limits the circuit performance. The traditional 2D global routing and subsequent net by net assignment of available empty tracks on various layers lacks a global view for ...
MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...
MP-trees: a packing-based macro placement algorithm for mixed-size designs
DAC '07: Proceedings of the 44th annual Design Automation Conference

In this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '15: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design

November 2015

955 pages

ISBN:9781467383899

General Chair:
Diana Marculescu
Carnegie Mellon Univ., Dept. of Electrical and Computer Engineering, 5000 Forbes Ave., Pittsburgh, PA 15213, 412-268-1167
,
Program Chair:
Frank Liu
IBM Corp., IBM Austin Research Lab, 11501 Burnet Rd., MS 904-6G017, Austin, TX 78758, 512-286-7267

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Press

Publication History

Published: 02 November 2015

Check for updates

Qualifiers

Tutorial
Research
Refereed limited

Conference

ICCAD '15

Sponsor:

SIGDA

ICCAD '15: IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN

November 2 - 6, 2015

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
139
Total Downloads

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

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu DYu BLivramento VChowdhury SDing DVo HSharma APan D(2019)Synergistic Topology Generation and Route Synthesis for On-Chip Performance-Critical Signal GroupsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.283442438:6(1147-1160)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TCAD.2018.2834424
Liu DZhao ZWang ZYing ZChen RPan D(2018)OPERONProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196084(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196084
Liu DLivramento VChowdhury SDing DVo HSharma APan D(2017)StreakProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062321(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062321
Liu DYu BChowdhury SPan D(2016)Incremental layer assignment for critical path timingProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898033(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898033

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