›› 2015, Vol. 30 ›› Issue (3): 614-628.doi: 10.1007/s11390-015-1515-4

Special Issue: Computer Architecture and Systems

• Regular Paper • Previous Articles     Next Articles

Design-Rule-Aware Congestion Model with Explicit Modeling of Vias and Local Pin Access Paths

Zhong-Dong Qi(祁仲冬), Student Member, IEEE, Yi-Ci Cai(蔡懿慈), Senior Member, CCF, IEEE, Qiang Zhou(周强), Senior Member, CCF, ACM, IEEE   

  1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  • Received:2014-03-31 Revised:2014-10-14 Online:2015-05-05 Published:2015-05-05
  • About author:Zhong-Dong Qi is a Ph.D. candidate in the Department of Computer Science and Technology of Tsinghua University, Beijing. He received his B.E. degree in computer science from the same university in 2009. His current research interests include physical design automation of VLSI and parallel algorithms.
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61274031. A preliminary version of the paper was published in the Proceedings of CAD/Graphics 2013.

As technology advances, there is a large gap between traditional congestion model used in global routing and routing resource consumption in detailed routing. The new factors contributing to congestion include local pin access paths, vias, and various design rules. In this paper, we propose a practical congestion model with measurement of the impact of design rules, and resources consumed by vias and local pin access paths. This congestion model is compatible with path search algorithms used in global routing. Validated by experiments using full-flow routing, this congestion model correlates better with real resource consumption situation in detailed routing. Compared with previous work, it leads to much better solution quality and shorter runtime of detailed routing when it is used in layer assignment phase of global routing stage.

[1] Albrecht C. Global routing by new approximation algorithms for multicommodity flow. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2001, 20(5): 622-632.

[2] Roy J A, Markov I L. High-performance routing at the nanometer scale. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(6): 1066-1077.

[3] Pan M, Xu Y, Zhang Y, Chu C. FastRoute: An efficient and high-quality global router. VLSI Design, 2012, 2012: Article ID 608362.

[4] Moffitt M D. MaizeRouter: Engineering an effective global router. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(11): 2017-2026.

[5] Chang Y, Lee Y, Gao J, Wu P, Wang T. NTHU-Route 2.0: A robust global router for modern designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(12): 1931-1944.

[6] Hsu C, Chen H, Chang Y. Multilayer global routing with via and wire capacity considerations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(5): 685-696.

[7] Taghavi T, Alpert C, Huber A, Li Z, Nam G, Ramji S. New placement prediction and mitigation techniques for local routing congestion. In Proc. IEEE/ACM International Conference on Computer-Aided Design, November 2010, pp.621-624.

[8] Wei Y, Sze C C N, Viswanathan N, Li Z, Alpert C J, Reddy L N, Huber A D, Téllez G E, Keller D, Sapatnekar S S. GLARE: Global and local wiring aware routability evaluation. In Proc. the 49th ACM/EDAC/IEEE Design Automation Conference, June 2012, pp.768-773.

[9] Shojaei H, Davoodi A, Linderoth J T. Planning for local net congestion in global routing. In Proc. International Symposium on Physical Design, March 2013, pp.85-92.

[10] Lee C Y. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers, 1961, EC-10(3): 346-365.

[11] Moore E F. The shortest path through a maze. In Proc. International Symposium on the Theory of Switching, April 1957, pp.285-292.

[12] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[13] Kastner R, Bozorgzadeh E, Sarrafzadeh M. Pattern routing: Use and theory for increasing predictability and avoiding coupling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, 21(7): 777-790.

[14] Lee T, Wang T. Congestion-constrained layer assignment for via minimization in global routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(9): 1643-1656.

[15] Lee T, Wang T. Robust layer assignment for via optimization in multi-layer global routing. In Proc. International Symposium on Physical Design, March 2009, pp.159-166.

[16] Liu W, Li Y. Negotiation-based layer assignment for via count and via overflow minimization. In Proc. the 16th Asia and South Pacific Design Automation Conference, January 2011, pp.539-544.

[17] Cho M, Lu K, Yuan K, Pan D Z. BoxRouter 2.0: A hybrid and robust global router with layer assignment for routability. ACM Transactions on Design Automation of Electronic Systems, 2009, 14(2): Article No. 32.

[18] Hu J, Roy J A, Markov I L. Completing high-quality global routes. In Proc. the 19th International Symposium on Physical Design, March 2010, pp.35-41.

[19] Dai K, Liu W, Li Y. 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, 2012, 20(3): 459-472.

[20] Liu W, Kao W, Li Y, Chao K. NCTU-GR 2.0: Multithreaded collision-aware global routing with boundedlength maze routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32(5): 709-722.

[21] Viswanathan N, Alpert C J, Sze C C N, Li Z, Wei Y. The DAC 2012 routability-driven placement contest and benchmark suite. In Proc. the 49th ACM/EDAC/IEEE Design Automation Conference, June 2012, pp.774-782.

[22] Liu W, Koh C, Li Y. Case study for placement solutions in ISPD11 and DAC12 routability-driven placement contests. In Proc. ACM International Symposium on Physical Design, March 2013, pp.114-119.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Jin Lingzi; Zhu Hong;. Systems Programming in the Functional Language FP[J]. , 1988, 3(1): 40 -55 .
[2] Ma Zhifang;. DKBLM——Deep Knowledge Based Learning Methodology[J]. , 1993, 8(4): 93 -98 .
[3] Xiong Zhiguo; Xu Xi; Dong Shihai;. CX11: A Chinese Language Supporting Interface for X Window Environment[J]. , 1995, 10(1): 15 -22 .
[4] Yu Shengke;. Reasoning in H-Net: A Unified Approach to Intelligent Hypermedia Systems[J]. , 1996, 11(1): 83 -89 .
[5] Peng Chenglian;. Combining Gprof and Event-Driven Monitoring for Analyzing Distributed Programs:A Rough View of NCSA Mosaic[J]. , 1996, 11(4): 427 -432 .
[6] Zhao Zhuxing; Min Yinghua; Li Zhongcheng;. Path Sensitization[J]. , 1997, 12(3): 271 -282 .
[7] Schubert Foo; Siu Cheung Hui;. System Architectural Design for DeliveringVideo Mail over the World-Wide-Web[J]. , 1997, 12(4): 372 -385 .
[8] Li Bin; Liang Xundong; Liu Shenquan;. A Surface Rendering Approach in 3D Rectilinear Datafield[J]. , 1998, 13(3): 220 -227 .
[9] Ji-Gang Wu and Thambipillai Srikanthan. Power Efficient Sub-Array in Reconfigurable VLSI Meshes[J]. , 2005, 20(5): 647 -653 .
[10] Thomas Luft and Oliver Deussen. Real-Time Watercolor for Animation[J]. , 2006, 21(2): 159 -165 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved