以平行化限制規劃解決含障礙物的最長路徑問題

Obstacle-Aware Longest-Path Routing with Parallel Constraint Programming Solvers

陳煥文(Huan-Wen Chen)

指導教授 ： 曾奕倫

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

https://doi.org/10.6838/YZU.2012.00010

摘要

在設計高效能印刷電路板時，我們可能會遇到需要繞出最長路徑的繞線問題，而這個問題已經被證明是一個NP-hard的問題。在本篇論文中，我們對於格狀的最長路徑繞線問題提出一個限制規劃表示法，此方法亦可以表示繞線問題中包含障礙物的情況。當一個最長路徑繞線問題被轉換成為一個限制規劃問題後，便可以使用平行化的限制規劃求解工具來尋找出最佳解。另外，我們也可以藉由找非最佳解來換取較少的求解時間。並且，我們提出的方法也可以用來解決最短路徑繞線問題。實驗結果顯示，透過平行化的求解工具並使用8個執行緒，執行時間最快可以達到9倍以上的加速效果。若一部電腦的處理器核心個數增加，則可能可以再進一步減少求解的時間。

關鍵字

最長路徑繞線問題 ； 限制規劃 ； 平行化 ； 印刷電路板

並列摘要

The longest-path routing problem, which can arise in the design of high-performance printed circuit boards (PCBs), has been proven to be NP-hard. In this thesis, we propose a constraint programming (CP) formulation to the gridded longest-path routing problem, which may contain obstacles. After an instance of the longest-path routing problem has been transformed into a CP problem, parallel CP solvers can be used to find optimal solutions. In addition, suboptimal solutions can be generated in exchange for reduced execution time. The proposed formulation method can also be used to solve the shortest-path routing problem. Experimental results show that more than 9X speed-up can be achieved by using 8 threads in solving a formulated instance of the longest-path routing problem. It is possible that the execution time can be further reduced if a computer containing more processer cores is available.

並列關鍵字

Longest-Path Routing Problem ； Constraint Programming ； Parallel ； PCB

參考文獻

[12] W. L. Winston, and M. Venkataramanan, Introduction to Mathematical Programming, Tomson Learning, Inc., 2003.

[3] T. Yan and M. D. F. Wong, “BSG-Route: A length-constrained routing scheme for general planar topology,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 28, no.11, January 2009, pp.1679-1690.

[5] Y. Kohira, S. Suehiro and A. Takahashi, “A fast longer path algorithm for routing grid with obstacles using biconnectivity based length upper bound,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E92-A, no.12, December 2009, pp.2971-2978.

[6] Y. Kohira, S. Suehiro and A. Takahashi, “A fast longer path algorithm for routing grid with obstacles using biconnectivity based length upper bound,” in Proceedings of Asia and South Pacific Design Automation Conference, January 2009, pp.600-605.

[7] J.-T. Yan, M.-C. Jhong, and Z.-W. Chen, “Obstacle-aware longest path using rectangular pattern detouring in routing grids,” in Proceedings of Asia and South Pacific Design Automation Conference, January 2010, pp.287-292.