4.5 Slicing Tree 與模擬退火：樓板規劃的組合優化#

從分區到擺放：floorplanning 的問題形態#

分區（4.1–4.4）決定「什麼跟什麼在一起」，floorplanning 決定「這些模組在晶片上如何擺、佔多大矩形」。形式化地：給定 \(n\) 個模組，各有一個面積（軟模組）或固定寬高（硬模組），要為每個模組指定一個不重疊的矩形位置，最佳化總面積、互連線長與長寬比。這是一個連續×離散混合的組合問題，早在 1960 年代即被證明與矩形切割 packing 問題同源，屬於 NP-hard。

早期 EDA 的解法是 slicing floorplan：只考慮可以用遞迴水平/垂直切割線切出來的佈局。1970 年代 Ohtsuki 與 Otten 等人的工作確立了這個模型的可計算性——slicing 佈局可以用一棵二元樹（slicing tree）編碼：內部節點是切法（水平 H 或垂直 V），葉子是模組。給定樹形與每片模組的形狀選項，可以由下而上在 \(O(n)\) 時間內算出最小包覆面積（Stockmeyer 在 1983 年證明軟模組的最優方向選擇可在多項式時間完成）。

Otten 在 1982 年（European Conference on Circuit Theory and Design）提出用後序遍歷的符號串——後來稱為 Polish expression——來編碼 slicing tree，並證明這種編碼使得「樹形空間」可以被一個線性大小的字串窮盡鄰域地走訪。Martin D. F. Wong 與 C. L. Liu 在 1986 年的 IEEE TCAD 期刊論文（會議版於 ICCAD 1985）〈A new algorithm for floorplan design〉把這個編碼發揚光大：他們證明任何 slicing tree 都對應一個 normalized Polish expression（不允許連續兩個相同切法符號、操作數在前運算子在後的後序式），且該表達式集合構成一個格狀的鄰域空間，任兩點可由有限個「M1 交換相鄰操作數、M2 反轉切法鏈、M3 平移運算子」三種 move 相連——換句話說，slicing 佈局的整個空間被壓縮成一個可以用局部 move 遍歷的組合空間。

模擬退火：來自統計力學的接受準則#

有了編碼空間，還需要搜尋策略。貪婪下降會困在局部極小，而 1983 年 IBM Thomas J. Watson 研究中心的 Kirkpatrick、Gelatt 與 Vecchi 在《Science》發表〈Optimization by simulated annealing〉，把 Metropolis 等人 1953 年在 Los Alamos 為模擬物質退火所提出的接受準則轉化為組合最佳化演算法：若新解成本較低就接受；若較高，以機率 \(e^{-\Delta C / T}\) 接受， \(T\) 為「溫度」，隨迭代緩慢下降。高溫時幾乎任何 move 都可接受（全域探索），低溫時趨近貪婪下降（局部精修）。Kirkpatrick 等人在論文中展示了它在電路放置與 VLSI 佈局上的威力，1980 年代 IBM 內部便以此建構實驗性自動佈局系統——統計力學的數學，成了晶片設計的生產工具，這是 EDA 史上最奇特的跨域移植之一。

Wong–Liu 1986 年的演算法正是兩者的合體：以 normalized Polish expression 為編碼、以三種 move 為擾動、以模擬退火為搜尋引擎。成本函數是

其中 wirelength 以模組質心間的半周長估計；aspect ratio 與 pin 位置約束可透過懲罰項加入。每次退火迭代：隨機挑一個 move，重算 slicing tree 的面積與線長（ \(O(n)\) ），依 Metropolis 準則決定接受與否。溫度排程上，Wong–Liu 用「上一輪接受的平均 \(\Delta C\) 估初始溫度、每輪以 0.85–0.95 的比例降溫、溫度夠低且連續數輪無改善即停」的標準排程。在 MCNC 基準（如 apte、xerox、ami33）上，Wong–Liu 演算法把 slicing 佈局面積做到接近最佳，成為此後十五年所有 floorplanning 論文的比較基準。

Wong-Liu SA:
  E = random normalized Polish expression
  T = T0 (估自初始平均 ΔC)
  repeat until frozen:
    repeat N times:
      E' = random_move(E in {M1, M2, M3})
      ΔC = cost(E') - cost(E)        # O(n) 由下而上重建
      if ΔC <= 0 or rand() < exp(-ΔC/T): E = E'
    T = r * T                        # r ∈ [0.85, 0.95]
  return best E seen

工程上的調校細節同樣具歷史價值。初始溫度的選取遵循 Kirkpatrick 的原始建議：先隨機做一批 move、取其平均 \(|\Delta C|\) ，令 \(T_0\) 使接受率落在 80% 到 95%。降溫比 \(r\) 在品質與時間之間取捨，Wong–Liu 實驗顯示 0.85 是性價比拐點；而「凍結判據」（連續數輪內最佳解無改善即終止）比固定輪數更符合退火的物理直覺。這套排程自此成為 EDA 文獻中 SA 實作的預設範本，被此後幾乎每一篇 floorplanning 論文原樣引用。

Slicing 的原罪#

Slicing 模型的優點是編碼小、move set 簡單、面積計算線性；但它排除了大量天然的非切片佈局。最著名的反例是 pinwheel 結構：四個模組沿中心旋轉排列，中央留一個十字交叉的走線通道——這種佈局無論如何都切不出來。隨著晶片上的巨集（SRAM、PLL、處理器核）越來越多樣，強迫 slicing 等於強迫面積浪費，業界開始追求能表達任意佈局、又能被退火有效搜尋的編碼。1990 年代後半，一連串非切片編碼競逐登場：sequence pair、O-tree、corner block list，以及本書下節的主角 B*-tree。它們如何延續 Wong–Liu 框架、又如何在編碼大小與 move 效率之間取捨，正是下一節的主題。