Maze Routing with Minimum Cost Buffer Insertion under Slew and Obstacle Constraints

迷宮繞線與在迴轉率及障礙物限制下作最小成本之緩衝器嵌入

李尚貽(Seong-I Lei)

指導教授 ： 麥偉基

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

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

摘要

隨著先進的超大型積體電路(VLSI)技術，鮮明的迴轉率和低功率消耗在積體電路設計中是極其須要的。在非時序關鍵的線路上作時序緩衝器嵌入只會導致額外的功率損耗和資源浪費。很不幸地大部分前作仍然選擇優化時間延緩而非單獨處理迴轉率限制。在一些相關的作品中，[7]提出一條公式作迴轉率的模型，而[5]則使用以電容為基礎的迴轉率模型，其中並沒有考慮到線路的電阻率。在這一篇論文中，我們學習了對兩點線路同時作繞線與緩衝器嵌入的基本問題。我們提出了兩個最理想的迷宮繞線與在迴轉率及障礙物限制下作最小成本的緩衝器嵌入的演算法，同時我們在這兩個演算法中採用兩種不同的迴轉率模型。除了對功率或全部緩衝器尺寸作最小化外，我們的演算法還能夠處理其他的緩衝器成本。跟迷宮繞線與作優化時間延緩的緩衝器嵌入的作品[2]比較下，我們的演算法比他們的快了超過一個數量級。實驗結果證明了我們的MCSB演算法是非常有效率的，以及其執行時間並不太會受迴轉率限制的影響。

關鍵字

迴轉率 ； 緩衝器嵌入 ； 迷宮繞線

並列摘要

With the advanced VLSI technology, sharp slew rate and low power comsumption are often required in integrated circuit design. Timing buffering on non-critical nets may result in extra power dissipation and waste of buffering resource.
Unfortunately, most previous works still optimized for delay instead of handling the slew constraints independently. For the related works, [7] proposed an equation to model slew while [5] used a capacitance-based slew model without considering interconnect resistivity.
In this paper, the elementary problem of simultaneous routing and buffer insertion for two-pin nets is studied. We propose two optimal polynomial time algorithms for maze routing with minimum cost buffer insertion under slew and obstacle constraints and we employ two different slew models in our algorithms. Besides minimizing power/total buffer size, our algorithms can also be adapted to handle other buffering costs. It is more than an order of magnitude faster than maze routing with buffer insertion for optimal delay [2]. Experimental results demonstrate that our MCSB algorithm is very efficient and the runtime is insensitive to the slew constraints.

並列關鍵字

Slew constraints ； Buffer insertion ； Maze routing

參考文獻

[1] S. Hu, C.J. Alpert, J. Hu, S. Karandikar, Z. Li, W. Shi and C.N. Sze, ``Fast Algorithms For Slew Constrained Minimum Cost Buffering,'' in Proc. DAC, pp.308-313, 2006.

[2] H. Zhou, D. F. Wong, I. Liu and A. Aziz, ``Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Locations,'' in Proc. IEEE Trans. on CAD, vol.19, No.7, pp.819-824, July 2000.

[3] M. Lai and D. F. Wong, ``Maze Routing with Buffer Insertion and Wiresizing,'' in Proc. DAC, pp.374-378, 2000.

[4] L. Huang, M. Lai, D. F. Wong and Y. Gao, ``Maze Routing with Buffer Insertion Under Transition Time Constraints,'' in Proc. DATE, pp.702-707, 2002.

[5] C.J. Alpert, A.B. Kahng, B. Liu, I. Mandoiu and A. Zelikovsky, ``Minimum-Buffered Routing of Non-Critical Nets for Slew Rate and Reliability Control,'' in Proc. ICCAD, pp.408-415, 2001.