迴圈展開與平行度 (Loop Unrolling & Parallelism)

#csapp #performance #loop-unrolling #instruction-parallelism #concept

Overview Table

小節	主題	核心結論
5.8 (p.567)	k × 1 迴圈展開 (loop unrolling)	減少 loop overhead,但 critical path 仍有 n 個運算 → 最多達到 latency bound
5.9.1 (p.572)	多重累加器 (multiple accumulators),k × k 展開	拆成 k 條獨立依賴鏈 → 突破 latency bound,CPE ≈ L/k
5.9.2 (p.577)	重新結合 (reassociation),k × 1a 展開	只改括號位置,把乘法移出依賴鏈 → 效果近似 k × k
Web Aside (p.582)	SIMD / AVX 向量指令	單指令處理 8 個 32-bit 或 4 個 64-bit 資料,再提升 4×–8×
5.10 (p.583)	結果總結	純 C + 標準編譯器達 throughput bound,較 combine1 快 10–20×;加 SIMD 整體可達 180×

名詞	定義
CPE	Cycles Per Element,每處理一個元素所需週期數
Latency bound	依賴鏈上每次運算需等前一次完成 → CPE 下限 = 運算延遲 L
Throughput bound	功能單元最大產能 → CPE 下限 = `I / C`(issue time / 單元數,即 1/throughput)
Critical path	data-flow graph 中延遲總和最長的依賴鏈,決定執行時間下限

參考機(Intel Core i7 Haswell)關鍵參數:整數加法 L=1、整數乘法 L=3、浮點加法 L=3、浮點乘法 L=5;各單元皆 fully pipelined(issue time I = 1)。

5.8 k × 1 迴圈展開 (Loop Unrolling) (p.567-571)

Loop unrolling 是一種程式轉換:每次迭代計算 k 個元素,使迭代次數減為約 n/k。好處有二:

減少不直接貢獻結果的 overhead 運算(loop indexing、conditional branch)。
暴露進一步轉換空間,讓後續能縮短 critical path(本節僅做展開,不做其他轉換)。

k × 1 展開的通用寫法(展開因子 k,但只用單一累加變數 acc):

主迴圈上限設為 limit = n − k + 1,即 i < n − k + 1,保證最大索引 i + k − 1 < n 不越界。
每次迭代 i += k,套用 OP 於 data[i] ... data[i+k-1]。
第二個「收尾迴圈」逐一處理剩下的元素,執行 0 到 k − 1 次(k = 2 也慣用迴圈寫法)。

/* 2 x 1 loop unrolling (combine5, p.568) */
long limit = length - 1;
for (i = 0; i < limit; i += 2)
    acc = (acc OP data[i]) OP data[i+1];   /* 仍是單一依賴鏈 */
for (; i < length; i++)                    /* 收尾迴圈 */
    acc = acc OP data[i];
*dest = acc;

CPE 實測(combine5 / 3×1 亦同):只有整數加法從 1.27 → 1.01(達 latency bound 1.00),其餘(int 、double +、double)完全不變——因為它們早已卡在各自的 latency bound(3.01 / 3.01 / 5.01)。即使展開到 k = 10(Fig. 5.17),沒有任何情況能低於 latency bound (p.569)。

原因(data-flow 分析,Fig. 5.18–5.20):兩條 vmulsd 都讀寫同一暫存器 %xmm0,兩個 mul 必須串列執行;迭代數減半但每迭代有 2 個 mul,critical path 仍是 n 個 mul:

combine5 (2×1) 的 data-flow:critical path 仍為 n 個 mul
                                (acc 在 %xmm0 上的單一依賴鏈)

 data[0] ──load──▶ mul ─┐
 data[1] ──load──▶ mul ─┤◀── 兩個 mul 串在同一鏈上   ┌ add(i+=2,可平行)
 data[2] ──load──▶ mul ─┤
 data[3] ──load──▶ mul ─┤
   ...                  │
 data[n-1] ─load─▶ mul ─┴──▶ acc   總延遲 ≈ n × L → CPE = L

編譯器也會展開迴圈

gcc 在最佳化等級 -O3 以上會自行執行某些形式的 loop unrolling (p.571 Aside)。

一般化敘述的例外

「展開必能改善效能」不成立:若 CPE 已在 latency bound(如上例的乘法與浮點運算),k × 1 展開毫無幫助;而展開過度還會導致 register spilling 反而變慢(見 05-Program-Optimization/04-Limiting-Factors-and-Memory-Performance)。

5.9.1 多重累加器 (Multiple Accumulators) (p.572-577)

