現代處理器運作 (Modern Processor Operation)

Overview Table

5.7 為什麼要理解微架構 (p.553–554)

前面各節的最佳化(消除函式呼叫、記憶體參照等 optimization blockers)不依賴目標機器特性;要再往前推,必須利用處理器的微架構 (microarchitecture)——處理器執行指令的底層系統設計。

• 機器碼層看似「一次執行一條指令」,實際上處理器同時評估多條指令,稱為 instruction-level parallelism (ILP);某些設計可有 100+ 條指令 "in flight"。
• 硬體以精巧機制保證平行執行的行為完全等同機器碼要求的循序語意 (sequential semantic model)。
• 兩個刻畫最大效能的下界:
  • Latency bound(延遲下界):一連串運算必須嚴格循序執行(下一個運算需要上一個的結果)時遇到;資料相依限制了 ILP。
  • Throughput bound(吞吐量下界):功能單元的原始計算能力上限,是程式效能的終極極限。

5.7.1 整體運作 (Overall Operation, p.554–558)

現代處理器是 superscalar(每個 clock cycle 可執行多個運算)且 out of order(執行順序不必對應機器碼順序)。整體設計分兩大部分:instruction control unit (ICU) 負責從記憶體讀指令並產生 primitive operations;execution unit (EU) 負責執行這些運算。相較第 4 章的 in-order pipeline(04-Processor-Architecture/05-Pipelined-PIPE-Implementation-and-Hazards),out-of-order 硬體複雜得多,但能達到更高 ILP。

        Instruction Control Unit (ICU)
  +--------------------------------------------+
  | Retirement     Fetch    --Address-->       |
  |   unit        control            Instruction
  | [Register    Instruction <--Instructions- cache
  |   file]        decode                      |
  +------------------|-------------------------+
      ^  Register    | Operations      ^
      |  updates     v                 | Prediction OK?
  +--------------------------------------------+
  | Branch  Arith  Arith   Load     Store      |  Functional
  |   |      ops    ops     |         |        |  units
  |   +--Operation results--+-Addr    +-Addr   |
  |      (forwarding)       |  ^Data  |  Data  |
  |                         v  |      v        |
  |                       [ Data cache ]       |
  +--------------------------------------------+
              Execution Unit (EU)

Fetch 與分支預測 (p.554–555)

• ICU 從 instruction cache(存放最近使用指令的高速記憶體)讀取指令,且遠遠超前目前執行位置預先擷取,爭取解碼時間。
• 遇到 branch 時有兩個方向:taken(跳到 branch target)/ not taken(往下一條)。
• Branch prediction:猜測是否 taken 並預測目標位址;speculative execution:在確認預測正確之前,就開始 fetch、decode 甚至執行預測方向的指令。Fetch control 區塊內建分支預測以決定要抓哪些指令。
• 預測錯誤時:處理器將狀態重設回分支點,改往另一方向 fetch/execute。如 3.6.6 所述,misprediction 代價高昂——重新 fetch、decode、送入功能單元都需要時間。

指令解碼為 micro-operations (p.555–556)

Decode 邏輯把實際指令轉成一組 primitive operations(micro-operations),每個只做一件簡單事(加兩數、讀記憶體、寫記憶體)。拆解目的:讓專用硬體單元分工,平行執行多條指令的不同部分。解碼細節各機器不同且高度保密,但不需知道底層細節也能做最佳化。

功能單元 (Functional Units, p.556–557)

EU 每個 cycle 可接收多個 operations,分派 (dispatch) 給特化的功能單元:

• Load unit:處理讀記憶體 → 處理器的運算,內含加法器算位址;Store unit:處理器 → 記憶體,也含位址加法器。兩者經 data cache(存放最近存取資料的高速記憶體)存取記憶體。
• Branch operations 送進 EU 不是為了決定去哪,而是驗證預測是否正確;錯了則 EU 丟棄分支點之後已算出的結果,並通知 branch unit 正確目的地、從新位置開始 fetch。
• 算術單元刻意設計成通用(可執行多種整數/浮點運算組合):若一單元只做整數、另一只做浮點,則偏重某類運算的程式無法充分利用多單元。

