Integer Linear Programming-based ECO Approach with Wire Length Consideration

基於線性規劃為基礎考量連線長度之ECO演算法

10.29948/JAE.201010.0009

陳漢忠(H. C. Chen)；黃信雄(H. H. Huang)；謝財明(T. M. Hsieh)

工程修改問題 ； 線性規劃方程組 ； 連線總長度 ； 備用晶元選擇 ； 虛擬點 ； engineering change order ； integer linear programming ； total wire length ； spare cell selection ； virtual node

先進工程學刊

5卷4期（2010 / 10 / 01）

347 - 355

英文

本論文提出一以線性規劃為基礎的方法，將備用晶元選擇問題成功轉換成資源分配問題。本論文的最佳化目標是針對給定工程修改內容，搜尋緩衝器備用晶元以達成工程修改，並且最小化連線總長度。為了加速演算法的執行時間，本論文提出一以插入虛擬節點為考量之新搜尋方法，考量連線中點和所有備用晶元的座標，有效率搜尋最短連線總長度的晶元配置解。本論文所提的方法成功將電路特性轉換成線性方程組，連線組將能描述：每一工程修改問題僅能使用單一備用晶元、單一備用晶元僅能配置給單一之工程修改；若有些連線插入緩衝器依然時序違反，則再執行一次ILP線性模組。針對連線方程組使用商用軟體Lingo求得最小連線長度之晶元配置。實驗結果顯示：本論文所提線性規劃為基礎的方有效率且有效地減少工程修改所需之連線總長度。

This paper identifies an integer linear programming-based approach with regards to the spare cells selection as the problem of resource allocation. The objective aims to search the spare cell assignment with minimization of total wire length. A novel wire length estimation method is proposed to accelerate the runtime of the proposed approach. In the proposed method, only the virtual node, i.e. the location of buffer insertion (middle point in this work) of the interconnection and the spare cells are taken into account for acquiring the spare cell assignment with the minimization of total engineering change order in length. If the timing violations still appear, the procedure will insert buffer again by performing the ILP formulations. The circuit characteristics, including the demand of each engineering change order and the supply of spare cell resource, could be successfully integrated into the ILP formulations. Experimental results showed that the proposed integer linear programming-based approach significantly minimized the total wire length.