2000s - 高階合成 HLS：從 C 程式碼直接長出硬體#

案件摘要#

2000 年代中葉，RTL 已經不夠快了：AI、影像、通訊演算法一改再改，工程師卻要為每次改動重寫數萬行 Verilog。高階合成（High-Level Synthesis, HLS）讓設計師直接寫 C/C++/SystemC，工具自動排出時程、分配資源、長出 RTL 電路。從 1980s Gajski 的 Y-chart 櫺想、1990s 行為合成商用化未成，到 2004 Xilinx AutoPilot 一戰成名，HLS 終於在 AI 加速器時代成為設計主力。

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

抽象層再上移：1986 邏輯合成把設計從閘級上移到 RTL；但 RTL 描述的仍是「每個 cycle 做什麼」，演算法工程師寫的是「資料怎麼流動」。兩者之間隔著一道翻譯鴻溝。
Gajski 的 Y-chart（1983）：Gajski 與 Kuhn 把設計空間畫成行為／結構／實體三軸，每軸各有抽象層次。Y-chart 暗示：行為層（演算法）應可自動往下合成——這是 FHDL（FORTRAN-based HDL）與行為合成的理論源頭。
1990s 商用化未成：行為合成工具（Synopsys Behavioral Compiler 等）上市卻沒有成為主流——C 描述的語意太模糊（指標、動態記憶體、未定序行為），品質輸給手寫 RTL，設計師不買單。
關鍵推理：工具必須收緊語意（限定可合成的 C 子集）＋讓使用者指揮（pragma 指令），品質才能追上手寫 RTL：

\[ \text{HLS 可用性} = \underbrace{\text{C 語意收斂}}_{\text{可合成子集}} \times \underbrace{\text{pragma 控制}}_{\text{使用者知識}} \times \underbrace{\text{排程/分配演算法}}_{\text{核心引擎}} \]

AI 加速器引爆：2010s 深度學習讓「演算法一季一改」成為常態，RTL 開發速度成為瓶頸；Xilinx AutoPilot（2004）、Mentor Catapult、Cadence Stratus 終於等到爆發點。

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

1. 案件現場：HLS 的三步手續#

\[ \text{C/C++/SystemC} \xrightarrow{\text{排程 scheduling}} \text{排程表} \xrightarrow{\text{資源分配 allocation/binding}} \text{資料路徑} \xrightarrow{\text{控制器合成}} \text{FSM + RTL} \]

排程（scheduling）：決定每個運算在哪個 cycle 執行，滿足資料相依與資源約束。
資源分配（allocation/binding）：決定需要幾個加法器、乘法器、記憶體 port，並把運算綁到硬體單元上。
控制器合成：產生 FSM，逐 cycle 發出控制訊號，指揮資料路徑。

2. ASAP / ALAP 排程：最快的邊界#

給定資料流程圖（DFG） \(G=(V,E)\) ，每個節點 \(v\) 有延遲 \(d(v)\) 。ASAP（越早越好）排程定義：

\[ S_{\text{ASAP}}(v) = \max_{u \to v}\big(S(u) + d(u)\big), \qquad S_{\text{ASAP}}(v_0) = 0 \]

ALAP（最晚可以多晚）在總時限 \(T\) 下反向推：

\[ S_{\text{ALAP}}(v) = \min_{v \to w}\big(S(w)\big) - d(v), \qquad S_{\text{ALAP}}(v_{\text{out}}) \le T \]

兩者之差定義浮動範圍（mobility/slack）：

\[ \text{mobility}(v) = S_{\text{ALAP}}(v) - S_{\text{ASAP}}(v) \]

critical path 上 mobility \(=0\) ，這些運算沒有排程自由；其他運算可在 \([S_{\text{ASAP}}, S_{\text{ALAP}}]\) 間滑動——這個滑動空間正是資源共享的彈藥。

3. List Scheduling：latency 約束下的資源共享#

ASAP/ALAP 是「無資源約束」的上限。實際上硬體單元有限：例如只有 1 個乘法器，所有乘法必須錯開。list scheduling 用優先權排隊：

每個 cycle 取出「predecessor 已完成」的備選運算，依 priority \(=\) mobility 最小（或到達出口的最長距離）排序。
資源可用就排入，否則排到下一 cycle。

資源共享的取捨本質：

\[ \text{面積} \downarrow \quad\Longleftrightarrow\quad \text{latency} \uparrow \]

若乘法器從 4 個減為 1 個，面積約省 75%，但總 latency 變長（乘法必須序列化）。HLS 工具在給定約束下迭代，找出 Pareto 前沿。

4. Modulo Scheduling：迴圈 pipeline 與 II#

迴圈是 HLS 的主戰場。modulo scheduling（軟體 pipeline 的硬體版）把迴圈疊起來：第 \(i\) 次迭代與第 \(i-1\) 、 \(i-2\) 次同時執行。核心指標是啟動間隔（Initiation Interval, II）：

\[ \text{II} = \max\big(\text{II}_{\text{res}},\ \text{II}_{\text{dep}}\big) \]

\(\text{II}_{\text{res}}\) ：資源約束——若迴圈內有 3 個乘法但只有 1 個乘法器， \(\text{II}_{\text{res}} \geq 3\) 。
\(\text{II}_{\text{dep}}\) ：相依約束——迭代間資料相依距離 \(\delta\) 與延遲 \(d\) 決定 \(\text{II}_{\text{dep}} \geq \lceil d/\delta \rceil\) 。

