限制因素與記憶體效能 (Limiting Factors & Memory Performance)

Overview Table

本章前段已建立兩個效能下限,本節探討「為何實際程式達不到、或如何逼近這些下限」:

• Latency bound(critical path):資料相依鏈的延遲總和 $T$ → 程式至少需 $T$ cycles。
• Throughput bound:需 $N$ 次某運算、$C$ 個 functional units、issue time $I$ → 至少需 $N\cdot I/C$ cycles。

5.11.1 Register Spilling(暫存器溢出)(p.584)

Loop parallelism 的效益受限於「能否用暫存器表達計算」。若程式的平行度 P 超過可用暫存器數,編譯器會進行 spilling:把部分暫時值存到記憶體(通常配置在 run-time stack)。

• x86-64 有 16 個整數暫存器 + 16 個 YMM 暫存器(存放浮點資料)。
• combine6 擴展實驗:10×10 unrolling 已達 throughput bound;20×20 unrolling 不再改善、部分反而變差(整數加法 CPE 由 0.55 升到 0.83)。
• 一旦發生 spilling,多 accumulator 的優勢多半喪失——每次更新 accumulator 從 1 條指令變成 load + 運算 + store 3 條。

10x10 unrolling(acc0 在暫存器):
  vmulsd (%rdx), %xmm0, %xmm0        ; acc0 *= data[i](1 條指令)

20x20 unrolling(acc0 溢出至 stack):
  vmovsd 40(%rsp), %xmm0             ; 從 stack 讀 acc0
  vmulsd (%rdx), %xmm0, %xmm0        ; 乘 data[i]
  vmovsd %xmm0, 40(%rsp)             ; 寫回 stack

5.11.2 Branch Prediction 與 Misprediction Penalty(p.585)

現代處理器採 speculative execution:遇到分支時猜測方向,先執行預測目標的指令,但不真正修改暫存器或記憶體;預測正確才 commit 結果,預測錯誤則丟棄所有推測結果、從正確位置重新 fetch——重新填滿 pipeline 的代價就是 misprediction penalty(參考機器約 19 cycles)。

分支的推測執行流程:

  fetch branch ──> 預測方向 ──> 沿預測路徑推測執行(結果暫存,不 commit)
                                   │
                     分支結果確定 ──┤
                                   ├─ 預測正確 → commit 結果(零額外成本)
                                   └─ 預測錯誤 → 丟棄推測結果
                                                → 從正確位址重新 fetch
                                                → 罰款 ~19 cycles(refill pipeline)

需要預測的對象:conditional jump(是否 taken)、indirect jump(如 jump table)與 procedure return(目標位址)。本節聚焦 conditional branch。

原則一:不必擔心「可預測」的分支(p.586)

• 分支預測邏輯很擅長辨識規律模式與長期趨勢。
• loop-closing branch 通常被預測為 taken,只在最後一輪 mispredict 一次。
• bounds checking 實驗(combine4 vs combine4b):加入 if (i >= 0 && i < v->len) 邊界檢查後,整數加法 CPE 僅 1.27→2.02,其餘三種組合完全不變——因為檢查永遠成立、高度可預測,額外計算可與 combining 運算平行進行,不影響 critical path。

原則二:改寫成適合 conditional move 的程式碼(p.587)

分支預測只對規律模式可靠;依資料任意特性(如正負)決定的分支本質上不可預測。此時應讓編譯器產生 conditional data transfer(cmov) 而非 conditional control transfer:先算出兩個分支的值,再用條件搬移選取,無需猜測、無罰款。

• 兩者 CPE 差約 (13.5 − 3.5) ≈ 10 cycles;因隨機資料約半數分支才 mispredict,故推得每次 misprediction penalty ≈ 20 cycles,與參考機器約 19-cycle 量測吻合。
• C 程式員無法直接控制編譯器是否產生 cmov,只能用較「functional」的風格提高機率,並檢查產生的組合語言 + 實測確認。

5.12 Understanding Memory Performance(p.589)

本節僅考慮所有資料都在 cache 中的情形(cache 細節見第 6 章)。現代處理器有專用 load/store functional units,內含 buffer 保存未完成的記憶體請求:

• 參考機器:2 個 load units(各可保存 72 個未完成讀取請求)、1 個 store unit(store buffer 容納 42 個寫入請求)。
• 每個 unit 每 cycle 可發起 1 個操作(issue time = 1)。

5.12.1 Load Performance(p.590)

Load 效能取決於兩個面向:throughput(pipeline 能力) 與 latency。

• Throughput 限制:每算 1 個元素需 load k 個值,2 個 load units → $\text{CPE}\ge k/2$。combining 系列每元素讀 1 個值,故 CPE 不可能低於 0.50(SIMD 除外)。
• Latency 限制:當 load 的位址依賴前一次 load 的結果時,load 進入 critical path。典型例子:linked list 走訪 ls = ls->next。

list_len 的 critical path(load latency 決定 CPE):

     %rdi ──> [load] ──> %rdi' ──> [load] ──> %rdi'' ──> ...
               (4c)                 (4c)
     每次 load 的位址 = 上一次 load 的結果 → 無法重疊

• list_len 量測 CPE = 4.00 = load latency = 參考機器 L1 cache 存取時間 4 cycles。
• 對照:combining 迴圈的 load 位址只依賴迴圈索引 i,load 彼此獨立、可完全 pipeline,latency 不影響 CPE。

5.12.2 Store Performance(p.591)

• Store 亦可完全 pipeline:clear_array(dest[i] = 0)達 CPE = 1.0,是單一 store unit 的極限。
• Store 不影響任何暫存器值,故一連串 store 之間不會形成資料相依。
• 只有 load 會受 store 影響:load 可能讀回 store 剛寫入的值 → write/read dependency。

Store Buffer 與位址比對

        Load unit                       Store unit
   ┌───────────────┐             ┌─────────────────────┐
   │               │   matching  │     Store buffer     │
   │   address ────┼────────────>│  ┌─────────┬──────┐  │
   │               │  addresses  │  │ Address │ Data │  │
   │      data <───┼─────────────│  ├─────────┼──────┤  │
   │               │  (若位址相符 │  │   ...   │ ...  │  │
   └──────┬────────┘   直接轉發) └──┴────┬────┴──────┴──┘
          │                              │
          v                              v
   ┌─────────────────────────────────────────┐
   │                Data cache               │
   └─────────────────────────────────────────┘

• Store buffer 保存已發出但尚未完成(尚未更新 data cache)的 store 之位址與資料,讓連續 store 不必等待 cache 更新。
• 每個 load 必須比對 store buffer 中的位址;若相符(任一寫入 byte 與讀取 byte 同址),直接取用 buffer 中的資料作為 load 結果(store-to-load forwarding)。

write_read 實驗:s_addr / s_data 分解

movq %rax,(%rsi) 這條 store 指令被解碼成兩個獨立操作:

• s_addr:計算 store 位址、在 store buffer 建立 entry 並填入 address 欄。
• s_data:填入該 entry 的 data 欄。

write_read 內迴圈 (*dst = val; val = (*src)+1; cnt--) 的相依關係:

   %rax    %rsi    %rdi    %rdx
    │       │       │       │
    │       └──> [s_addr]   │      (1) s_addr 必須先於 s_data(entry 先建立)
    ├──────────> [s_data]   │      (2) load 必須與所有 pending store 比對位址
    │               ┆(3)    │          → load 相依於 s_addr
    │       ┌──> [load] <── %rdi   (3) 虛線:條件相依——僅當位址相符時,
    │       │       │       │          load 才須等 s_data 寫入 buffer
    v       v       v       v
  [add $1] <────────┘    [sub $1]
    │                       │
   %rax'                  %rdx'

兩種呼叫方式的 critical path 對比:

Example A(位址不同)         Example B(位址相同)
  s_data   (獨立)               s_data ─┐
  load     (獨立)                       v
    │                                 load
    v                                   │
  [sub] ← 唯一 critical path            v
    │                                 [add] ──> 下一輪 s_data(critical path)