功能單元皆 fully pipelined,每週期可啟動新運算,但單一 acc 讓新運算必須等前一個完成,每 L 週期才能啟動一次。若合併運算滿足結合律 (associative) 與交換律 (commutative)(如整數加法、乘法),可把運算拆成多組、最後再合併。

以乘積 $P_{n} = \prod_{i = 0}^{n - 1} a_{i}$ 為例(n 為偶數),拆成偶數索引與奇數索引兩組:

P_{n} = P E_{n} \times P O_{n}, P E_{n} = \prod_{i = 0}^{n / 2 - 1} a_{2 i}, P O_{n} = \prod_{i = 0}^{n / 2 - 1} a_{2 i + 1}

/* 2 x 2 loop unrolling (combine6, p.573) */
data_t acc0 = IDENT, acc1 = IDENT;
for (i = 0; i < limit; i += 2) {
    acc0 = acc0 OP data[i];      /* 偶數索引鏈 */
    acc1 = acc1 OP data[i+1];    /* 奇數索引鏈,互不依賴 */
}
for (; i < length; i++)
    acc0 = acc0 OP data[i];
*dest = acc0 OP acc1;            /* 最後合併 */

CPE 比較表(p.573):

Function	方法	int +	int *	double +	double *
combine4	單一累加器	1.27	3.01	3.01	5.01
combine5	2 × 1 展開	1.01	3.01	3.01	5.01
combine6	2 × 2 展開	0.81	1.51	1.51	2.51
Latency bound		1.00	3.00	3.00	5.00
Throughput bound		0.50	1.00	1.00	0.50

首度突破 latency bound:兩條 vmulsd 分別寫 %xmm0 與 %xmm1,mul 之間無依賴(Fig. 5.22–5.23),形成兩條 critical path,各含 n/2 個運算 → CPE ≈ L/2(如 double *:5.00/2 = 2.50)。唯一例外是整數加法:CPE 0.81 雖低於 1.0,但 loop overhead 仍太多,達不到理論值 0.50。

combine6 (2×2) 的 data-flow:兩條互相獨立的 critical path

 偶數鏈 (acc0/%xmm0)          奇數鏈 (acc1/%xmm1)
 data[0] ─load─▶ mul ─┐       data[1] ─load─▶ mul ─┐
 data[2] ─load─▶ mul ─┤       data[3] ─load─▶ mul ─┤
   ...                │         ...                │
 data[n-2] ─load▶ mul ┴▶acc0  data[n-1] ─load▶ mul ┴▶acc1
        每鏈 n/2 個運算 → CPE ≈ L/2(兩單元同時工作)

推廣為 k × k 展開:展開因子 k、k 個平行累加器。k 夠大時所有情況都逼近 throughput bound(Fig. 5.25, p.576):

int +:k = 7 時 CPE 0.54(bound 0.50,受兩個 load unit 限制)
int * 與 double +:k ≥ 3 時 CPE 1.01(bound 1.00)
double *:k ≥ 10 時 CPE 0.51(bound 0.50,兩個 FP 乘法器 + 兩個 load unit;浮點乘法雖較複雜,throughput 反而是加法的兩倍)

達到 throughput bound 的展開因子條件:延遲 L、容量(單元數)C 的運算必須讓所有 pipeline 填滿:

k \geq C \cdot L

例:double * 的 C = 2、L = 5 → 需 k ≥ 10;double + 的 C = 1、L = 3 → k ≥ 3 即可。

正確性(功能保持)的關鍵差異

整數:二補數加法/乘法即使溢位仍滿足交換律與結合律(02-Information-Representation/03-Integer-Arithmetic),combine6 與 combine5 在所有情況下結果相同,故部分編譯器會自動做此轉換。
浮點:加法與乘法不具結合律(02-Information-Representation/04-Floating-Point)。若偶數索引全是絕對值極大的數、奇數索引全接近 0.0, $P E_{n}$ 可能 overflow 或 $P O_{n}$ underflow,而依序計算的 $P_{n}$ 卻正常。實務上多數資料平滑良好,2× 效能通常值得,但開發者應與潛在使用者確認;大多數編譯器不會對浮點碼做此轉換(無法評估改變行為的風險)。

5.9.2 重新結合轉換 (Reassociation Transformation) (p.577-581)

只移動一對括號,即可打破序列依賴、突破 latency bound——稱為 2 × 1a 展開(combine7, p.578):

acc = (acc OP data[i]) OP data[i+1];   /* combine5: 2x1  — 兩個 OP 都在 acc 鏈上 */
acc = acc OP (data[i] OP data[i+1]);   /* combine7: 2x1a — 元素先互相結合 */

