B*樹: 用於非切割平面規劃之新式表示法

Abstract

在這篇論文中，我們針對非切割平面規劃 (non-slicing floorplans)提出了一種具有高效率、高彈性及高效能的資料結構，稱作B*樹。B*樹是根據有順序性的二元樹及在 [1]中所提的admissible placement。由於承繼了有順序性二元樹的一些良好的特性，B*樹可以很容易的被實作出來，並且能在很快的時間內完成一些樹的基本運算，它能在常數的時間 (constant time)內完成搜尋及插入的動作，而在線性的時間 (linear time)內完成刪除的動作。相較之下，其他針對非切割平面規劃提出的表示法，均需花費至少線性時間來完成上述三種動作。除此之外，在admissible placement和它對應的B*樹之間存在著一對一的對應關係，而且它們之間的轉換只需要線性的時間來完成。有別於其他針對非切割平面規劃提出的表示法，需要建構constraint graphs來計算面積，B*樹可以根據它所對應的擺置，直接從B*樹的資訊來計算面積，而在計算時，只需部分更動B*樹的結構。而我們並將處理固定外形的邏輯區塊 (hard module)技術擴展到處理可旋轉的邏輯區塊 (rotated module) ，事先放置好的邏輯區塊 (pre-placed module) ，外形可改變的邏輯區塊 (soft module)及一般直線形的邏輯區塊 (rectilinear module) 。 根據MCNC測試資料的實驗結果顯示，在與O樹 [1]比較下，B*樹的速度快了4.5倍，節省60%的面積並得到面積較小的擺置結果。我們也運用simulated annealing在B*樹上，來得到更好的實驗結果，甚至連一般直線形的邏輯區塊，我們都可以用B*樹得到幾近最佳面積解。

We present in this thesis an efficient, flexible, and effective data structure, B*-trees, for non-slicing floorplans. B*-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the respective primitive tree operations search, insertion, and deletion in only O(1), O(1), and O(n) times while existing representations for non-slicing floorplans need at least O(n) time for each of these operations, where n is the number of modules. The correspondence between an admissible placement and its induced B*-tree is 1-to-1 (i.e., no redundancy); further, the transformation between them takes only linear time. Unlike other representations for non-slicing floorplans that need to construct constraint graphs for cost evaluation, in particular, the evaluation can be performed on B*-trees and their corresponding placements directly and incrementally. We further show the flexibility of B*-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B*-tree representation runs about 4.5 times faster, consumes about 60% less memory, and results in smaller silicon area than the O-tree one [1]. We also develop a B*-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules.