擺置階段評估繞線完成度的有效率區域壅塞模型

An Efficient Local-Congestion Model for Routability Estimation in Placement

龐立遠(Li-Yuan Pang)

指導教授 ： 劉建男 ； 陳泰蓁

國立中央大學/資訊電機學院/電機工程學系/碩士(2015年)

摘要

隨著超大型積體電路的快速演進，電路的可繞度（Routability）問題愈趨嚴重。一般在繞線階段時才能準確得知電路可繞度之資訊，然而若此時才發現電路的可繞度不足，在設計上會浪費大量的時間重新進行擺置與再繞線。因此若在擺置階段就考慮電路的可繞度資訊並能及時發現問題，即可避免時間的浪費。
為了精準的預估可繞度，本篇論文採用全域繞線研究做為基底，但目前絕大部分的全域繞線研究皆沒有考慮細部繞線階段可能產生的壅塞問題，這導致即使完成了全域繞線，仍有相當大的機率無法得到無壅塞（Congestion-free）的細部繞線結果。因此，本篇論文提出了適用於擺置階段的快速區域壅塞模型（Local congestion model），搭配適合在擺置階段使用的快速全域繞線器，能夠提早預知區域壅塞的情形，並且提早迴避壅塞區域（Congested region），或者識別不可繞（Unroutable）的電路。實驗結果顯示，本篇論文所提出的方法可以在短時間內預估電路的區域壅塞，使得全域繞線器可以提早得知細部繞線階段之可繞度資訊。

關鍵字

區域壅塞

並列摘要

With the advances of Very-Large-Scale Integration circuits, the routability problem has become more and more significant. Conventionally, circuit routability can only be evaluated precisely after routing stage. However, if the routability is not sufficient, it will waste lots of time to re-place and re-route. Thus, routability evaluating in placement stage is important to discover potential routing problems and avoid redesign efforts.
For accurate routability evaluation, this thesis proposes a method based on global routing. However, most of the global routing researches didn’t consider the possible congestions occurred in the detailed routing stage. It is possible that congestion-free detailed routing results are still not available. Therefore, a fast local congestion model for placement stage is proposed in this thesis. Combined with a fast global router, the proposed fast local congestion model can predict the distribution of routing congestion to avoid congested regions and identify unroutable circuits. Experimental results showed that the proposed model can obtain local congestion information fast in placement stage and help the global router to evaluate the routability of the circuits.

並列關鍵字

Local Congestion

參考文獻

[3] Z. Cao, T. Jing, J. Xiong, Y. Hu, L. He, and X. Hong, "DpRouter: A Fast and Accurate Dynamic-Pattern-Based Global Routing Algorithm," Proc. Asia and South Pacific Design Automation Conf., pp.256-261, Jan. 2007.

[4] W. H. Liu, Y. L. Li, and C. K. Koh, "A Fast Maze-Free Routing Congestion Estimator With Hybrid Unilateral Monotonic Routing," Proc. Intl. Conf. on Computer-Aided Design, pp.713-719, Nov. 2012.

[5] 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 Trans. on Computer-Aided Design and Integrated Circuits and Systems, pp.709-722, May 2013.

[7] M. K. Hsu, Y. F. Chen, C. C. Huang, S. Chou, T. H. Lin, T. C. Chen, and Y. W. Chang, “NTUplace4h: A Novel Routability-Driven Placement Algorithm for Hierarchical Mixed-Size Circuit Designs,” IEEE Trans. on Computer-Aided Design and Integrated Circuits and Systems, pp. 1914-1927, Dec. 2014

[8] M. Cho and D. Z. Pan, "BoxRouter: a new global router based on box expansion and progressive ILP," Proc. ACM/IEEE Design Automation Conf., pp.373-378, Jul. 2006.