迴圈總時間 \(\approx (\text{迭代數} - 1)\times \text{II} + \text{prologue/epilogue}\) 。pragma pipeline 的目標就是把 II 壓到理論下限。

5. Python 實作：ASAP/ALAP ＋ List Scheduling#

# DFG：節點 (名稱, 運算類型, 延遲cycle)，邊 = 資料相依
nodes = {'a': ('load', 1), 'b': ('mul', 2), 'c': ('mul', 2),
         'd': ('mul', 2), 'e': ('add', 1), 'f': ('add', 1),
         'g': ('store', 1)}
edges = [('a','b'), ('a','c'), ('a','d'),      # 同一陣列資料餵三個乘法
         ('b','e'), ('c','e'), ('c','f'), ('d','f'),
         ('e','g'), ('f','g')]
pred = {v: [u for u, w in edges if w == v] for v in nodes}
succ = {v: [w for u, w in edges if u == v] for v in nodes}

def asap(nodes, pred, d):
    S = {}
    def go(v):
        if v not in S:
            S[v] = max((go(u) + d[u] for u in pred[v]), default=0)
        return S[v]
    for v in nodes: go(v)
    return S

def alap(nodes, succ, d, T):
    S = {}
    def go(v):
        if v not in S:
            S[v] = min((go(w) for w in succ[v]), default=T+1) - d[v]
        return S[v]
    for v in sorted(nodes, key=lambda x: -len(succ[x])): go(v)  # 近似反拓樸
    return S

def list_schedule(nodes, types, d, T, n_res):
    """n_res: {'mul': 1, 'add': 1} 資源數約束；回傳各節點開始 cycle"""
    S_asap = asap(nodes, pred, d)
    S_alap = alap(nodes, succ, d, T)
    mob = {v: S_alap[v] - S_asap[v] for v in nodes}
    S, busy = {}, {}
    for c in range(T + 1):
        ready = [v for v in nodes if v not in S
                 and all(u in S and S[u] + d[u] <= c for u in pred[v])]
        ready.sort(key=lambda v: mob[v])                 # mobility 最小優先
        for v in ready:
            r = types[v]
            if len([x for x in busy.get(r, []) if x[0] <= c < x[1]]) < n_res.get(r, 1):
                S[v] = c; busy.setdefault(r, []).append((c, c + d[v]))
        if len(S) == len(nodes): break
    return S, S_asap, S_alap

d = {v: nodes[v][1] for v in nodes}
types = {v: nodes[v][0] for v in nodes}
S, S_asap, S_alap = list_schedule(nodes, types, d, 8, {'mul': 1})  # 只約束乘法器
print("節點  ASAP  ALAP  排程")
for v in sorted(S, key=S.get):
    print(f"{v:>4}  {S_asap[v]:>4}  {S_alap[v]:>4}  {S[v]:>4}")
# 乘法器只有 1 個：b、c、d 三個乘法被錯開排程；總時間從 5 cycles 變 8 cycles

6. C 程式碼示範：pragma 指揮 HLS#

// C 原始碼：矩陣-向量乘（HLS 輸入）
void matvec(int A[N][M], int x[M], int y[N]) {
#pragma HLS ARRAY_PARTITION variable=A complete dim=2  // 陣列分塊：M 個 bank，port 翻倍
    for (int i = 0; i < N; i++) {
#pragma HLS PIPELINE II=1                              // 迴圈 pipeline，目標 II=1
        int sum = 0;
        for (int j = 0; j < M; j++)
            sum += A[i][j] * x[j];
        y[i] = sum;
    }
}
// 對應 pragma：
//   unroll → 複製硬體，迭代平行展開（面積↑ throughput↑）
//   pipeline II=1 → 每 cycle 啟動一個新迭代（modulo scheduling）
//   array_partition → 記憶體分 bank，消除 port 衝突瓶頸
// HLS 輸出 RTL 骨架：FSM (IDLE→READ→MAC→ACCUM→WRITE) 控制 M 個乘加單元

結案 -- 後果與影響#

演算法工程師直接寫 C：HLS 把硬體設計門檻從「懂 RTL 的數位設計師」降到「懂演算法的任何人」，軟硬體鴻溝被大幅壓縮。
AI 晶片設計主力工具：2010s–2020s 深度學習加速器（NPU、TPU、FPGA 加速卡）大量以 HLS 開發；Google TPU 的部分模組與 TSMC 先進製程的 FPGA 驗證平台都用到 HLS 流程。
Xilinx Vivado HLS 與 AMD/Intel FPGA 生態：AutoPilot（2004 收購 AutoESL 前身）→ Vivado HLS（2012）→ Vitis HLS（2019），成為 FPGA 高階設計標準；AMD 併購 Xilinx 後 HLS 深入資料中心產品線。
商業三強齊備：Mentor Catapult、Cadence Stratus、Synopsys HLS——抽象層上移的十年長跑終於收成，理論（modulo scheduling、ML-for-HLS）延續至今。

關鍵人物與文獻#

Daniel Gajski：Y-chart（Gajski–Kuhn, 1983）與 FHDL、行為合成理論奠基。
Jason Cong（UCLA）：AutoESL／AutoPilot 的學術源頭，FPGA HLS 先驅。
R. Camposano、W. Wolf（eds）, High-Level VLSI Synthesis, Kluwer, 1991；G. De Micheli, Synthesis and Optimization of Digital Circuits, 1994。
J. Cong, B. Liu, S. Neuendorffer, et al., High-Level Synthesis for FPGAs, IEEE Trans. on CAD, 2022。
Mentor Catapult、Cadence Stratus、Xilinx Vivado HLS 使用手冊。