Intel Core i7 Haswell 參考機有 8 個功能單元 (0–7)(p.557 部分能力):

• 「整數算術」指加法、位元運算、shift 等基本運算;乘除需更特化的資源。
• 一個 store 需要兩個功能單元:一個算 store 位址(單元 7)、一個實際存資料(單元 4)(機制詳見 5.12)。
• 統計:4 個單元可做整數運算、2 個可 load、2 個可 FP 乘法——直接決定後述 throughput bound。

Retirement unit 與 register renaming (p.557–558)

Retirement unit(位於 ICU,管轄 register file:整數、浮點、SSE/AVX 暫存器)追蹤處理進度,確保符合機器碼的循序語意:

• 指令解碼後其資訊放入 FIFO queue,直到兩種結局之一:
  1. Retired(退役):該指令的 operations 全部完成、且通往它的所有分支都確認預測正確 → 此時才更新 program registers。
  2. Flushed(沖銷):上游某分支預測錯誤 → 丟棄所有已算結果。因此 misprediction 不會改變程式狀態。
• Speculative execution 期間,結果不寫入 program registers 或 data memory。

為加速結果在指令間傳遞,執行單元之間直接交換 "operation results"(第 4 章 data forwarding 的進化版,參見 04-Processor-Architecture/04-Pipelining-Principles),最常見機制為 register renaming:

decode:  某指令將更新暫存器 r → 產生唯一 tag t,
         renaming table 加入項目 (r, t)
decode:  後續指令以 r 為運算元 → 送往 EU 的 operation 以 t 為來源
execute: 第一個 operation 完成 → 產生結果 (v, t) 廣播
         所有等待 t 的 operations 直接以 v 為來源值(forwarding)

• 值直接在 operation 之間轉發,不必寫入再讀出 register file → 後續運算在前一運算完成後立即可開始。
• Renaming table 只保存有 pending write 的暫存器;若解碼指令需要的 r 查無 tag,operand 直接從 register file 讀取。
• 有了 renaming,整串運算可完全 speculative 執行,暫存器仍只在分支結果確定後才更新。

5.7.2 功能單元效能 (Functional Unit Performance, p.559–560)

每種運算以三個參數刻畫(Figure 5.12,Haswell 參考機,對其他處理器亦具代表性):

• Latency(延遲):執行該運算所需的總 clock cycles。
• Issue time(發射時間):兩個獨立同類運算之間的最小間隔 cycles。
• Capacity(容量):能執行該運算的功能單元數(可同時發射數)。

• Fully pipelined:issue time = 1 的單元每個 cycle 可開始一個新運算。實作為一連串 stages,例如典型 FP adder 有 3 個 stages(對應 3-cycle latency):處理 exponent → 加 fraction → 捨入 (round)。
• Pipelining 能力只有在存在連續且邏輯上獨立的運算時才能發揮——這正是後續 ILP 最佳化的核心動機。
• Divider 不是 pipelined(整數/FP 除法與 FP square root 共用):issue time = latency,必須完成一整個除法才能開始下一個;latency/issue 依 dividend 與 divisor 的值而異(故給定為範圍),使除法成為相對昂貴的運算。
• 最大吞吐量 (maximum throughput) 定義為 issue time 的倒數;capacity $C$、issue time $I$ 時,處理器潛在吞吐量為 $C/I$ ops/cycle。例:FP 乘法 2 units、issue 1 → 每 cycle 2 個。
• 晶片面積有限,設計者以 benchmark 評估、把最多資源給最關鍵運算:整數乘法與 FP 乘法/加法被投入大量硬體以達低 latency 與深度 pipelining;除法罕用且難以低延遲或 full pipelining。

由此得出 combining 函式 CPE 的兩個基本下界(p.560):

5.7.3 處理器運作的抽象模型 (p.561–565)

分析工具:data-flow graph(資料流圖)——非正式的圖形表示法,顯示 operations 之間的資料相依如何限制執行順序;相依鏈形成 critical path(關鍵路徑),給出執行一組指令所需 clock cycles 的下界。

