3.6 技術映射的 ASIC 之路：Pattern Matching 與 Cut-based 映射#

從布林網路到標準元件庫#

多級優化（3.5 節）產出一張與工藝無關的布林網路：節點是 AND/OR/NOT 這類抽象運算。但晶片是用具體的 cell 蓋出來的——standard cell 庫裡有 NAND2、NOR3、AOI21、MUX、DFF，每個 cell 有自己的面積、delay、功耗。技術映射（technology mapping）就是把布林網路的每個部分替換成庫裡的 cell，使某個目標函數（面積、延遲、功耗）最佳。這是邏輯綜合流程的最後一個主要階段，也是 1980 年代末至 1990 年代商業 EDA 最賺錢的戰場。本節講 ASIC 側的演算法譜系：從 1987 年的 Dagon 到 cut-based mapping。

Library、Pattern Matching 與 Tree Covering#

映射問題的形式化需要三個要素。其一，library（單元庫）：每個 cell 用一個布林函數描述，例如 AOI21 = \(\overline{a(b+c)}\) 。其二，subject graph：布林網路的規範表示，1980 年代常用 NAND-DAG（全部由 NAND2 與反相器組成的有向無環圖）。其三，覆蓋（covering）：用 library 中 cell 的 pattern（同為 NAND-DAG 的小子圖）去覆蓋 subject graph，每個被覆蓋區域對應一個 cell 實例，覆蓋成本 = 面積或延遲之和。

這本質上是子圖同構（subgraph isomorphism）問題，NP-hard。1987 年 Kurt Keutzer 在 Berkeley（其博士論文完成於此，隨後任職 AT&T Bell Labs）發表的 Dagon 系統給出了使問題可解的兩大簡化：第一，把 subject graph 分解成森林——對每個有多個 fanout 的節點切開（tree partitioning），每棵樹獨立映射；第二，在單棵樹上用動態規劃（tree covering）：自底向上，對每個節點枚舉所有能匹配的 pattern（pattern matching 預先離線完成——把每個 cell 的函數表示成 canonical form 做比對），記錄該節點以各 pattern 覆蓋其子樹的最小成本。因為樹的後繼結構唯一，局部最佳即全局最佳：

DP_MAP(node v):
  best[v] = ∞
  for pattern p 匹配於 v（p 覆蓋 v 與其部分後代）:
      cost = area(p) + Σ best[child]   （child 為 p 之外的被切開 fanout 節點）
      best[v] = min(best[v], cost), 記錄 p

單樹映射是 \(O(n \cdot |patterns|)\) 的多項式演算法，精確（在「切樹」的前提下）。Dagon 的成本以面積為主，延遲則以啟發式調整。Keutzer 隨後在 Bell Labs 發展了 Logic Synthesis Workbench（LSW, 1989 年前後），把映射形式化為「bidirectional 移動」的可組合演算法集，成為學界映射研究的參考架構；他與 Brayton 等人合編的工作奠定了 mapping-benchmark 文化（MCNC benchmarks）。

從面積到延遲：FlowMap 之前與之後的樹映射局限#

樹覆蓋的精確性被 fanout 切開破壞了：真實電路是 DAG，重聚斂（reconvergence）使「切開的兩棵樹」其實共享邏輯，獨立映射可能重複計算或錯失共享。1990 年代初，兩條路線分頭解決。面積導向：選擇性地允許節點在多處重複（duplication）或引入 global covering 的近似（如 MIS 中 Rudell 的 build-map/verify-map 嘗試）；延遲導向：Tourvig/Rudell 的 delay-driven tree mapping 與 1992 年 Keutzer、Malik、Saldanha 等人的工作，在動態規劃中同時追蹤 (area, arrival time) 的 Pareto 集合。商用側，Synopsys Design Compiler 在 1990 年代把這類樹/DAG 映射與 timing-driven 變體工程化到極致：以靜態時序分析（STA）回饋的 slack 為權重，映射過程中反覆調整每個節點的成本函數（slack 負的節點用快 cell，slack 正的用省電 cell），並結合邏輯複製（load splitting）與结构化重整。

Cut-based Mapping：K-LUT 框架的通用化#