CPE(p.577):combine7 = int + 1.01、int 1.51、double + 1.51、double 2.51 —— 整數加法同 combine5,其餘三項與 combine6 相同(相對 k × 1 加速 2×)。

原理(Fig. 5.27–5.29):每迭代仍是 2 load + 2 mul,但第一個 mul 只把 data[i] * data[i+1] 相乘(不依賴 acc,可提前執行、與 critical path 平行);只有第二個 mul(乘入 acc)留在依賴鏈上 → 單一 critical path 只含 n/2 個運算,CPE 下限約減半:

combine7 (2×1a) 的 data-flow:單一 critical path,只含 n/2 個 mul

 data[0] ─load─┐
               ├▶ mul ──┐  (元素對相乘,脫離依賴鏈,可平行)
 data[1] ─load─┘        ▼
 acc ─────────────────▶ mul ──┐          ← critical path
 data[2] ─load─┐              │
               ├▶ mul ──┐     │
 data[3] ─load─┘        ▼     ▼
                        mul ◀─┘ ──▶ ... ──▶ acc(共 n/2 個)

k × 1a 推廣(Fig. 5.30):效能與 k × k 多重累加器相近,皆逼近 throughput bound。

可靠性比較

重新結合同樣改變浮點運算順序(正確性考量同 5.9.1)。多數編譯器不會重新結合浮點運算;目前的 gcc 會重新結合整數運算,但「不一定有好效果」。書中結論 (p.581):展開迴圈 + 累加多個平行值,是更可靠 (more reliable) 的加速手法。

Practice Problem 5.8 精華(p.581, 解答 p.612):3 展開的 r = r * x * y * z,五種括號結合方式的 CPE 下限 = 5P/3(P = critical path 上依賴 r 的乘法數,L = 5,每迭代處理 3 個元素):

結合方式	critical path 上的 mul 數 P	CPE 下限
A1 `((rx)y)*z`	3	5.00
A2 `(r(xy))z`、A5 `(rx)(yz)`	2	3.33
A3 `r((xy)z)`、A4 `r(x(yz))`	1	1.67

Web Aside OPT:SIMD — AVX 向量指令 (p.582-583)

SIMD(single instruction, multiple data):單一指令對整個資料向量運算。SSE(1999)演進為 AVX;向量暫存器 %ymm0–%ymm15,每個 32 bytes → 可裝 8 個 32-bit 或 4 個 64-bit 數(整數或浮點皆可)。

例:vmulps (%rcx), %ymm0, %ymm1 一次讀 8 個 single-precision 值並做 8 個平行乘法( $a_{i} \leftarrow a_{i} \cdot b_{i}, 0 \leq i \leq 7$ ),結果存入 %ymm1。
gcc 提供 C 語言擴充,讓程式以向量運算表達並編譯成 AVX/SSE 指令(比直接寫組語可攜,也能生成其他處理器的向量指令)。
「Vector 8 × 8」(展開 8 次 + 8 個向量累加器)相對 scalar 10 × 10 版:32-bit 情況約 8×、64-bit 約 4× 提升;向量化把 throughput bound 再降為 scalar 的 1/8(32-bit)或 1/4(64-bit)。
例外:AVX 沒有 64-bit 整數平行乘法指令,long 乘法無法向量化(gcc 生不出向量碼)。

5.10 最佳化合併程式碼的成果總結 (p.583-584)

Function	方法	int +	int *	double +	double *
combine1	Abstract -O1	10.12	10.12	10.17	11.14
combine6	2 × 2 展開	0.81	1.51	1.51	2.51
	10 × 10 展開	0.55	1.00	1.01	0.52
Latency bound		1.00	3.00	3.00	5.00
Throughput bound		0.50	1.00	1.00	0.50

純 C 語言 + 標準編譯器 就能達到接近 throughput bound(0.50 / 1.00),僅受功能單元容量限制,相對原始碼 10–20× 提升。
改寫為 SIMD 再得約 4×–8×;single-precision 乘法從 11.14 → 0.06,整體 超過 180×。
啟示:現代處理器算力龐大,但需以「非常風格化 (stylized)」的寫法才能榨出來。

最佳化路徑(以 double * 的 CPE 演進為例)

 combine1     combine4      combine5       combine6 / combine7      +SIMD
 抽象 -O1  →  消除瓶頸   →   k×1 展開    →   k×k 多累加器 / k×1a  →  向量化
  11.14        5.01           5.01            2.51 → 0.52(k=10)     更低
               ▲latency bound 卡住▲          ▲突破 latency bound▲
                                             逼近 throughput bound

