程式效能最佳化練習題 (Practice - Program Optimization)

因為 memory aliasing:編譯器無法排除 xp 與 yp 指向同一位置的可能,必須假設最壞情況。
當 xp == yp 時:twiddle1 連續兩次翻倍,結果為原值的 4 倍;twiddle2 執行 *xp += 2*(*xp),結果為 3 倍。行為不同,故此轉換不是 safe optimization。

func1 回傳 0+1+2+3 = 6;func2 回傳 4×0 = 0。
f 具有 side effect(修改全域狀態),故兩寫法不等價。多數編譯器不分析函式是否無 side effect,一律假設最壞情況、保留所有函式呼叫,不會把 4 次呼叫合併成 1 次。

(a) CPE = 9.0:CPE (cycles per element) 是執行時間線性項的斜率,常數 368 是 overhead(n 夠大時可忽略)。
(b) 週期時間 = 1/頻率 = $1/(4\times {10}^9)$ 秒 = 0.25 ns = 250 ps。

解 $60+35n<136+4n$ → $31n<76$ → $n<2.45...$,即 n ≤ 2 時版本 1 較快;n ≥ 3 起版本 2 較快。
模式:小 n 時常數項(overhead)低者勝,大 n 時 CPE 低者勝;記得 n 是整數,交叉點要取整。

Latency bound:運算間嚴格循序相依(下一個需要上一個的結果)時,CPE 下限 = 運算 latency L。
Throughput bound:功能單元原始算力極限,吞吐量 = C/I ops/cycle,CPE 下限 = I/C。
整數加法 4 單元理論上 0.25,但參考機器只有 2 個 load units,每 cycle 最多讀 2 個元素,故逐元素讀取的 combining 運算下限為 0.50。

addq %rax,%rdx(純暫存器)= 1 個 operation;addq %rax,8(%rdx) = 3 個:load(讀記憶體)、add(相加)、store(寫回)——記憶體參照與算術分離,讓專用單元平行分工。
一個 store 需要 2 個功能單元:一個計算 store 位址、一個實際存資料。

推測執行期間結果不寫入 program registers 或 data memory。指令解碼後進入 retirement unit 的 FIFO queue,只有當其 operations 全部完成、且通往它的所有分支都確認預測正確時才 retire(此時才更新暫存器);預測錯誤則整批 flush,丟棄推測結果並從正確目標重新 fetch。register renaming(tag 轉發)讓整串運算可以完全 speculative 地執行。

主迴圈條件為 i < n − k + 1(即 limit = n − k + 1),保證最大索引 i + k − 1 < n;收尾迴圈執行 0 到 k − 1 次。
不能突破 latency bound:單一 acc 使所有運算仍在同一條相依鏈上,critical path 仍有 n 個運算。實測只有整數加法(原本受 loop overhead 拖累)從 1.27 → 1.01,其餘完全不變。

(a) k 條獨立鏈 → CPE ≈ L/k = 5/5 = 1.00(仍高於 throughput bound 0.50,故不會被下界截斷)。
(b) 填滿所有 pipeline 需 $k \ge C \cdot L = 2 \times 5 = $ 10。書中實測 double * 在 k ≥ 10 時 CPE 達 0.51。

從 5.01 降到約 2.51(CPE ≈ L/2)。
改括號後,data[i] OP data[i+1] 的元素互乘不依賴 acc,可脫離相依鏈提前平行執行;只有第二個運算(乘入 acc)留在鏈上 → critical path 從 n 個運算縮為 n/2 個。這就是 2 × 1a reassociation(combine7),效果與 2 × 2 多重累加器相當。

整數:二補數加法與乘法即使溢位仍滿足結合律與交換律,任意重排結果不變,故部分編譯器會自動做此轉換。
浮點:加法與乘法不具結合律——重排可能因 rounding 或 overflow/underflow 改變結果(例如偶數索引全是極大值、奇數索引接近 0 時,分組乘積可能 overflow 而依序計算正常)。因此多數編譯器不對浮點碼做此轉換,開發者需自行確認可接受。

效能由 critical path 上的 latency 總和決定,而非運算總數。
polyh 的跨迭代相依鏈是 result 的更新:mul (5) 與 add (3) 串聯在同一鏈上 → 每迭代 8 cycles → CPE 8.00。
poly 的跨迭代鏈只有 xpwr = x*xpwr 的單一 mul(5 cycles);a[i]*xpwr 與 result += 不在跨迭代鏈上,可與之平行執行 → CPE 5.00。運算總數少 ≠ 快。

原因:不可預測分支 + branch misprediction penalty(參考機器約 19 cycles,與 13.5 − 3.5 ≈ 20 的差距吻合)。隨機資料使依資料決定方向的分支猜錯率約一半。
解法:改寫成 functional style——先用 ?: 條件運算算出兩個結果值、再無條件賦值,促使編譯器產生 conditional move (cmov):無需預測、無罰款,CPE 與資料模式無關(minmax 例:13.5 → 4.0)。注意可預測分支(loop-closing、恆成立的 bounds check)幾乎零成本,不必刻意消除。

Register spilling:x86-64 只有 16 個整數暫存器與 16 個 YMM 暫存器,平行度(累加器數)超過可用暫存器時,編譯器把部分 accumulator 溢出到 run-time stack。每次更新 accumulator 從 1 條指令變成 load + 運算 + store 3 條,多重累加器的優勢消失。辨識特徵:組譯碼中 accumulator 以 %rsp 位移存取(如 vmovsd 40(%rsp),%xmm0 ... vmovsd %xmm0,40(%rsp))。

每次 load 的位址依賴前一次 load 的結果,load 進入 critical path、無法重疊 → CPE = load latency = L1 cache 存取時間 4 cycles。
陣列走訪的 load 位址只依賴迴圈索引 i,各 load 彼此獨立、可完全 pipeline;此時限制是 throughput(2 個 load units → 每元素 k 次 load 時 CPE ≥ k/2,combining 系列故不低於 0.50)。

Store 指令被拆成 s_addr(算位址、在 store buffer 建 entry)與 s_data(填入資料)兩個操作;每個 load 都要比對 store buffer 中的位址,相符時直接轉發 buffer 資料(store-to-load forwarding)。
Example A(異址):位址不符,load 與 store 獨立進行,critical path 只剩 cnt-- 的 sub 鏈 → CPE 1.3(接近下限 1.0)。
Example B(同址):load 必須等 s_data 完成才能取值,critical path 變成 s_data → load → add 的循環,每輪約 7 cycles → CPE 7.3。這就是 write/read dependency;記憶體運算的相依要等位址算出來才知道,是記憶體效能難以預測的根源。

combine3:每迭代寫回污染 v[2],計算過程 1 → 2·1=2 → 3·2=6 → 6·6=36,最終 [2, 3, 36]。
combine4:acc 在暫存器累積 1·2·3·5 = 30,結束才寫入,最終 [2, 3, 30]。
兩者行為在 aliasing 下不同,故編譯器不能自動把 combine3 轉成 combine4——即使後者更貼近程式意圖,編譯器只能保守假設 dest 可能指向向量內部。