高品質多層障礙物排除之直角史坦那樹之建置

Abstract

在現今的超大型積體電路設計，障礙物越來越多，加上多層的繞線平面考量，使得繞線變得更加複雜與困難。傳統單一繞線層，使用障礙物排除之直角史坦那樹來處理繞線的問題。單一層的障礙物排除之直角史坦那樹已經被證明是一個NP完備問題。因此考量多層的障礙物排除之直角史坦那樹是更為複雜的問題。本篇研究提出一高品質的多層障礙物排除之直角史坦那樹的建置方法。該方法會對繞線層上的點作評估，根據評估結果會許出一組合適的史坦那點集合，進一步形成史坦那樹。之後再依據初步的結果做線長的改進。實驗結果與 [6] 比較，在導通孔的成本設為3的環境下，結果的品質能改進 1.8% ~ 3.91%。而在導通孔的成本設為5的環境下，結果的品質能改進 0.97% ~ 4.81%。

Single layer obstacles-avoiding rectilinear Steiner minimal tree (SL-OARSMT) has been generally applied to route nets. In modern VLSI designs, pins and obstacles, such as Intellectual Property (IP) blocks, macro blocks, power networks, pre-routed nets, etc are more and more. Besides, multiple routing layers has been considered. Therefore, this study develops an effective multi-layer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) construction algorithm for modern designs. The proposed algorithm mainly comprises the initial tree construction stage and the tree topology refinement stage. A novel maze routing based Steiner-Points evaluation is used to identify a set of good Steiner points to construct initial tree. And a novel rip-up and re-select scheme to improve the final result. Experimental results show that the proposed algorithm effectively improves the total wire-length by 1.8% ~ 3.91% under the condition that via cost is 3, and 0.97% ~ 4.81% under the condition that via cost is 5 over [6].