串擾效應導向和RLC串擾上限的軌道分配演算法

Abstract

隨著超大型積體電路製程的長足進步，現今的積體電路設計已經發展到超微米(VDSM)製程的時代。現在所設計出來的晶片尺寸越來越小，也使得電路繞線的間距變得越來越近，並且電路接線的寬度也相對應地變小。再者，因為積體電路設計的時脈持續在增加當中，目前晶片設計的時脈已經發展到了十億赫茲(Gigahertz)以上。因此，基於以上的理由，使得我們在設計高效能晶片的時候，必須考慮到串擾效應(Crosstalk effect)為電路設計所帶來的有關於電路完整性和正確性的問題。 之前做軌道分配的相關方法，是以區域為基礎的方法。這種以區域為基礎的 方法，可能會產生較差軌道利用率的軌道分配結果。在這篇文章中，我們提出了兩個串擾導向的軌道分配演算法。首先提到的，是考量到電容串擾效應的以列為基礎的軌道分配演算法。RBTA首先利用最左邊端點演算法來增加軌道的利用率，接著，我們提出了一個軌道重疊圖的新概念。藉著軌道重疊圖，我們就能將電容串擾導向的軌道分配問題，轉化為尋找最小成本漢米爾頓路徑(MWHP)的問題，也就是實現了針對串擾導向軌道分配問題，所產生的最佳軌道排序。在實驗數據中顯示出，相較於以前的方法，RBTA可以減少平均32.33%的電容串擾效應。與之前的方法相比較，RBTA也能夠得到較佳軌道利用率的軌道分配結果。 第二個串擾導向的軌道分配演算法，就是針對串擾上限問題，分別考量到電容和電感串擾效應的串擾上限導向演算法(RLC-bounded TA)。我們選擇了以區域為基礎的軌道分配方式來實作這個演算法。我們的演算法由兩個步驟所組成。首先是第一個步驟，利用了我們的啟發式找結黨的演算法。我們將IRoute重疊圖中所找到的結黨，由大到小依序來做處理。我們將結黨相對應的IRoute做軌道分配的動作，產生了一個軌道分配的初步解。接著是第二個步驟，如果，這個結黨中已經分配好的IRoute有產生電感串擾效應的話，我們就用限制搜尋的方法，來進一步地減少電感串擾效應值。在我們的實驗中顯示，當訊號線影響率為25%，33%，和50%時，在和第一步驟完成後的串擾成本值比較，電感串擾值分別平均減少了66.9%，62.80%，和55.44%。因此，我們知道限制搜尋方法對電感串擾值有明顯的減少作用。而且，訊號線影響率越高的，電感串擾值減少率越低。

In this work, we have proposed crosstalk-driven and RLC-bounded track assignment algorithms. First, RBTA first applies LEA to produces a utilization-driven TA, and then transforms the crosstalk minimization problem into finding a MWHP by the proposed new track overlap graph. Experimental results show that RBTA algorithm reduced crosstalk 32.33% and produced fewer failed nets than previous works. In second, we proposed an enhanced finding clique heuristic. For each clique in IRoute OLG in the decreasing order of clique size, RLC-bounded TA first apply initial assignment to produce a capacitance-free TA result, and then if inductance coupling occurred, we use Tabu search to reduce inductance coupling more. Experimental results show that Tabu search phase reduced inductance coupling 66.9%, 62.80% and 55.44% when the sensitive rate is 25%, 33% and 50%, respectively. In the future, we hope to develop a row-based RLC-bounded track assignment algorithm.