考慮圍籬區域及大型方塊阻礙物之細部繞線驅動之擺置

Detailed Routing-Driven Placement with Fence Regions and Macro Blockages

蘇信元(Xin-Yuan Su)

指導教授 ： 林柏宏

國立中正大學/工學院/電機工程學系/碩士(2016年)

摘要

繞線驅動擺置的問題已經被研究很長一段時間而且被非常多的文獻解決了。但是針對細部繞線驅動擺置的研究成果非常少，甚至是加上圍籬區域的考量。考慮圍籬區域的擺置在本研究中為一個新的問題定義。在這篇論文裡，我們提出一個考慮圍籬區域擺置問題的解法。這其中包含 (1)基於區域的群集技術、(2)針對不同圍籬區域限制的依序擺置、(3)迭代的基於區域的擺置，主要是為了破除依序擺置後的結果的品質受限、(4)一個啟發式的方法於擺置合法化的階段來粗略地符合設計規定的要求。然而，一些高複雜度的測試基準電路在我們的演算法中並沒有辦法有效地解決。雖然我們最後的結果無法在ISPD 2015 的競賽中達到前三名，但我們的實驗結果也已經從比賽繳交的版本中作出了很大的改善，而且我們的擺置器，也於ISPD 2015 的競賽中在總分上獲得了第四名的殊榮。

關鍵字

細部繞線驅動之擺置 ； 圍籬區域 ； 解析式擺置 ； 基於區域的群集 ； 可繞度

並列摘要

The routability-driven placement problem has been studied for a long period and handled by so many researches. But the solution to detailed routability-driven placement is few and even to the region constraints. The placement with region constraints is defined as a new problem formulation in this work.
In this thesis, a new solution to deal with the placement problem with region constraint and is proposed. It contains (1) region-based clustering, (2) placement sequence among different regions to handle the region constraints, (3) iterative region-based placement to break the quality limitation after placement sequence among the different regions (4) a heuristic method in the legalization stage to solve the design rules roughly. However, there are some benchmarks we could not solve effectively due to the high complexity of the designs. Although the quality of our results could not achieve to the top three teams in the ISPD 2015 Contest, our experimental results have been improved a big progress from the submitted version in the contest. And our placer also achieves the 4th total score in the ISPD 2015 Contest.

並列關鍵字

Detailed Routing-Driven Placement ； Fence Regions ； Analytical Placement ； Region-based Clustering ； Routability

參考文獻

[1] K.-T. C. Laung-Terng Wang, Yao-Wen Chang, Ed., Electronic Design Automation:

[7] M.-C. Kim, J. Hu, D.-J. Lee, and I. Markov, “A SimPLR method for routability-

[9] X. He, T. Huang, W.-K. Chow, J. Kuang, K.-C. Lam, W. Cai, and E. Young, “Ripple

2.0: High quality routability-driven placement via global router integration,” in

Proceedings of ACM/IEEE Design Automation Conference, May 2013, pp. 1–6.