利用遞移封閉圖表示法處理巨集電路擺置

Abstract

由於矽智財(Intellectual Property)模組的普遍使用，巨集電路的數量在先進系統晶片(System-on-a-Chip)的設計中已大量增加，仰賴工程師手動擺置巨集電路的傳統設計流程已不符合現代需求。在本篇論文中，我們提出一個利用遞移封閉圖(Transitive Closure Graph)表示法來處理巨集電路擺置問題的演算法。它除了能有效地移除巨集電路間違反規則的重疊，亦可進一步最佳化巨集電路的擺置結果。為了縮短擺置時間，我們改進遞移封閉圖表示法，使得在只處理其必要之簡化邊的情況下，依然不降低擺置品質。相較於現有的巨集電路擺置方法僅能將電路擺置在晶片周圍，我們的演算法可利用線性規劃來得到一個非緊緻的擺置結果。而透過延伸原有之線性規劃，我們的演算法亦能輕易地來處理許多的擺置要求與達成不同的擺置目標。從實驗結果中可見，我們的演算法與各式領先的學術界擺置器整合後均可明顯並有效地縮短線長。

In this thesis, we propose a transitive-closure-graph-based (TCG-based) macro placement algorithm that removes macro overlaps and optimizes macro positions. Improving over TCG by working only on its essential edges without loss of the solution quality, our algorithm can efficiently and effectively search for a high quality macro geometric relation. Instead of packing macros along chip boundaries like the most recent previous work, our placer can determine a non-compacted macro placement by linear programming and placement region cost evaluation. Our macro placer is so flexible and versatile that it can easily extend the linear programming formulation to handle various placement constraints/objectives. Combined with various leading academic placers, our macro placer can consistently and significantly reduce the wirelength, implying that our macro placer is robust and has very high quality. For example, based on the ISPD’06 placement benchmarks, combined with our macro placer, the resulting wirelength of Capo 1.2, mPL6, and NTUplace3 can further be reduced by 5%, 6%, and 15% on average, respectively.