• 語意結論:write_read(&a[0], &a[0], n) 執行後該位置值為 n − 1(每輪讀回上一輪寫入的值再 +1)。
• 通用結論:暫存器運算的相依在解碼時即可確定;記憶體運算的相依要等 load/store 位址算出來才知道——這是記憶體效能難以預測的根源。

5.13 實務效能改善技巧(p.597)

三層優化策略總覽:

5.14 找出並消除效能瓶頸(p.598)

大程式連「該優化哪裡」都不明顯,需要 code profiler(在執行時收集效能資料的分析工具)。

5.14.1 Program Profiling:gprof(p.598)

Profiling = 在程式中加入 instrumentation code,量測各部分耗時;優點是可用真實 benchmark 資料執行實際程式。gprof 提供兩種資訊:①各函式耗費的 CPU time;②各函式被呼叫次數(按 caller 分類)。

gprof 三步驟:
  1. 編譯連結時加 -pg(用 -Og,避免 inline 使呼叫計數失真)
       linux> gcc -Og -pg prog.c -o prog
  2. 正常執行(慢約 2 倍),產生 gmon.out
       linux> ./prog file.txt
  3. 分析
       linux> gprof prog

報告解讀:

• 第一部分:各函式耗時排序(% time / cumulative / self seconds / calls)。
• 第二部分:calling history——誰呼叫它、它呼叫誰、各多少次。例:find_ele_rec 遞迴呼叫 158,655,725 次 / 頂層呼叫 965,027 次,比值 164.4:1 → 推得平均每次掃描 約 164 個 list 元素。

gprof 的特性(限制):

• 計時不精確:採 interval counting——OS 每隔 δ(約 1.0–10.0 ms)中斷一次,把整段 δ 記到「當下正在執行的函式」。長時間統計上合理;執行 < 1 秒的程式只能當粗估。
• 呼叫計數很可靠(前提:無 inline substitution)——每個 caller/callee 組合都有計數器。
• library 函式預設不顯示,時間併入呼叫者;可自寫 wrapper(如 Strlen 包 strlen)追蹤。

5.14.2 用 Profiler 引導優化:n-gram 案例(p.601)

分析莎士比亞全集(965,028 詞)的 bigram 統計(363,039 個 unique bigrams),六個版本的演進:

Amdahl's Law 的應用(p.604)

• insertion sort 佔 203.7/209.0 秒 → $\alpha =0.974$。
• quicksort 使排序時間趨近 0($k\to \mathrm{\infty }$)→ 預測加速 $S=1/(1-\alpha )\approx 39.0$,實測 38.5,吻合。
• 啟示:單點優化的上限由 α 決定;消除一個瓶頸後新瓶頸出現,持續加速必須轉攻其他部分。詳見 01-Computer-Systems-Tour/04-Amdahls-Law-and-Concurrency-Themes。

5.15 Summary(p.604)

• 編譯器無法替你換掉爛演算法/資料結構;消除 optimization blockers(memory aliasing、procedure calls)是程式員的責任,也是良好編程習慣。
• 進階調校需理解 microarchitecture:功能單元的 operations、capabilities、latencies、issue times 即可建立效能預測基準(latency bound / throughput bound)。
• 分支:讓它可預測,或改寫成適合 conditional data transfer 的形式。
• 記憶體:注意 store/load 互動;把值放在區域變數(得以配置在暫存器)常有幫助。
• 大程式用 profiler(gprof;更精細的有 Intel vtune、Linux valgrind,可分析到 basic block 層級——basic block 是中間無控制轉移離開的指令序列,必定整段執行)。

Exam/Test Patterns

Related Notes

• 05-Program-Optimization/01-Optimizing-Compilers-and-Blockers
• 05-Program-Optimization/02-Modern-Processor-Operation
• 05-Program-Optimization/03-Loop-Unrolling-and-Parallelism
• 03-Machine-Level-Programs/03-Control-Flow
• 04-Processor-Architecture/05-Pipelined-PIPE-Implementation-and-Hazards
• 06-Memory-Hierarchy/03-Cache-Memories
• 01-Computer-Systems-Tour/04-Amdahls-Law-and-Concurrency-Themes