1997-多層分區#

案件摘要#

FM 演算法（1982）線性時間，但仍有局部性缺陷：只看「當前割的鄰居」——百萬節點的圖，FM 一次 pass 從單一起點看不到全局結構，解的品質隨規模惡化。1997 年，明尼蘇達的 George Karypis 等人（hMetis）與 IBM 的 Alpert 等人（MLPart）同時提出多層分區：先「粗化」（coarsen，反覆把節點配對合併成超節點，圖縮小百倍）→ 在最粗層跑 FM → 「反粗化」（uncoarsen，逐層展開並局部精修）。這個「先縮後放」的粗化-反粗化典範，讓分區品質首次隨規模穩定甚至改善——hMetis 成為分區的事實標準，典範更蔓延到佈局（mPL、NTUplace）、聚類、圖學習等整個大圖處理領域。

前因 -- 為什麼會有這個案子#

• FM 的局部性：FM 一次 pass 只搬「割線附近」的節點；大圖的全局結構（社群、聚類）在局部視野外——需要「先看全局、再修局部」。
• VLSI 規模爆炸：1990s 晶片達百萬閘；min-cut 佈局的反覆分區呼叫 FM 數千次，品質瓶頸放大。
• 計算科學的平行先例：多重網格法（multigrid, 1970s）在偏微分方程求解用「粗網格校正 + 細網格平滑」——同構思想已在數值領域驗證。
• 聚類理論就緒：圖的匹配（matching）、重邊合併的粗化技巧已在圖論成熟。

線索與推理 -- 數學式、程式、理論#

核心：粗化-反粗化三階段#

1. 粗化（coarsening）：反覆用最大匹配（heavy-edge matching）把節點兩兩合併——偏好合併重邊相連的節點（它們應屬同側）；每層圖縮小約一半，數十層後圖只剩數百節點；
2. 初始分區：在最粗層跑 FM——小圖上 FM 接近全局；
3. 反粗化（uncoarsening/refinement）：逐層展開，每層用 FM 局部精修——粗層的決定指引細層的搜尋方向。

為什麼有效：多重網格的推理#

多重網格的數學：誤差的高頻分量在細網格上局部平滑、低頻分量在粗網格上才看得到——FM 在細圖上只能修高頻錯誤，粗層的 FM 修低頻（全局）錯誤。多層分區把兩者組合：粗層定全局骨架，細層修局部細節。

這是數值分析（multigrid）→ 組合最佳化的又一次跨界移植——與模擬退火（統計力學）、DAGON（編譯器）同屬「物理/數學回歸」主線。

為什麼品質隨規模穩定#

顯式枚舉與單層 FM 的解品質隨規模惡化（局部性）；多層方法的粗層是 \(O(\text{層數}) = O(\log n)\) 級的「全域視野」，故解品質隨規模平緩——這是大圖處理渴望的「規模不變性」。

hMetis 的工程#

Karypis 等把三階段工程化：heavy-edge matching、FM 的超圖版（hMetis 處理超邊）、隨機多重重啟取最好——成為 VLSI 分區的事實標準（頁面評測中常年第一）。

結案 -- 後果與影響#

• 分區標準二十年：hMetis 至今仍是學術與工業分區的基準工具；所有現代分區器（KaHyPar、TritonPart）都沿用粗化-反粗化。
• 典範蔓延到佈局：min-cut 佈局（mPL、NTUplace）全盤採用多層架構——「先粗後細」成為大規模佈局的核心思想。
• 與解析法的交會：多層分區提供初始解，解析佈局（Kraftwerk、ePlace）精修——混合架構成為現代佈局器標配。
• 多重網格的第二春：multigrid 思想後續進入 ePlace（2015，多層靜電求解）與圖神經網路的池化（pooling）——同一推理在 AI 時代繼續繁衍。

關鍵人物與文獻#

• George Karypis：明尼蘇達大學，hMetis 與 METIS 庫作者，圖分區/聚類大家。
• Charles J. Alpert：IBM，MLPart 與分區理論綜述。
• 文獻：
• G. Karypis, R. Aggarwal, V. Kumar, S. Shekhar, "Multilevel Hypergraph Partitioning: Application in VLSI Domain," DAC 1997.
• C. J. Alpert, L. W. Hagen, A. B. Kahng, "Fast Hierarchical Multilevel Circuit Partitioning," IEEE TCAD 16, 773 (1997)（MLPart 前身）。
• W. Hackbusch, Multi-Grid Methods and Applications, 1985（多重網格理論）。