基於整數線性規劃之最小化多餘線段全域性繞線器

ILP-based Global Router for Dangling-wire Minimization

蔡梅香(Mei-Hsiang Tsai)

指導教授 ： 劉一宇

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

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

摘要

由於半導體製程技術的進步，在製作晶片的成本上相對地也越來越昂貴，尤其是光罩的成本。因此可以重複使用光罩的設計架構便逐漸受到重視，以達到節省成本的目的，FPGA和structured ASIC即是目前熱門的設計型態。在本論文中我們將在structured ASIC及crossbar switch block這樣的架構之下，對因線段在switch block轉彎時會產生的多餘線段進行探討，而這些多餘線段我們稱之為dangling-wire。由於這些dangling-wires會造成電路的繞線能力變差及導線的延遲時間變長使得電路效能降低。因此避免電路效能變差，本論文提出兩種ILP-based global router來降低電路上dangling-wire產生的數量，並在此兩種ILP router中皆加入routing resource使用量的考量。第一種ILP router為concurrent ILP router，我們將電路中所有的two-pin nets透過此router的concurrent ILP formulation做一次性的全盤考量及最佳化，藉此縮減電路中的dangling-wires。從實驗結果來看我們可以發現與Heuristic router [1]相比，我們在加入routing resource的考量且不加上ripup-reroute機制時，在dangling-wire的部份我們縮減了33.1%，而在routing resource的使用量部份則是減少了14.21%；第二種ILP router為sequential ILP router，由於第一種concurrent ILP router的runtime需要非常大量的時間，因此基於runtime的考量，我們提出了另一種net by net的sequential ILP formulation。與Heuristic router相比，sequential ILP router在加入routing resource的考量且不加上ripup-reroute機制時，在dangling-wire部份我們得到了25.47%的降低及8.3%的routing resource使用量的改善，並且比起concurrent ILP router，sequential ILP router擁有較快速的runtime。

關鍵字

整數線性規劃 ； 繞線

並列摘要

With the increasing chip manufacturing cost, via-programmable structured ASIC becomes a promising design style to amortize mask cost among different designs. Crossbar switch is one of the most area efficient switch architecture for structured ASIC. In this thesis, we study the dangling-wire issue for crossbar switch. The dangling-wire occurs when there is a routing bend in crossbar switch and impacts routability and circuit performance. We proposed two ILP-based global routers, concurrent ILP router and sequential ILP route, to reduce the dangling-wires taking routing resource utilization into consideration. In concurrent ILP router, we minimize the dangling-wires and routing resource for all two-pin nets simultaneously. The experimental results demonstrate that our concurrent ILP router improves 33.1% dangling-wires and 14.21% channel width as compare to a heuristic router [1], but the run time of our concurrent ILP router is 380X over the heuristic router. In order to reduce the runtime, we then propose a fast and net-by-net sequential ILP router. The experimental results demonstrate that our sequential ILP router reduces 25.47% dangling-wires and 8.3% routing resource as compare to the heuristic router, and the run time is 29X over the heuristic router.

並列關鍵字

ILP ； router ； FPGA

參考文獻

[2]. C. Chu, Y. C. Wong, "FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design", in IEEE Transactions on Computer-Aided Design of Integrated Circuit and Systems, vol.27, no.1, pp.70-83.

[3]. Y. Ran, M. Marek-Sadowska, "Via-configurable routing architectures and fast design mappability estimation for regular fabrics", in IEEE Transactions on Very Large Scale Integration Systems, vol.14, no.9, pp.996-1009, 2006.

[1]. Y. H. Hung, H. Y. Li, P. Y. Hsu, Y. Y. Liu, "Dangling-wire avoidance routing for crossbar switch structured ASIC design style", in Proceedings of IEEE International Symposium on VLSI Design, Automation, and Test (VLSI-DAT), pp. 177-180, 2010

[4]. CPLEX: http://www-01.ibm.com/software/integration/optimization/CPLEX-optimizer/