Branch Prediction

4.1 - 概述 分支預測和 Cache 左右著 CPU 的效能，對於 superscalar CPU 來說，準確度高的分支預測更為重要 在一般的 RISC 指令集中，分支指令包含兩個要素： 方向： 分支指令的方向只有兩種：跳轉 (taken)，或是不跳轉 (not taken) 有些跳轉指令是無條件執行的 (e.g. jmp 指令)，有些跳轉指令則是需要根據指令中攜帶的條件是否成立來決定是否發生跳轉 (e.g. beq 指令) 目標位址： 對於一般的 RISC 指令集，目標位址在指令中有兩種形式： 直接跳轉 (direct)： 目標位址 = 當前分支指令 (或分支指令的下一條指令) 的 PC 值 + immediate PC offset 由於指令通常只有 32/64 bits，因此 immediate PC offset 的值範圍也就有限，因此也限制了直接跳轉能夠跳轉的範圍 因為 immediate PC offset 值是 encode 在分支指令中，因此在 pipeline 的 decode stage 就可以直接將 immediate PC offset 給解析出來，因此這種類型的指令是很容易進行分支預測的 這種跳轉指令的執行效能也比較好 間接跳轉 (indirect)： 目標位址是來自於 register 的內容，由於 register 是 32/64 bits，因此可以跳轉到任何位址 由於跳轉位址來自於 register，因此此類的分支指令的目標位址需要等待一段時間才能獲得 (e.g. 要等到 pipeline 的 execute stage) 在確認目標位址前進到 pipeline 的指令，有可能都會是無效的 (if taken)，因此增大了 mis-prediction penalty 且由於 register 的內容是會動態變化的，因此這類的分支指令很難對目標位址進行預測 不過慶幸的是，這類指令通常都是 call 或是 return 類型的指令，這類指令都有很強的規律性，是容易被預測的 MIPS R3000 只使用了 5 級的 pipeline，在第二個階段的 decode stage，就可以得到分支指令跳轉的目標位址，即使發生了跳轉 (taken)，也只需要丟棄一道仍在 fetch stage 的指令，misprediction penalty 並不高 ...

4.3 - 分支指令的目標位址預測 分支指令的目標位址可以分為兩種： 直接跳轉 (direct)： 對於直接跳轉指令 (e.g. RISC-V 的 beq、jal、lui 指令)，它的跳轉 offset 是以 immediate value 的方式 encode 在 opcode 中 (有可能是 PC-relative，也有可能不是)，所以它的目標位址是固定的，只要記錄這條分支指令目標位址即可 當再次遇到這條分支指令時，如果分支預測結果是 taken，那麼目標位址就可以直接使用先前所記錄的值 間接跳轉 (indirect)： 對於間接跳轉指令 (e.g. RISC-V 的 jalr 指令)，由於它的目標位址來自於暫存器，而暫存器的值是有可能一直變化的，所以對間接跳轉指令來說，要預測目標位址並不是一件容易的事情 然而慶幸的是，程式中大部份的間接跳轉指令都是用來呼叫函式的，也就是 call 和 return；這種目標位址是有規律的，因此可以對其進行預測 4.3.1 - 直接跳轉類型的分支預測 對於直接跳轉類型的分支指令 (假設是 PC-relative)，其目標位址有兩種情況： 當分支指令 not taken 時： 目標位址 = 當前分支指令的 PC 值 + sizeof(fetch group) e.g. PC + 4 當分支指令 taken 時： 目標位址 = 當前分支指令的 PC 值 + signed extended offset e.g. PC + offset ...

11.1 - 概述 DEC 的 Alpha 21264 是 superscalar CPU 的一個典範，其為 4-way out-of-order superscalar CPU，工作頻率是 466 ~ 667 MHz，benchmark：SPECint95 - 40、SPECfp95 - 86；與同時期其他的處理器 benchmark 對比： Alpha 21264 的 pipeline 最多同時支持 80 條指令，以及 80 個 checkpoints，因此對於 branch mis-prediction、exception、interrupt，Alpha 21264 都可以快速地恢復 CPU 狀態 Alpha 21264 的分支預測器實現了基於局部歷史 (Local prediction) 和基於全局歷史 (Global prediction) 兩種預測方式，並根據程式的執行情況，動態選擇預測率最高的方法，這就像是兩種分支預測方式在進行競爭一樣 對於 load/store 指令，Alpha 21264 採用了 Speculative Memory Disambiguation 和 Load hit/miss Prediction Alpha 21264 採用 7-stage pipeline，比較短的 pipeline 使 branch mis-prediction 發生時的 mis-penalty 比較低，從而提高處理器的效率： ...