以整數線性規劃演算法處理具有串音限制的河流繞線

An Integer Linear Programming Algorithm for Crosstalk-Constrained River Routing

隨著積體電路製造技術的進步，連線間的距離越來越小且電路工作頻率越來越高，使得串音雜訊對於積體電路效能甚至於產量之影響與日俱增。因此，降低連線間的串音已成為現今超大型積體電路設計的一個重要議題。在本文中，我們提出一個可減少串音影響之有格線河流繞線演算法。在我們的方法中，首先給定一個以傳統繞線演算法所求得之初始解，接著再以疊代的方式重新指派初始解中水平與垂直線段以降低串音值。為了有效與以最佳方式執行重新指派程序，我們嘗試以整數線性規劃演算法加以處理。此外，我們亦提出降低整數線性規劃之變數與限制數之技巧。實驗結果顯示本文所提出之整數線性規劃演算法具有相當之成效。針對所有測試例子，平均而言，整數線性規劃演算法能將整體繞線之抗串音雜訊能力提升約20%。另外，對每個測試例子而言，所有串音限制亦皆可滿足。 As advances in technology produce smaller interconnection wire spacing and higher circuit operating frequency, the effect of crosstalks on performance and even on yield in integrated circuit design and manufacturing thus increases rapidly. Consequently, reduction of crosstalks between interconnection wires has become important in VLSI (very large scale integration) design. In this paper, an approach for the gridded river routing problem with the objective of minimizing crosstalks is presented. Given an initial routing solution generated by a conventional river routing algorithm, the reduction of crosstalks is carried out by an iterative reassignment of the horizontal and vertical wire segments. To effectively and optimally perform the reassignment process, an integer linear programming (ILP) formulation is proposed in conjunction with procedures for reducing the number of variables and constraints. The experimental results show that the proposed ILP approach is very promising. On an average, this approach shows a 20% increment for total slack when comparing the initial solutions; moreover, all the crosstalk constraints are satisfied with some margins for each test example.