基於導線寬度與位置調整之交談雜訊與延遲最佳化

Abstract

基於導線寬度與位置調整之交談雜訊與 延遲最佳化 研究生：謝孟桓 指導教授：張耀文 博士 國立交通大學資訊科學研究所 摘要 隨著尺寸的減小、較高的時序和連接線密度，交談雜訊在數位IC中變成與時間（timing）同等重要的影響因素。因此，在超大型積體電路設計中同時降低交談雜訊與延遲就變成了一項重要的考量。在深次微米的領域中，交談雜訊在全域繞線或通道繞線中的影響變的愈來愈大，這與傳統的繞線問題不同。交談雜訊通常有負面的影響，並且導致電路發生無法預期的行為；因此為了確保電路功能的正確性，每條線路（net）的交談雜訊必須盡可能的減少。為了降低交談雜訊，我們可以縮小線寬來增加線與線之間的距離；然而，這將會使得線路延遲增加。另一方面，假如一條線路的線寬變大了（每條線段有較大的線寬），則在線路中的每條線段的延遲都將會變小，因此線路可以在較高的頻率下工作；然而，這卻會增加交談雜訊。另一個改變交談雜訊的方法是：利用導線位置調整來改變導線之間的距離或是互相相鄰且平行的長度。在做導線位置調整的同時，也改變了被移動導線段的上游與下游導線段的電容負載，因此進而影響線路的延遲。這個導線寬度與導線位置的調整對交談雜訊和延遲的影響，就是繞線所要解決的問題。本論文的目的就是希望能夠在線寬與導線位置限制的前提下，同時將交談雜訊與延遲做最佳化。 目前已經有多項文獻從事這方面的研究，其處理交談雜訊的方法大致用在全域繞線階段或是繞線後置處理階段。在全域繞線階段中，由於交談雜訊是用預測的，因此會產生誤差，進而導致繞線結果可能無法被接受。在後置處理階段中，交談雜訊更精確地被測量；但是由於大量的限制條件與非線性的特徵，以致於難以找到有效率的演算法來做最佳化。在本論文中，我們考慮調整導線位置與導線寬度來最小化交談雜訊與延遲。首先，我們將一條線路（net）轉換成一棵繞線樹（routing tree）；接著，將調整位置的範圍按照某種方式切割，這將會使得目的函式（objective function）在被切出來的各個小調整範圍中擁有monotonic或unimodal的特性[12]；最後，我們在不需要解決任何非線性等式的情況下，使用我們的反覆（iterative）演算法來解決線路位置與寬度的問題。根據我們實驗的結果顯示，我們可以在平均增加延遲4.90％的情況下，減少交談雜訊平均達8.55％。

With decreasing feature sizes, higher clock rates, and increasing interconnect densities, crosstalk is getting a greater concern of comparable importance to timing in digital integrated circuits. Consequently, simultaneous reduction of crosstalk and delay becomes an important consideration in VLSI design. Unlike the traditional routing problem, crosstalk in global routing or channel routing becomes larger in deep sub-micron era. Crosstalk usually have negative effects, and thus incur unexpected circuit behavior. To guarantee the proper functioning of a circuit, crosstalk for each net should be as small as possible. To reduce crosstalk, we can reduce wire width to increase the distance between the wire and the neighboring ones.However, this would increase the delay of the net. On the other hand, if the wire width of a net becomes larger,the delay of each wire segment in the net becomes smaller, and thus nets can be operated at higher frequency. However, this would increase crosstalk.To change crosstalk, we also can use wire perturbation to change the position of wires. This changes the distance or the overlapped length between wires. At the same time, wire perturbation also makes the load of the upstream and downstream wires change, and hence change the delay of the net. These effects of wire sizing and perturbation on crosstalk and signal delay presents a routing problem:How to optimize crosstalk and delay concurrently under wire width and position constraints? Most previously proposed methods deal with crosstalk problem either in the global routing phase or in the post-layout phase. In the global routing phase, because the exact positions of nets are undetermined, crosstalk is only approximate and thus the routing result may be unacceptable.In the post-layout phase, crosstalk can be measured in more accuracy. But due to the large numbers of constraints and the nonlinearity of the constraints, it is difficult to optimize crosstalk by using efficient algorithms.In this thesis, we consider adjusting wire position and wire width to minimize crosstalk and delay. We first formulate a net as a routing tree.Like the work in [12], we divide the whole perturbation range into sub-intervals. The objective function in each sub-interval is either monotonic or unimodal.We then apply an iterative algorithm to solve the net position and sizing problem without solving any non-linear equations.Experimental results show that our method can achieve an average reduction of 8.55% in crosstalk with an average increase of 4.90% in delay.