應用序列對法之平面規劃

Abstract

對於VLSI設計方面而言，平面規劃是一個很重要的步驟。大部分已知的平面規劃方法只考慮可切割的結構 (slicing structure)，而這個可切割的結構是由水平或垂直的切割線循環式 (recursively) 地分割而成。但是，此結構通常限制得太過嚴謹以致於我們無法精確地描述邏輯區塊。為了能夠正確地描述真實的邏輯區塊，我們希望可以使用不可切割的結構 (non-slicing structure) 來處理平面規劃的問題。在許多不可切割結構的系統化表示法之中，因為序列對法 (sequence pair) 對於處理平面規劃問題具有的優越特性而使其顯得日趨重要。 以序列對法為基礎而發表出來關於平面規劃方面的成果，大部分都只有處理外形不可改變的邏輯區塊 (hard module)，意即，長與寬皆固定的區塊。如此一來往往造成晶片面積使用率的低落。因此，可以處理外形可改變的邏輯區塊 (soft module) 的平面規劃方法對於達到更佳效能的設計是很重要的。 本篇論文中，我們提出了一個經驗法則來處理外形可改變區塊的平面規劃問題，而這個方式是由序列對衍生而來。我們首先使用序列對法來表示邏輯區塊，接著我們定義了一種新式的交換法則 (perturbation of move)，使得我們可以運用冶煉法 (simulated annealing) 來搜尋較佳的平面規劃結果。另外，我們也把時脈的估計整合到序列對法之中一併計算。 根據我們的實驗數據顯示，與傳統的交換方式比較之下，我們的方式對晶元成本有著顯著的改善。例如，平均在晶片大小以及空白區域大小方面分別改善了 2.06% 以及 23.18%。另外，實驗結果同時顯示了我們的新方法與NSC'98 微處理機計畫所設計的平面規劃 (1999年四月版本) 的結果比較，在晶片面積大小以及時脈長度平均改善了 7.3% 以及 14%。

Floorplanning is an essential step in physical design. Most existing methods consider only the slicing structure, i.e., the structure can be bipartitioned into two slicing structures with a horizontal or vertical cutline, which is often too restricted to model real logic modules accurately. To precisely model real modules, it is desirable to use the non-slicing structure for floorplanning. Among the non-slicing formulations, the sequence pair formulation is getting very popular since its first introduction in 1995 due to its advantageous properties for handling module floorplanning. Most existing work on sequence pair based floorplanning only deal with hard modules, i.e. the modules with fixed width and height, resulting in inefficient area utilization. Approaches that can handle soft modules whose shapes can be adjusted are important to achieve better performance design. In this thesis, we address a new heuristic for soft modules floorplanning based on sequence pairs. We first represent logic modules by using the sequence pair structure, then we define a new type of perturbations of moves during simulated annealing to search for a good floorplanning. We also incorporate a timing estimation into the sequence pair representation for early timing planning. Experimental results show that our new perturbation scheme significantly outperforms the traditional perturbations of moves. For example, our new approach results in respective average reductions of 2.06\% and 23.18\% in chip size and dead space based on the sequence pair formulation, compared with the traditional perturbations of moves. Experimental results also show averages of 7.3\% and 14\% improvements in chip size and critical net length, compared with the version of NSC'98 microprocessor floorplanning released in April 1999.