combine4 的 CPE 實測(p.561)幾乎全部貼合 latency bound:

這不是巧合:計算 n 個元素的積/和需約

其中 $L$ 為 combining 運算的 latency,$K$ 為呼叫函式與迴圈起訖的 overhead,故 CPE = latency bound $L$。

從機器碼到 data-flow graph (p.561–562)

combine4 內迴圈(data_t = double、OP = *;%rdx = data+i、%rax = data+length、%xmm0 = acc):

.L25:                             # loop:
  vmulsd (%rdx), %xmm0, %xmm0    #   acc *= data[i]
  addq   $8, %rdx                 #   data+i 前進
  cmpq   %rax, %rdx               #   與 data+length 比較
  jne    .L25                     #   若 != 繼續迴圈

4 條指令被 decoder 動態展開為 5 個 operations:vmulsd 拆成 load(讀來源運算元)+ mul;兩者出自同一條指令,其間的中間值不對應任何暫存器。cmp 更新 condition codes,由 jne 測試。

迴圈中被存取的暫存器分四類(p.562–563):

Loop registers 之間的運算鏈決定了限制效能的資料相依。 精煉圖形時(Figure 5.14):cmp 與 jne 不在 loop registers 的相依鏈上——假設 ICU 預測 branch taken(繼續迴圈),它們的作用只是測試條件、若 not taken 通知 ICU,且假設此檢查夠快不會拖慢處理器 → 塗白剔除,只留 loop registers,得到單次迭代的抽象模板:

   %xmm0            %rdx
     |             /  |
     |   data[i]->load |
     |        |       add
    mul <-----+        |
     |                 |
   %xmm0            %rdx
  (每迭代兩條跨迭代相依:acc 走 mul 鏈,data+i 走 add 鏈)

Critical path:模板複製 n 次 (Figure 5.15, p.564–565)

 Critical path(左鏈)        (右鏈)
 data[0] --> load
               |
              mul            add
               |              |
 data[1] --> load             |
               |              |
              mul            add
               |              |
              ...            ...
               |              |
 data[n-1]--> load            |
               |              |
              mul            add

 左鏈:n 個 mul(FP latency 5)→ 5n cycles ← critical path
 右鏈:n 個 add(int latency 1)→ n cycles(不構成限制)

• FP 乘法 latency 5 → 左側 mul 鏈為 critical path,需 $5n$ cycles → CPE = 5.00,正是 latency bound。
• 執行時 FP multiplier 是限制資源;指標操作、比較測試、load 皆與乘法平行進行;每個新的 acc 值要等 5 cycles 才能餵回下一次乘法。
• 其他資料型別/運算組合的圖形相同,只是左鏈換成不同運算;凡 latency $L>1$ 者,實測 CPE 均恰為 $L$。

其他效能因素 (p.565)

整數加法實測 CPE = 1.27 > 1.00(左右兩鏈皆預測 1.00):

小結:combine4 的 critical path 長 $L\cdot n$(acc 的連續更新造成),CPE 至少為 $L$;latency bound 看似根本極限,但下一步(5.8 起)將重構運算以增強 ILP,使 throughput bound 成為唯一限制,把 CPE 壓到 1.00 以下或附近 → 05-Program-Optimization/03-Loop-Unrolling-and-Parallelism。

多項式求值案例(Practice Problems 5.5 / 5.6 素材,p.566–567)

關鍵教訓:Horner 法運算次數較少($n$ vs $2n$ 個乘法)卻更慢——效能由 critical path 上的 latency 總和決定,而非運算總數;poly 較多的乘法與相依鏈平行執行,不佔 critical path。

Exam/Test Patterns

Related Notes

• 05-Program-Optimization/01-Optimizing-Compilers-and-Blockers
• 05-Program-Optimization/03-Loop-Unrolling-and-Parallelism
• 05-Program-Optimization/04-Limiting-Factors-and-Memory-Performance
• 04-Processor-Architecture/04-Pipelining-Principles
• 04-Processor-Architecture/05-Pipelined-PIPE-Implementation-and-Hazards
• 03-Machine-Level-Programs/03-Control-Flow