5.4 VPR 的模擬退火：FPGA 擺放三十年不敗的溫度排程#

當 ASIC 世界從 force-directed 走向 ePlace 的分析式方法時，FPGA 的擺放引擎卻始終堅守另一個典範：模擬退火（simulated annealing, SA）。這個典範的載體是多倫多大學（University of Toronto）Jonathan Rose 團隊開發的 VPR（Versatile Place and Route）。理解 VPR 的 SA，不僅是理解一個演算法，更是理解「問題結構決定方法選擇」的絕佳案例。

VPR 的誕生：1990 年代的多倫多#

VPR 最初的學術版本見於 1990 年代後期：Jonathan Rose 與其學生 Vaughn Betz（VPR 1.0 的主要實作者，後與 Alexander Marquardt 合作）在 1999 年發表了系統性的描述（Betz 與 Rose 的系列論文，最終彙整為 Betz、Rose、Marquardt 等人的專書 Architecture and CAD for Deep-Submicron FPGAs, 1999）。VPR 與同時期的 CAD 工具鏈（用於 FPGA 架構研究的 VPack/T-VPack、以及後來的 ABC 綜合前端）共同構成了一個完整的學術 FPGA CAD 流程，其設計哲學是「架構無關」——使用者以 XML 描述 FPGA 架構，VPR 就能在該架構上執行擺放與繞線，因此它成為三十年来 FPGA 架構研究的標準評測平台。Betz 之後加入 Altera，把 VPR 的思想帶入商業工具；VPR 本身則由多倫多大學持續維護演進（VPR 6、VPR 7、VPR 8，加入 timing-driven 與最新架構支援），今日的開源 FPGA 工具鏈（如 nextpnr 的部分思想、以及眾多架構研究論文）仍以 VPR 為對照基準。

模擬退火在 VPR 中的形狀#

模擬退火源自 Kirkpatrick、Gelatt 與 Vecchi 1983 年的經典論文（以及 Černý 1985 年的獨立工作），其物理原型是冶金學的退火：固體先加熱至高溫使原子自由移動，再緩慢降溫使系統落入低能量晶格。演算法對應如下：狀態＝一個擺放；能量＝成本函數；溫度 \(T\) ＝接受劣化移動的機率尺度。VPR 的 SA 骨架：

p = 隨機初始擺放;  T = 初始溫度 T_0
while T > T_end:
    for i in 1..N_moves:            # 每個溫度做大量移動
        隨機選取移動類型 (swap / move)
        計算 ΔC (成本變化, 通常只更新局部)
        if ΔC < 0 or random() < exp(-ΔC / T):
            接受移動
    更新溫度與每溫度移動數
    if 長期無改善: 提前降溫或終止
return 歷史最佳擺放

VPR 的移動集以 swap 為主：隨機挑兩個邏輯塊（logic block）互換位置；當其中一方佔用多個 site（cluster 化的 block）時則是帶位移約束的 swap。成本函數是三項加權和：

第一項是 bounded net bounding box 線長（對 FPGA 的繞線資源分佈做修正的 HPWL 近似， \(q(e)\) 是依 net pin 數校正的係數）；第二項是 timing 項，把時序關鍵路徑上的連接以 criticality 加權計入，使 SA 傾向把關鍵路徑拉近；第三項是擁塞項，懲罰繞線資源超載的區域。三個 \(\lambda\) 權重與 criticality 的更新由外層的 timing analyzer 反覆回饋——這是 placement 與 timing 分析交織的典型做法。

溫度排程：VPR 的真正秘方#

SA 的理論保證（Geman 與 Geman 1984 的收斂定理）要求降溫慢到 \(T_k \sim c/\log k\) ，實務上完全不可行。VPR 的成功在於一套精調的工程化排程：

初始溫度並非拍腦袋決定，而是透過「採樣移動」自動校準——先做一組試探移動，測量 \(\Delta C\) 的平均絕對值，令 \(T_0\) 使初始接受率落在目標（約 0.44 附近，這個數字源自 White 1984 年對等溫平衡的研究）。之後每個溫度層執行大量移動（內部迴圈長度隨電路大小成長），並以動態機制調整：VPR 追蹤最近移動的成本變化統計，當接受率過低或過高時縮短內部迴圈提前降溫。降溫函數採用混合式：早期用幾何降溫 \(T \leftarrow \alpha T\) （ \(\alpha \approx 0.5\) ，快速粗降），後期轉為緩慢降溫以精修。此外，VPR 的 \(\Delta C\) 計算是增量的——一個 swap 只影響少數 net，成本變化可局部計算，使單一移動的評估是 \(O(1)\) 到 \(O(k)\) 而非整個電路重掃。這使得 SA 的每秒移動數達到百萬級，是「便宜移動＋大量試錯」策略成立的基礎。

初始化溫度:
  做 S 次試探移動, 記錄 |ΔC| 樣本
  T_0 使 exp(-Δ̄C / T_0) ≈ 0.44   →   T_0 ≈ 1.5 × mean(|ΔC|)

為何 SA 在 FPGA 上二十年不敗#

FPGA 擺放與 ASIC 標準 cell 擺放有本質差異，這決定了方法選擇。第一，FPGA 的 site 是離散且異構的：每個 CLB 的輸入接腳有固定位置，開關盒（switch box）資源分佈不均，HPWL 在這裡只是粗略代理，分析式方法賴以成立的「連續密度場」假設很弱。第二，FPGA 擺放的組合約束極強：block 類型必須與 site 類型匹配，swap 是自然的鄰域移動，而分析式方法需要額外的「散開→對齊」兩階段，且對齊損失大。第三，也是常被忽略的一點：SA 對成本函數幾乎沒有要求——線長、時序、擁塞可以任意混搭非凸非線性的項，這對 FPGA 這種「成本很難寫成光滑函數」的問題特別寬容。

學界並未停止嘗試分析式方法：1990 年代末至 2000 年代，出現過以二次線長＋合法化為骨架的 FPGA 擺放研究（如針對叢集式 FPGA 的 partition-based 與 quadratic 方法），以及後來把 ePlace 思想移植到 FPGA 的嘗試（在開源工具如 nextpnr 的 veryl 生態中也偶有實驗）。這些方法在純線長上偶有勝出，但一旦加入真實的時序與繞線資源約束，往往被 VPR 的 SA 加上繞線器（router）的組合流程追平甚至反超——因為 SA 能與 timing 反覆迭代收斂。截至 2020 年代，SA 仍是 FPGA placement 的 baseline 與大多數商業工具（Xilinx/AMD 與 Intel 的工具鏈皆大量使用退火式移動）的核心。這段歷史提醒我們：演算法的「理論優雅」與「工程勝出」是兩回事，問題的離散結構有時比數學光澤更有決定權。

從流程來看，無論 ASIC 或 FPGA，SA 或分析式方法產出的都是「非法」的擺放——cell 重疊、或偏離 site 格點。把它變成合法布局的最後一哩，就是下一節的主題：legalization。