可避開障礙物之直角史坦那樹建構的平行化演算法

Parallel Algorithms for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction

張政源(Cheng-Yuan Chang)

指導教授 ： 曾奕倫

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

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

摘要

在積體電路實體設計自動化的領域中，可避開障礙物之直角極小史坦那樹(Obstacle-Avoiding Rectilinear Steiner Minimal Tree, or OARSMT) 建構的問題是一個基本的問題，而且，此問題已經吸引許多研究人員從事相關的研究。本論文提出三個建構OARSMTs的平行化演算法，這三個演算法都是採用 Maze routing和double front-wave expansion 的方式。在這些平行化演算法當中，第一個演算法是採用將繞線區域分割的方式。第二個平行化演算法以不切割繞線區域，並且使用平行化區域連線與平行化清除繞線資料的技巧。第三個演算法則是採用繞線區域壓縮的方法。由實驗結果顯示，第二個平行化演算法不僅可以產生相當短的總繞線長度的結果，而且還能有效地減少在具有共享記憶體架構的多核心電腦系統上執行的時間。

關鍵字

傳播 ； 返回 ； 平行化清除 ； 平行化連線 ； 繞線

並列摘要

In the field of integrated circuit physical design automation, the problem of obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is a fundamental problem and has attracted a lot of research attention. In this thesis, three parallel algorithms for constructing OARSMTs are proposed. These algorithms are based on maze routing and double front-wave expansion. The first proposed algorithm uses the method of partitioning the original routing region into smaller regions. With regard to the second algorithm, the original routing region is not partitioned. However, a technique for concurrent connections of wires within small regions and a technique for cleaning up partial routing information are used. The third algorithm uses the approach of compressing the original routing region into another region with fewer coordinates. Experimental results show that the second parallel algorithm not only generates very short wires, but also performs efficiently on shared-memory multi-core computer systems.

並列關鍵字

Routing ； Propagate ； Backtrack ； Parallel-CleanUp ； Parallel-Connect

參考文獻

[11]Yung-Tai Chang, Ya-Wen Tsai, Jun-Cheng Chi, Mely-Chen Chi, “Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction,” In Proceedings International Symposium on VLSI Design, Automation & Test, pp. 35-38, 2008. (EI). (Best Paper Nomination).

[6]Yu Hu, Tong Jing, Xianlong Hong, Zhe Feng, Xiaodong Hu, Guiying Yan. “An-OARSMan: Obstacle-Avoiding Routing Tree Construction with Good Length Performance,” In Design Automation Conference. Proceedings of the ASP-DAC 2005. Asia and South Pacific, 2005, pp. 7-12 Vol. 1.

[1]Lee, “An algorithm for path connection and its application,” IRE Trans. Elec- tronic Computer, EC-10, 1961

[2]M. Garey and D. Johnson, “The rectilinear Steiner tree problem is NP-Complete,” SIAM Journal of Applied Mathematics, pp. 826–834, 1977.

[3]Takumi Watanabe, Hitoshi Kitazawa, and Yoshi Sugiyama, “A Parallel Adaptable Routing Algorithm and its Implementation on a Two-Dimensional Array Processor,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-6, No. 2, March 1987, pp. 241-250.