考慮冗餘接點之電路線軌指派法

Redundant-Via Aware Track Assignment

蘇冠丞(Guan-Chan Su)

指導教授 ： 李毅郎

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2008年)

https://doi.org/10.6842/NCTU.2008.00063

摘要

傳統的冗餘接點安插是在後佈局階段來實現的，在繞線階段考慮冗餘接點的安插是勢在必行的。三階段的繞線系統對於處理大型的設計成為一種必需的系統。在這篇論文中，我們提出了第一個在電路線軌指派階段考慮冗餘接點影響的演算法(RATA)，並且將此演算法整合到一個三階段的繞線系統中。一個潛在接點的模型首先被提出。線段和接腳的相對位置被分成不同的類型。全域格點段落花費的提出使得在考慮冗餘接點安插的電路線軌指派法上更有彈性和效率。藉由持續的更新全域格點段落花費，反覆的執行最小二部配對法來得到指派的結果。繞線樹將會在電路線軌指派後被建立，並且用簡單且固定的典型連線來連接接腳和線段。在精細繞線之前，產生死亡接點的典型繞線將會被拔除。最後在精細繞線結束之後，套用一個後佈局的冗餘接點安插器來實現最後的冗餘接點安插以及得到冗餘接點安插率。
實驗結果顯示相對於沒有考慮冗餘接點的電路線軌演算法，我們在死亡接點的個數上平均減少了29%。冗餘接點的安插率則由99.54% 增為99.66%。此外此繞線系統和[12]的執行時間相比快了 1.84倍。

關鍵字

冗餘接點 ； 電路線軌指派法

並列摘要

Traditional redundant via insertion (RVI) is performed at post-layout stage and the effect of RVI is merely considered in detailed routing. Three-stage routing system becomes necessary for processing large-scaled designs. In this paper, we propose the first work to consider the effect of RVI in track assignment, and integrate the proposed redundant-via aware track assignment (RATA) algorithm into a three-stage routing system. A potential via (PV) model is first proposed. Iroutes and pins are then classified into different types according to their relative positions. GCell segment cost is also proposed to offer high flexibility and efficiency to evaluate the cost of assigning an iroute to a track with RVI consideration. RATA algorithm iteratively employs a minimum bipartite matching to identify the assignment with continuous updating GCell segment cost. Routing tree construction is executed following RATA to complete simple connection between iroutes and pins with fixed patterns. Before detailed routing, the pattern routing that yields dead vias is ripped up. After detailed routing, a post-layout RVI tool is applied to realized RVI and have the final RVI rate. Experimental results show that the number of dead vias is decreased by 29% in average as compared to the TA algorithm without RVI consideration. The final RVI rate is promoted from 99.54% to 99.66% by the proposed RATA algorithm. Besides, the complete routing system runs 1.84X faster than the work in [12].

並列關鍵字

redundant via ； track assignment

參考文獻

[1] Huang-Yu Chen, Mei-Fang Chiang, Yao-Wen Chang, Lumdo Chen, and Brian Han, “Novel Full-Chip Gridless Routing Considering Double-Via Insertion,” in Proc. of Conf. on Design Automation, pp. 755-760, 2006.

[2] Kuang-Yao Lee and Ting-Chi Wang, “Post-Routing Redundant Via Insertion for Yield/Reliability Improvement,” in Proc. of Conf. on Asia South Pacific Design Automation, pp.303-308, 2006.

[3] Kuang-Yao Lee, Ting-Chi Wang and Kai-Yuan Chao, “Post-Routing Redundant Via Insertion and Line End Extension with Via Density Consideration,” in Proc. of Int. Conference on Computer-Aided Design, pp.633-640, 2006.

[5] Shabbir Batterywala, Narendra Shenoy, William Nicholla, and Hai Zhou, “Track assignment: a desirable intermediate step between global routing and detailed routing,” in Porc. Int. Conf. on Computer Aided Design, pp. 59-66, 2002.

[6] Huang-Yu Chen, Szu-Jui Chou, Sheng-Lung Wang and Yao-Wen Chang, “Novel Wire Density Driven Full-Chip Routing for CMP Variation Control,” in Proc. Int. Conf. on Computer Aided Design, pp. 831-838, 2007.