Exam/Test Patterns

情境 / 關鍵字	答案
k × 1 展開後 CPE 為何不變?	critical path 仍有 n 個運算(單一 acc 依賴鏈),已在 latency bound,展開只省 overhead
k × 1 展開哪個情況會進步?	只有整數加法(L=1,原本受 loop overhead 拖累),1.27 → 1.01
k × 1 展開的迴圈上限怎麼設?	`limit = n − k + 1`(即 `i < n−k+1`),收尾迴圈跑 0 ~ k−1 次
求 k × k 展開後 CPE 下限	每條鏈 n/k 個運算 → CPE ≈ L/k,但不能低於 throughput bound `I/C`
要達 throughput bound 的最小展開因子	$k \geq C \cdot L$ (例:double * 需 k ≥ 2×5 = 10;double + 需 k ≥ 1×3 = 3)
為何浮點版 combine6 可能與 combine5 結果不同?	浮點加/乘不具結合律,重排可能因 rounding / overflow / underflow 產生差異
為何整數版重排一定安全?	二補數運算即使 overflow 仍滿足交換律與結合律
`acc = acc OP (data[i] OP data[i+1])` vs `(acc OP data[i]) OP data[i+1]`	前者是 reassociation (2 × 1a):元素先互乘脫離依賴鏈,critical path 剩 n/2 個運算,CPE 減半
給定括號結合方式求 CPE 下限(PP 5.8 型)	數出 critical path 上依賴 r 的運算數 P → 下限 = L·P/k(書例 5P/3:A1=5.00, A2/A5=3.33, A3/A4=1.67)
Horner's method CPE = 8 的來源(PP 5.6)	每迭代 `result = a[i] + x*result`:mul(5) + add(3) 串在同一依賴鏈 → 8 cycles/element
運算次數較多的 poly 為何反而比 Horner 快(PP 5.5/5.6)	`xpwr = xxpwr` 的 critical path 每迭代只有 1 個 mul(5 cycles);運算總數少 ≠ 快*,critical path 才是關鍵
編譯器會自動展開嗎?	gcc -O3 以上會做部分 loop unrolling;整數可能自動平行化,浮點不會被自動重排
AVX 向量暫存器規格	`%ymm0`–`%ymm15`,32 bytes,可裝 8 個 32-bit 或 4 個 64-bit 值
哪種運算無法用 AVX 向量化?	64-bit 整數乘法(AVX 無此平行指令)
多累加器 vs 重新結合,哪個較可靠?	多累加器(k × k)——書中明言 unroll + 累加多個平行值是 more reliable 的方法

公式速記

Latency bound: $CPE \geq L$ (單一依賴鏈)
Throughput bound: $CPE \geq I / C$ ;整體 $N$ 次運算至少需 $N \cdot I / C$ cycles
k 條平行鏈: $CPE \approx L / k$
填滿 pipeline 條件: $k \geq C \cdot L$
$P_{n} = P E_{n} \times P O_{n}$ , $P E_{n} = \prod_{i = 0}^{n / 2 - 1} a_{2 i}$ , $P O_{n} = \prod_{i = 0}^{n / 2 - 1} a_{2 i + 1}$
PP 5.8 型: $CPE \geq L \cdot P / k$ (P = critical path 運算數,k = 展開因子)

05-Program-Optimization/01-Optimizing-Compilers-and-Blockers — 前置:CPE 定義與編譯器最佳化的阻礙
05-Program-Optimization/02-Modern-Processor-Operation — 前置:功能單元延遲/容量、latency 與 throughput bound、data-flow graph 的由來
05-Program-Optimization/04-Limiting-Factors-and-Memory-Performance — 後續:register spilling 讓過度展開失效、分支預測與記憶體瓶頸
02-Information-Representation/03-Integer-Arithmetic — 二補數運算的結合律/交換律(整數重排安全的依據)
02-Information-Representation/04-Floating-Point — 浮點不具結合律、rounding/overflow 的根源
04-Processor-Architecture/04-Pipelining-Principles — pipeline 填滿與 issue time 的硬體基礎

Overview Table

5.8 k × 1 迴圈展開 (Loop Unrolling) (p.567-571)

5.9.1 多重累加器 (Multiple Accumulators) (p.572-577)

5.9.2 重新結合轉換 (Reassociation Transformation) (p.577-581)

Web Aside OPT:SIMD — AVX 向量指令 (p.582-583)

5.10 最佳化合併程式碼的成果總結 (p.583-584)

Exam/Test Patterns

Related Notes