真正的範式轉移發生在 1990 年代末，而且是從 FPGA 問題（3.7 節的 FlowMap）反哺回 ASIC 的。Cut-based mapping 的框架如下：對布林網路（此時通常表示成 AIG，And-Inverter Graph——僅含 AND2 與反相邊的規範網路，由 Alan Mishchenko 在 Berkeley 於 2000 年代大力推廣）的每個節點 \(v\) 枚舉其 cuts：一個 cut 是一組節點 \(\{u_1..u_k\}\) ，使 \(v\) 到 PI 的每條路徑都經過其中某節點；cut 大小 \(\le K\) 時，該 cut 對應一個 \(K\) 輸入的邏輯塊（FPGA 的 LUT，或經過變換後的複合 cell）。每個 node 保留最好（Pareto 最優）的若干 cuts，映射就是為每個節點選 cut、形成覆蓋。Cut enumeration 有高效的 \(O(n \cdot K)\) 等級演算法（利用 cut 的單調性合併子節點的 cuts），使「枚舉所有小 cut + 動態規劃選優」在數百萬閘的電路上可行。

CUT_MAP(node v):   // 深度/面積皆可
  cuts(v) = merge(cuts(u1), ..., cuts(uk)) 取前 B 個最優
  for c in cuts(v):
      cost(c) = 成本(c) + Σ max-cost(cut of u in c)  // 動態規劃
  保留 Pareto 最優的少量 (深度, 面積) 對

這個框架（Mishchenko 與 Satrajit Chatterjee 等人在 ABC 中的 amap、&nf 等命令）統一了面積、延遲、功耗的映射：差別只在成本函數與 cut 排序（cut ranking）策略。對 ASIC，把 AIG 的 cut 進一步用「super-gate + boolean matching」匹配到 cell library，或在映射後做 local restructuring，即得到 standard cell 網表；等價性驗證則由 combinational miter + SAT 把關。

Design Compiler 與商業化的制度意義#

演算法敘事必須配上商業敘事才完整。1986 年，Aart de Geus 與同事自 GE 離開創立 Synopsys（初名 Optimal Solutions），核心洞察有二：一是「邏輯綜合」不該只做面積，而要 timing-driven——以設計約束（constraints：時脈、輸入輸出延遲）驅動每一步優化；二是商業模式的槓桿在 standard cell 世代的 ASIC 產業——代工與 cell library 的普及（1980 年代末 VLSI Technology、LSI Logic 等 ASIC 廠商的 cell-based 生意）創造了「要把網表映射到各家庫」的普遍需求，一個 library-independent 優化 + library-aware mapping 的工具可以服務所有客戶。Design Compiler 於 1990 年前後上市（綜合核心來自 de Geus 在 GE 時代的邏輯優化技術與後續收購），配合 Verilog 語言標準化（1990 年 Open Verilog International 成立、1995 年 IEEE 1364），迅速成為 ASIC 設計的事實標準，到 1990 年代中期佔據邏輯綜合市場的絕對份額。這是 EDA 歷史上第一次，一個「編譯器式」的工具成為晶片設計的中心樞紐——RTL（而非網表）成為設計的真正源碼，設計生產力躍升一個數量級。

小結與轉場#

ASIC 技術映射的演算法史，是「樹上精確、DAG 啟發、cut 框架統一」的演進：Dagon（1987）用 tree covering + 動態規劃證明映射可自動化；LSW 與 Design Compiler 把它變成 timing-driven 的工業流程；ABC 的 cut-based mapping 則以 AIG 為共同基底，讓同一套演算法同時服務 ASIC cell 與 FPGA LUT。而 cut-based 框架的誕生地，其實是 FPGA——那裡的「每個邏輯單元恰好是 K-LUT + 若干暫存器」的離散資源結構，使映射問題變得異常純粹，也逼出了 1994 年那個著名的深度最佳演算法。

下一節 3.7，我們轉向 FPGA：K-LUT 架構、cut enumeration，與 Jason Cong 和 Yuzheng Ding 的 FlowMap——第一個也是至今唯一一個在深度上保證全局最佳的技術映射演算法。