以限制規畫與混和整數線性規畫為基礎之可避開障礙物的交換盒繞線器

Obstacle-Avoiding Switchbox Routers with Constraint Programming and Mixed Integer Linear Programming

李哲逸(Che-I Lee)

指導教授 ： 曾奕倫

元智大學/資訊學院/資訊工程學系/碩士(2011年)

摘要

交換盒繞線法是超大型積體電路設計自動化中的一種細部繞線方式；一個交換盒包含一個矩形的區域，以及外部一些需要做繞線的端點；交換盒繞線器會將屬於同一條線路的端點連接在一起。對一個存在多個端點的多條線路的交換盒繞線方法已經被正名是無法在有限時間內去求解，本論文以限制規畫和混和整數線性規畫的方式來表達我們所設置的限制式，並使用求解工具去求解，實驗數據顯示我們能對一個交換盒繞線問題求出他的最短路徑。我們更使用多核心的中央處理器來求解以提升執行效率。在使用十六個核心的時候可以得到八十四倍的加速效果。

關鍵字

可避開障礙物的交換盒繞線器 ； 超大型積體電路物理設計自動化 ； 限制規畫 ； 混和整數線性規畫

並列摘要

Switchbox routing is a type of problems arising in the detailed routing phase of VLSI physical design automation. A switchbox is a rectangular area and its boundary contains a number of terminals; each terminal belongs to a specific net. A switchbox router can connect all the terminals belonging to the same net and the router must complete the connection of each net. It has been proven that a switchbox routing problem containing multiple terminals and multiple nets belongs to the class of NP-complete. In this thesis, we present a constraint programming (CP) formulation and a mixed integer linear programming (MILP) formulation to switchbox routing problems. Therefore, CP solvers and MILP solvers can be used to find solutions. Experimental results show that more than 84X speed-up can be achieved by using a parallel MILP solver with 16 threads. The execution time can be further reduced when a computer containing more processor cores is available.

並列關鍵字

Obstacle-avoiding switchbox router ； VLSI physical design automation ； constraint programming ； parallel mixed integer linear programming

參考文獻

[1] Sherwani, N., “Algorithms for VLSI Physical Design Automation,” Springer, Third Edition, 1998.

[2] Yan, J.-T., Hsiao, P.-Y., “Minimizing the number of switchboxes for region definition and ordering assignment,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, pp. 336-347, 1996.

[4] Hartmann, S., Schaffter, M.W., Schulz, A.S., “Switchbox routing in VLSI design: Closing the complexity gap,” Theoretical Computer Science, 1998.

[6] Jin-Tai Yan and Pei-Yung Hsiao, “A general switchbox router with via minimization,” Proceedings of IEEE Region 10 Conference, pp. 574-577, 1993.

[7] Yan, J.-T and Hsiao, P.-Y, “CONVERGE: a circular-assignment-based switchbox router with via reduction,” IEE Proceedings on Computers and Digital Techniques, pp. 72-76, 1995.