多層次超大型模組之放置與平面規劃

Abstract

在這篇論文中，我們提出一個基於B*-tree表示法之多層次架構去處理大量模組的平面規劃及晶片放置，稱作MB*-tree。MB*-tree採用兩階段的技術─先群集再反群集。在群集的階段根據面積及模組的連通性利用quadratic programming (Lagrangian relaxation)反覆將硬(軟)的模組群組起來，同時利用B*-tree建立模組之間的幾何關係。而在反群集的階段，反覆地解開被群集的模組(也就是執行樹的延展)，然後再調整平面規劃及放置的結果。在反群集階段，MB*-tree保留了模組之前的幾何關係，這個特性使得MB*-tree對多層次平面規劃與放置而言成為非常理想的資料結構。在實驗中，顯示MB*-tree的結果不會隨著電路複雜度大小而有所顯著變化，而其他知名研究報告─Sequence pair，O-tree及B*-tree則不然。在處理電路大小範圍為49至9800個模組、408至81600條訊號線時，MB*-tree在時間近似線性成長的情況下，獲得高品質的平面規劃，其未使用空間不大於3.72%。而Sequence pair、O-tree及B*-tree在相同的時間下卻分別只能處理196、196及1960個模組的電路，且未使用空間高達27.33%以上。

We present in this thesis a multilevel floorplanning/placement framework based on the B*-tree representation, called MB*-tree, to handle the floorplanning and packing for large-scale building modules. The MB*-tree adopts a two-stage technique, clustering followed by declustering. The clustering stage applies quadratic programming (Lagrangian relaxation) to iteratively groups a set of hard (soft) modules based on a cost metric guided by area utilization and module connectivity, and at the same time establishes the geometric relations for the newly clustered modules by constructing a corresponding B*-tree for them. The declustering stage iteratively ungroups a set of the previously clustered modules (i.e., perform tree expansion) and then refines the placement/floorplanning solution by using a simulated annealing scheme. In particular, the MB*-tree preserves the geometric relations among modules during declustering, which makes the MB*-tree an ideal data structure for the multilevel floorplanning/placement framework. Experimental results show that the MB*-tree scales very well as the circuit size increases while the famous previous works, sequence pair, O-tree, and B*-tree, do not. For circuit sizes ranging from 49 to 9,800 modules and from 408 to 81,600 nets, the MB*-tree consistently obtains high-quality floorplans with dead spaces of less than 3.72% in empirically linear runtime, while standalone sequence pair, O-tree, and B*-tree can handle only up to 196, 196, and 1,960 modules in the same amount of runtime and result in the dead spaces of as large as 27.33%.