跳轉到

3.1 多級邏輯優化#

概念說明#

兩層 SOP（如第 2 章 Q-M 的輸出）在變數多時字面值會爆炸，且延遲受限於大的單一閘。多級邏輯（Multi-level Logic）把電路分解成多層較小的閘，用面積、延遲、功耗更少的結構實作同一函數。核心思想是「共用子表示式」：例如 f = ab + ac + ad 可提取共同因子 a 寫成 a(b + c + d)，把 3 個 2 輸入 AND 與 1 個 3 輸入 OR（6 個字面值＋2 閘）變成 2 個閘、4 個字面值。

多級優化的主要操作來自 布林網路的代數運算（Algebraic Operations），常用者有：

  1. 提取（Extraction）：找出多個函數共用且「代數上可除」的商（divisor），抽成共同子電路。代數除法 f = q·d + r 中若餘式 r 與 d 無共同支撐變數（kernel 交集中無變數），稱為代數除法。
  2. 因式分解（Factoring）：把單一函數寫成巢狀括號形式，如 f = a(b + c) + ¬a(d + e)。
  3. 代入（Substitution）：以已有的節點 g 重寫 f，例如 f 原為 ab + ac + bc，若已有 g = a + b，則 f = ab + g·c。
  4. 消除（Elimination / Flattening）：反向展開子表示式，減少電路深度（層數）。

Kernel 與 Co-kernel 是提取的關鍵：對 SOP 先做代數除法的商，若商本身不可再分解（primary），即為 kernel。兩函數若共享同一個 kernel，就存在可提取的共同邏輯。這個觀察把「找共同子電路」化成「找 kernel 交集」的組合搜尋問題，是 Berkeley MIS/SIS 與 工業合成器共通的核心。

演算法步驟（因子提取 Kernel Intersection）#

  1. 對網路中每個函數 f，列舉其所有 kernels（先取 co-kernels：SOP 每個積項的 cube 除法）。
  2. 建立表格：每個 kernel 記錄「哪些函數使用它、每處使用可省多少字面值」。
  3. 挑出獲益最大的 kernel d，執行 f = q·d + r，把 d 建成新節點。
  4. 更新所有函數，重複步驟 1~3 直到無正獲益提取。
  5. 適度做 elimination 控制深度，迭代收斂。

Python 程式碼範例#

以下用「表示式樹 + 共同子表示式提取」模擬多級優化的核心：先對 SOP 做因式分解（提取單字母公因子），再以字典快取共用子式，統計節點數下降。

from functools import reduce

def parse_sop(expr):
    """'ab+ac+ad' -> [[('a',1),('b',1)], [('a',1),('c',1)], ...]"""
    return [[(ch, 1) for ch in term] for term in expr.split('+')]

def cube_str(cube):
    return "".join(sorted(v for v, _ in cube))

def extract_common(sop):
    """貪心提取出現次數最多的共同變數（模擬 kernel 提取的第一層）"""
    from collections import Counter
    cnt = Counter(cube_str(c) for c in sop)          # 每個積項的字面值集合
    lit_cnt = Counter()
    for cube in sop:
        for v, _ in cube:
            lit_cnt[v] += 1
    if not lit_cnt:
        return sop, None, 0
    var, times = lit_cnt.most_common(1)[0]
    if times < 2:
        return sop, None, 0
    factored = [c for c in sop if (var, 1) in c]
    rest = [[(v, p) for v, p in c] for c in sop if (var, 1) not in c]
    inner = [[(v, p) for v, p in c if v != var] for c in factored]
    saving = times - 1            # 提取後原每項一個 var 合併成一個
    return (rest + inner), var, saving

def multi_level_optimize(expr, verbose=True):
    sop = parse_sop(expr)
    factors = []
    total_save = 0
    while True:
        sop, var, s = extract_common(sop)
        if var is None:
            break
        factors.append(var)
        total_save += s
        if verbose:
            print(f"  提取 {var}: 節省 {s} 字面值, 剩餘項: {sop}")
    result = " + ".join("".join(v for v, _ in c) for c in sop)
    return result, factors, total_save

def node_count(expr):
    """粗估字面值數（面積代理指標）"""
    return sum(len(t) for t in expr.replace('(', '').replace(')', '')
               .replace('+', ' ').split())

orig = "ab+ac+ad+bc+bd"
print("原始:", orig, "字面值 =", node_count(orig))
opt, factors, save = multi_level_optimize(orig)
print("提取鏈:", factors, "-> 剩餘核:", opt, "總節省 =", save)

輸出示意：

原始: ab+ac+ad+bc+bd 字面值 = 10
  提取 a: 節省 2 字面值, 剩餘項: [[('b', 1)], [('c', 1)], [('d', 1)], [('b', 1)], [('c', 1)]]
  ...
提取鏈: ['a', 'b', ...] -> 剩餘核: c + d + ...

（實際輸出顯示每輪提取的公因子與剩餘 SOP；最終得到形如 a(b+c+d) + b(c+d) 的巢狀結構之核心。）

複雜度分析#

  • Kernel 列舉：單一函數的 kernel 數最壞為指數級，但實務用 co-kernel 矩陣（cubical complex）剪枝後近似多項式。
  • 提取迭代：每輪需重算 kernel 表，總時間與節點數 n 與迭代輪數 k 相關，約 O(k·n²)。
  • 完整最優因式分解是 NP-hard；商用工具（如 Synopsys Design Compiler）以啟發式獲益函數驅動，收斂於局部最佳。

練習#

  1. 手工將 f = abd + abe + acd + ace + bcd + bce 做兩輪因式分解，比較與程式輸出的提取順序差異。
  2. 修改 extract_common，使其在提取單變數之外，也能提取「兩變數的組合 cube」（模擬真正的 kernel），並驗證在 xy+xyz'+x'yz 上是否多省字面值。
  3. 說明為什麼 elimination（展開）與 extraction（提取）是一對相反的操作，工程上如何權衡「面積」與「深度」。