繞線長度取向置放暨邏輯閘尺寸重定與緩衝器植入

Interconnect-Length Driven Placement with Simultaneous Gate Resizing and Buffer Insertion

郭昆典(Kun-Tien Kuo)

指導教授 ： 林榮彬

元智大學/資訊學院/資訊工程學系/碩士(2000年)

摘要

為了減少一個VLSI電路之臨界路徑（critical path）的延遲，時序取向之實體設計方法已被廣泛地使用。這些方法可以被區分為網路權重取向（net-weight driven）、網路長度取向（net-length driven）或路徑延遲取向（path-delay driven），他們有時候會在佈局後或佈局中執行邏輯閘尺寸重定（gate resizing）、緩衝器植入（buffer insertion）或繞線寬度調整（wire sizing）。長久以來，很多的設計者都質疑網路長度取向方法之可行性，因為要讓實體設計工具滿足所有的網路長度限制是相當困難的。然而隨著處理內部繞線延遲之困難度的不斷增加，假如網路長度界限能隨著設計過程的進行而調整，如此網路長度取向的實體設計工具是可行的。所以，本篇論文的主旨是要發展一個網路長度取向之標準元件置放器（ILDPer）。
ILDPer利用一個遞迴最小切割（min-cut）分割的演算法來指導每一個元件的置放。在置放過程中，這個演算法會考慮每一對source-sink pair之延遲界限的響影。邏輯閘尺寸重定及緩衝器植入被採用來使得網路延遲界限更容易被滿足。假如有很多網路違反他們的界限，ILDPer會動態地重新計算網路延遲界限。界限重新計算會根據目前部分置放的結果來產生一組更容易實現的網路延遲界限。我們將ILDPer整合至Cadence Preview Silicon Ensemble以評估它的效能。三個MCNC測試電路被用來評估ILDPer的效能。根據實驗結果，電路的最長路徑之延遲可減少達41%。

關鍵字

置放 ； 時序取向 ； 實體設計 ； 繞線長度 ； 邏輯閘尺寸重定 ； 緩衝器植入 ； 最小切割 ； 延遲界限

並列摘要

Timing-driven physical design approaches have been widely used to reduce the critical path delay of a VLSI circuit. These approaches can be classified as net-weight, net-length or path-delay driven, sometimes accompanied by gate resizing, buffer insertion or wire sizing performed either post or during layout process. Net-length driven approach has been long questioned by many designers about its feasibility of satisfying the bound constraints by physical design tools. However, with ever increasing difficulty of managing interconnect delay, a physical design tool driven by net-length bounds may be viable if net-length bounds can be adapted for the progress of design process. Therefore, this thesis proposes to develop an Interconnect- Length Driven standard cell Placer (ILDPer).
A recursive min-cut partitioning algorithm, taking into consideration of the delay bound of each source-sink pair, is employed by the ILDPer to direct the placement of each cell. Gate resizing and buffer insertion are adopted to make interconnect-delay bounds easier to satisfy. If many bound violations occur, bound re-computation is dynamically invoked to generate a new set of more realizable bounds based on current partial placement. The ILDPer is integrated into Cadence Preview Silicon Ensemble to evaluate its performance. Three MCNC benchmark circuits are employed in evaluation. The experimental results show up to 41% of reduction in the longest path delay can be obtained.

並列關鍵字

placement ； timing-driven ； physical design ； interconnect length ； gate resizing ； buffer insertion ； min-cut ； delay bound

參考文獻

[3] T. Koide, M. Ono, S. Wakabayashi, Y. Nishimaru and N. Yoshida, “A new performance driven placement method with the Elmore delay model for Row Based VLSIs,” Proc. of the 32th Design Automation Conference, 1995, pp. 405-412.

[4] W. Donath et al., “Timing driven placement using complete path delay,” Proc. of the 27th ACM/IEEE Design Automation Conference, 1990, pp. 84-89.

[5] Masayuki Terai, Kazuhiro Takahashi and Koji Sato, “A new min-cut placement algorithm for timing assurance layout design meeting net length constraint,” Proc. of the 27th ACM/IEEE Design Automation Conference, 1990, pp. 96-102.

[9] Wing K. Luk, “A fast physical constraint generator for timing driven layout,” Proc. of the 28th ACM/IEEE Design Automation Conference, 1991, pp. 626-631.

[10] Kerry S. Lowe, and P. Glenn Gulak, “A joint gate sizing and buffer insertion method for optimizing delay and power in CMOS and BiCOMS combinational logic,” IEEE Trans. on Computer-Aided Design, Vol. 17, May 1998, pp. 419-434.