以限制規劃與混合整數線性規劃方式為基礎之線長匹配繞線

Obstacle-Aware Length-Matching Routing with Constraint Programming and Mixed Integer Linear Programming

高永威(Yung-Wei Kao)

指導教授 ： 曾奕倫

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

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

摘要

線長匹配繞線問題在設計高效能印刷電路板中是個相當重要的議題，屬於同一匯流排的導線可能會被要求必須在相當短時間差之內，傳送訊號至對應的端點。隨著時脈頻率的增加，此訊號延遲問題的影響會更嚴重。因此，在設計印刷電路板繞線時，可對這些相關的導線做長度匹配的條件限制，使這些導線必須盡可能達到長度一致的結果，如此可有效地達到降低訊號延遲的問題。由於線長匹配繞線問題是屬於 NP 困難的問題，我們使用了限制規劃與混合整數線性規劃的條件方式來設置條件式，使得起點至終點間的連線能夠正確被連結，並且使導線的長度能夠盡可能達到一致。另外，在長度一致的情況下，我們的方式可以縮短總線段長度。本論文中我們使用了不同的最佳化軟體套件 (包含可平行化執行的最佳化軟體) 來比較求解結果。從實驗數據顯示，使用平行化最佳化軟體最多可得到365倍的加速。另外，和一個參考文獻中的方式比較，本論文所提出混合整數線性規劃方式亦可減少變數的數量達 10% 和減少限制條件的數量達 67%。

關鍵字

線長匹配繞線 ； 限制規劃 ； 混合整數線性規劃

並列摘要

In the design of high performance printed circuit boards (PCBs), length-matching routing is one of the most important tasks. Nets which belong to the same bus may be required to consider signal propagation delay. When the clock frequency increases, the signal propagation delay problem will become more serious to affect the timing skew. The length-matching routing problem which contains multiple nets and multiple obstacles has been proven to be NP-hard. In this thesis, we propose an approach which is capable of transforming instances of the length-matching routing problem into constraint programming (CP) and into mixed integer linear programming (MILP) problems. As a result, commercial optimization tools can be used to find optimal and suboptimal solutions of those CP and MILP problems. Experimental results show that as high as 365x speed-up can be achieved when a parallel MILP solver is used to solve an instance of the length-matching routing problem on a computer containing 8 processor cores. Compared with a formulation method proposed previously in the literature, our MILP-based formulation method can effectively reduce the number of variables by 10% and the number of constraints by 67%.

並列關鍵字

Length-Matching Routing ； Constraint Programming ； Mixed Integer Linear Programming

參考文獻

[9] I-Lun Tseng, Huan-Wen Chen, Che-I Lee, and Adam Postula, “Constraint Based Dogleg Channel Routing with Via Minimization,” International Conference on Artificial Intelligence, 2010, pp. 666-672.

[7] W. L. Winston, and M. Venkataramanan, “Introduction to Mathematical Programming,” Thomson Learning, Inc., 2003.

[3] T. Yan and M. D. F. Wong, “BSG-route: A length-matching router for general topology,” IEEE Transactions on Computer-Aided Design. 2008, pp. 499-505.

[4] J. T. Yan, and Z. W. Chen, “Obstacle-Aware Length-Matching Bus Routing,” International Symposium on Physical Design, March 2011.

[5] Che-I Lee, Huan-Wen Chen, and I-Lun Tseng, “Obstacle-Avoiding Switchbox Routing with CP and Parallel MILP,” Annual International Conference on Advances in Distributed and Parallel Computing. 2010.