深次微米技術下之連線最佳化

Abstract

在深次微米技術下，晶片尺寸的增加導致導線 (interconnect) 的長度日益增長， 同時邏輯閘 (gate) 和邏輯閘之間以及導線和導線之間的距離也越來越接近。此 趨勢導致傳輸線 (transmission line) 以及交談雜訊 (crosstalk) 的效應日益重要。 在本論文中，我們考慮兩個在深次微米技術下的連線最佳化的問題： （1）如何在傳輸線的模型下（transmission line model）進行效能最佳化的問題， 以及（2）在 Elmore 時間延遲模型（Elmore Delay Model) 下，在滿足交談雜訊的 限制下之效能最佳化的問題。 · 傳輸線模型下效能最佳化問題： 隨著晶片尺寸的增加以及訊號波長的逐漸接近導線長度，導線的傳輸效應於 計算電路延遲時逐漸扮演重要的角色。本論文中，根據傳輸線模型，我們利 用改變導線寬度以及邏輯閘大小的技術來進行延遲的最佳化。我們證明一條 導線路徑上的時間延遲函數是導線寬度或是邏輯閘尺寸的上凹函數 (convex function)， 這種函數函數中，一個區域的最佳解 (local optimum) 就等於是全域的最佳解 (global optimum)。 同時由於這種向上凹的特性 (convexity)，我們可以應用快速的搜尋演算法 如梯度搜尋演算法 (the gradient search procedure) 去計算時間延遲最佳化的 導線寬度以及邏輯閘的大小。 · Elmore 時間延遲模型下，在滿足交談雜訊限制下之效能最佳化的問題： 在滿足交談雜訊限制下，我們利用改變導線寬度 (wire sizing) 以及移動導線 位置 (wire perturbation) 的技術，來進行繞線延遲最佳化。此一演算法可以應 用到一般的繞線結構。我們的演算法包含兩個步驟：我們首先移動導線線段 使時間延遲最小，並滿足交談雜訊的限制條件，接著我們在滿足交談雜訊以 及面積的限制條件之下，調整導線的寬度去更進一步減少延遲時間。這一個 統合改變導線寬度以及移動導線位置的技術具有 unimodality 的特性，此特性 代表有僅有唯一的最佳解的位置可以導致最佳的延遲以及最小的交談雜訊。 運用這樣的特性可以大幅的降低搜尋的範圍，也因此可以快速的去計算最佳 的導線寬度以及導線的位置。針對 0.18 mm 以及 0.25 mm 這兩個製程技術的 實驗結果顯示，我們的演算法可以分別的達到平均44.5% 及44.2% 的延遲時間 的改進。我們並提出一套有效率的部分更動的技巧 (incremental update) 來提升 我們的執行速度。根據實驗，可以提昇執行速度達十倍。

In the very deep sub-micron technology, the lengths of interconnects are getting longer and devices are packed in ever-closer proximity. This trend makes the transmission line and crosstalk effects very significant. In this thesis, we consider the two interconnect optimization problems which arise from the very deep submicrion technology: performance optimization in the transmission line model and crosstalk-constrained performance optimization under the Elmore delay model. · Performance optimization in the transmission line model: As chip size increases and signal wavelengths approach wire lengths, transmission line properties of on-chip interconnections are getting more important in determining circuit performance. We present in this thesis formulas for optimizing delay by simultaneously sizing wires and buffers under the transmission line model. We show that the delay of a circuit path is a convex function of wire/buffer sizes, implying that a local optimum is equal to the global optimum. Due to the convexity, we can apply any efficient search algorithm such as the well-known gradient search procedure to compute the global optimal solution. Experimental results show the effectiveness of simultaneous wire and buffer sizing under the transmission line model. · Crosstalk-constrained performance optimization under the Elmore delay model: We also propose a unified wire sizing and perturbation algorithm for crosstalk-constrained performance optimization that is applicable to general routing structures. Our algorithm is based on a two-stage iterative technique: we first perturb all wire segments to the positions with the minimum delay, subject to the crosstalk constraint, and then we adjust the wire sizes to further optimize delay under crosstalk and area constraints. The unified wire sizing and perturbation technique has the property of unimodality, implying that there is a unique position resulting in the optimal delay and crosstalk. Applying these properties can dramatically reduce the search space and thus lead to a very efficient method to locate the best wire position and to determine the optimal wire size. Experimental results show that our algorithm can achieve average improvements of 44.5% and 40.2% in delay without sacrificing area and crosstalk for the 0.18 $\mu m$ and 0.25 $\mu m$ process technologies, respectively. Further, we develop an effective incremental update technique that can substantially speed up the runtime. Empirically, this technique can reduce runtime by 10 times.