系統晶片及奈米技術下直角史坦那樹之建構

Abstract

直角史坦那最小樹是實體設計上的一個必要問題，此外，在製程上有不同的限制，包括障礙物的避開、多層繞線、特定層的繞線方向，在系統晶片及奈米技術下的直角史坦那最小樹的建構上是不能被忽略的。這篇論文首先統合單層及多層避開障礙物的直角史坦那最小樹的建立，之後將其延伸到考慮特定繞線方向以及時間驅動的直角史坦那最小樹。這些延伸說明了我們的演算法可以很容易的適用到這些結構上，實驗結果也顯示我們的演算法超越文獻中的最佳結果。

The rectilinear Steiner minimal tree (RSMT) problem is essential in physical design. Moreover, the variant constraints for fabrication issues, including obstacle avoidance, multiple routing layers, layer-specific routing directions, cannot be ignored during RSMT construction for modern SoC and nanometer technologies. This thesis unifies single- and multi-layer obstacle-avoiding RSMT construction first and then extends it to consider preferred routing directions and to target timing-driven RSMT. These extensions demonstrate that our algorithm can easily be adapted to configurations. Experimental results show that our algorithm is promising and outperforms the state-of-the-art works.