3.3 查找表 LUT 映射與 FPGA#

from collections import defaultdict
from itertools import combinations

K = 2   # 2-LUT 示意（實務 K=4~6）

def topological_levels(net, order):
    """order: 拓撲序節點串列；net: node -> list of 輸入節點"""
    level = {}
    for v in order:
        level[v] = 0 if not net[v] else 1 + max(level[u] for u in net[v])
    return level

def enumerate_cuts(net, v, K):
    """列舉節點 v 的 K-feasible cuts（小網路用窮舉集合近似）"""
    # 先收集 v 的所有傳遞上游
    def cone(v, acc):
        for u in net[v]:
            if u not in acc:
                acc.add(u); cone(u, acc)
        return acc
    upstream = cone(v, set())
    cuts = []
    nodes = sorted(upstream, key=lambda x: -len(net[x]))  # 貪心：靠近 v 的優先
    # 窮舉所有 <= K 大小的「邊界集合」，驗證其為合法 cut
    from itertools import chain
    for r in range(1, K + 1):
        for cut in combinations(sorted(upstream), r):
            cut = set(cut)
            # 檢查：從 v 出發沿 net 反向，不穿過 cut 即可停
            seen, stack = set(), [v]
            ok = True
            while stack:
                x = stack.pop()
                for u in net[x]:
                    if u in cut:
                        continue
                    if u not in upstream:
                        ok = False; break
                    if u not in seen:
                        seen.add(u); stack.append(u)
                if not ok:
                    break
            if ok:
                cuts.append(frozenset(cut))
    return cuts

def lut_map(net, order, K=K):
    """深度最小化映射：DP 選 cut，回傳 (LUT清單, 深度)"""
    level = topological_levels(net, order)
    best = {}
    for v in order:                       # 拓撲序 DP
        if not net[v]:
            best[v] = (0, None)
            continue
        cuts = enumerate_cuts(net, v, K)
        candidates = [(1 + max(best[c][0] for c in cut), cut)
                      for cut in cuts if all(c in best for c in cut)]
        if not candidates:                # 無可行 cut：退而取全部輸入
            ins = frozenset(net[v])
            candidates = [(1 + max(best[c][0] for c in ins), ins)]
        best[v] = min(candidates, key=lambda t: t[0])
    pos = max(best, key=lambda v: best[v][0])
    depth = best[pos][0]
    # 回溯收集 LUT：沿最優 cut 遞迴
    luts = []
    seen = set()
    def trace(v):
        if v in seen or not net[v]:
            return
        seen.add(v)
        luts.append(v)
        for c in best[v][1]:
            trace(c)
    trace(pos)
    return luts, depth

# 網路： a,b -> n1; a,c -> n2; n1,n2 -> n3; n3,b -> out
net = {'n1': ['a', 'b'], 'n2': ['a', 'c'],
       'n3': ['n1', 'n2'], 'out': ['n3', 'b'],
       'a': [], 'b': [], 'c': []}
order = ['a', 'b', 'c', 'n1', 'n2', 'n3', 'out']   # 拓撲序
luts, depth = lut_map(net, order)
print("使用的 LUT 節點:", luts, " 深度 =", depth)
for v in luts:
    print(f"  LUT({v}) 輸入 = {sorted(net[v]) if net[v] else 'PI'}")

使用的 LUT 節點: ['out', 'n3', 'n1', 'n2']  深度 = 3
  LUT(out) 輸入 = ['b', 'n3']
  LUT(n3) 輸入 = ['n1', 'n2']
  LUT(n1) 輸入 = ['a', 'b']
  LUT(n2) 輸入 = ['a', 'c']