利用重新繞線做擁塞辨識的緩衝器插入

Congestion Aware Buffer Insertion with Re-routing

黃致豪(Zhi-Hao Haung)

指導教授 ： 麥偉基

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

https://doi.org/10.6843/NTHU.2006.00398

摘要

隨著超大型積體電路技術的快速發展，晶片的複雜度快速的增加，而且導線及邏輯閘的數目大量的成長。想在有限的晶片空間裡，達到滿足時間(timing)的要求而做繞線與擺放緩衝器變的非常困難。另外，當我們自動化插入緩衝器和繞線時，聰明地考慮擁塞程度(congestion)的管理變成是必要的條件。在這篇論文中，我們的貢獻是提出一個新的演算法，取名為CABIR，藉由在初始的Steiner tree上做重新繞線以降低繞線擁塞成本，並且產生一些緩衝器候選位置，它們有著最低總和的擺放擁塞成本。然後，我們利用所產生的低擁塞成本的樹和在樹上的一些低擺放擁塞成本的緩衝器候選位置，當作van Ginneken演算法的輸入。跟PRAB的演算法比較後[13]，實驗結果顯示我們的方法可以分別降低時間，繞線擁塞成本和擺放擁塞成本達到2%，4%和28%。而且我們的執行時間也很快。

關鍵字

緩衝器候選者 ； 擺放擁塞 ； 繞線擁塞

並列摘要

With the rapidly progress of VLSI technology, the complexity of a chip critically increases and the enormously growth of wires and gates, it becomes difficult to place buffers and route wires to meet timing in a limited space. In addition, it becomes necessary to consider congestion management intelligently while we insert buffers and route wires automatically. In this thesis, our contribution is to propose a new algorithm called CABIR to reduce the routing congestion cost by re-routing the initial Steiner tree and to generate some buffer candidate locations with the lowest total placement congestion cost. Then we pass the low congestion routing tree along with a set of low density buffer candidate locations as the input of the van Ginneken’s algorithm. Compare with the PRAB algorithm [13], the experimental results show that our approach is able to reduce timing, routing congestion cost and placement congestion cost up to 2%, 4% and 28% respectively. Also our runtime is fast.

並列關鍵字

buffer candidate ； placement congestion ； routing congestion

參考文獻

[1] J. Cong and D. Z. Pan,“Interconnect Delay Estimation Models for Synthesis and Design Planning,”in Proc. Asia and South Pacific Design Automation Conference, pp. 97-100, 1999.

[2] C. J. Alpert, A. Devgan, and S. T. Quay,“Buffer Insertion for Noise and Delay Optimization,”in Proc. Design Automation Conference, pp. 362-367, 1998.

[5] L. P. P. P. van Ginneken,“Buffer placement in distributed RC-tree networks for minimal Elmore delay,”In Proc. International Symposium on Circuits and Systems, pp. 865-868, 1990.

[6] J. Lillis, C. K. Cheng, and T. T. Y. Lin,“Optimal wire sizing and buffer insertion for low power and a generalized delay model,”In IEEE International Conference on Computer Aided Design, pp. 138-143, 1995.

[7] C. J. Alpert and A. Devgan,“Wire Segmenting For Improved Buffer Insertion,”in Proc. Design Automation Conference, pp. 588-593, 1997.