はじめに
CPUを１から作成しています。
https://github.com/tomamints/mints-riscv-cpu
SystemVerilogで自作しているRV64IMAC CPU「MiNTs-CPU」を、Rocket Chipと比較しながら改善しました。
この記事では、その中でも branch predictor / frontend に絞って書きます。
MiNTs-CPUはすでにOpenSBI、Linux 6.12、BusyBoxが動くところまで来ています。ただ、Linuxが動くようになると次に気になるのは、
世の中の公開されているモデルとどこまで性能に差があるのか
というところです。
そこでRocket Chipを参照CPUとして使い、自作CPUのどこに余分なサイクルがあるのかを測りました。
結論から言うと、今回のbranch-heavyな共通assembly microbenchmarkでは、
MiNTs-CPU:
Rocketとほぼ同等のcyclesまで改善
Linux boot workload:
CPI 2.529 -> 2.393
IPC 0.395 -> 0.417
まで改善できました。（約5.4%ほど改善）
ただし、これは「CPU全体でRocket」という意味ではありません。今回言えるのは、
共通RV64 integer assemblyのbranch-heavy loopにおいて、MiNTs-CPUのfrontend bubbleをRocketとほぼ同等まで削れた
ということです。
比較で最初に気をつけたこと
最初はCで小さなbenchmarkを書いて比較していました。
しかしC benchmarkだと、CPUそのもの以外の差が混ざります。
- compiler version
- optimization level
- ABI
- startup/runtime
- linker layout
- libc / host interface
実際、-O0 と -O2 だけでもMiNTs側のCPIが大きく変わりました。
なので、branch predictorのようなmicroarchitectureを比較するには、C benchmarkのままだと少し曖昧です。
そこで、比較対象を 共通のhand-written assembly kernel に切り替えました。
構造はこうです。
platform-specific wrapper
↓
rdcycle / rdinstret
↓
common assembly benchmark
↓
rdcycle / rdinstret
↓
platform-specific exit / print
RocketとMiNTsでwrapperは違いますが、測定区間のassembly kernelは共通です。
これにより、比較したい部分をかなり絞れます。
same measured instruction stream
same logical workload
same iteration count
same final result
same rdcycle / rdinstret measurement
Benchmark
今回見た基本ループは、整数ALU + loop branchだけの小さいものです。
1 iterationあたりの命令はこうです。
xor t0, t0, t1
slli t4, t0, 7
srli t0, t0, 57
or t0, t0, t4
addi t1, t1, 1
add t0, t0, t2
bne t1, t3, 1b
つまり、ほぼ、
6 ALU instructions + 1 taken branch
です。
このbenchmarkでは、D-cache、store buffer、PTW、MMIO、Linuxなどはほぼ関係ありません。
なので差が出るなら、主に、
- basic pipeline
- forwarding
- instruction fetch
- branch prediction / redirect
あたりです。
さらに、branchの影響を見るために、同じ仕事を2x、4xにunrollしたvariantも用意しました。
1x:
6 ALU + branch
2x:
12 ALU + branch
4x:
24 ALU + branch
もし差がbranch回数に比例するなら、unrollすると差も比例して減るはずです。
最初の結果
最初の結果はこうでした。
| variant | Rocket cycles | MiNTs cycles | MiNTs extra |
|---|---|---|---|
| 1x | 70,045 | 90,013 | +19,968 |
| 2x | 65,042 | 75,025 | +9,983 |
| 4x | 62,545 | 67,537 | +4,992 |
これはかなり分かりやすい結果でした。
MiNTsの余分なサイクルが、unrollするたびにほぼ半分になっています。
1x extra: 約20,000 cycles
2x extra: 約10,000 cycles
4x extra: 約 5,000 cycles
つまり、MiNTs側の余分なコストは、
branch回数にほぼ比例している
ということです。
この時点で、主犯はmemoryではなく、taken branchを処理するfrontend側だと見えてきました。
既にbranch predictorはあった
ここで少しややこしいのは、MiNTs-CPUにはすでにbranch predictorがありました。
大まかには、
- 2-bit PHT
- BTB
- RAS
を持っています。
なので最初は、
branch predictorが外れているのか？
と思いました。
しかし実際には、問題は精度そのものではありませんでした。
問題は、
予測が当たっていても、その予測を使うのが遅い
ことでした。
当時の流れは、概念的にはこうです。
fetch instruction
↓
instructionを切り出す
↓
branch predictorが命令を見る
↓
takenと分かる
↓
fetch redirect
↓
frontend flush / restart
つまり、正しくtakenと予測できても、その時点でfrontend redirectとして扱っていました。
これはbranch predictorが「当たるかどうか」とは別の問題です。
prediction accuracy
= 予測が正しいか
prediction timing
= 予測をいつ使えるか
今回は後者が問題でした。
改善1: fetch-side BTB
最初の改善は、conditional branchのtargetをfetch側で早く使うことです。
改善前は、branch命令をfetchしてから予測していました。
before:
fetch instruction
-> branchだと分かる
-> predictor says taken
-> redirect
改善後は、fetch PCの時点でBTB/PHTを見るようにしました。
after:
fetch PC
-> BTB/PHT lookup
-> predicted target PC
-> target blockを早くfetch
ここで大事なのは、architecturalな正解はあくまでEX stageに残していることです。
predictor = hint
EX branch resolution = truth
なので、fetch側のBTBは間違っても構いません。EXで実際のbranch結果と比較し、外れていたらflush/recoveryします。
逆に、当たっているときはfrontendを無駄にflushしないようにします。
fetch-BTB後の結果
fetch-side BTBを入れた後のMiNTs結果です。
| variant | before cycles | after fetch-BTB | saved |
|---|---|---|---|
| 1x | 90,013 | 80,015 | 9,998 |
| 2x | 75,025 | 70,027 | 4,998 |
| 4x | 67,537 | 65,039 | 2,498 |
saved cyclesがbranch回数に比例しています。
つまり、fetch-side BTBで、
約1 cycle / taken branch
を削れました。
ただし、まだRocketとの差は残っていました。
| variant | Rocket cycles | MiNTs after fetch-BTB | remaining gap |
|---|---|---|---|
| 1x | 70,045 | 80,015 | +9,970 |
| 2x | 65,042 | 70,027 | +4,985 |
| 4x | 62,545 | 65,039 | +2,494 |
これもまたbranch回数に比例しています。
つまり、もう1 cycle / branchくらいの固定costが残っていました。
改善2: fetch FIFO / issue FIFO bypass
次にtraceを見ました。
ここで分かったのは、branch targetへのfetch自体はかなり早くなったものの、その後にまだfetch block handoffのbubbleが残っていたことです。
MiNTsのfetch単位は8 byteです。
今回のloopでは、branch targetが8-byte blockの後半に来るケースがありました。
8-byte fetch block
lower 4B: previous instruction
upper 4B: branch target instruction
この場合、target instructionを1個出したあと、次の命令は次の8-byte blockにあります。
ところが以前は、
I-cache response
↓
target instructionを出す
↓
次cycle以降に次blockをrequest
のようになっていて、ここに固定の1 cycle bubbleがありました。
そこで、
- fetch FIFO response bypass
- issue FIFO fall-through / bypass
- I-cache response cycleで次requestを受けられるようにする
を入れました。
イメージとしては、FIFOを常に通過するpipeline stageとして使うのではなく、
downstreamが受け取れるなら直接流す
詰まった時だけFIFOに退避する
という形です。
new fetched instruction
↓
issue FIFO empty?
↓ yes
core ready?
↓ yes
bypass to core
もちろん、FIFOに既存命令がある場合は必ずFIFOを優先します。
FIFOに既存命令あり
-> FIFO headを先に出す
-> 新しい命令はFIFOへ
そうしないと命令順序が壊れます。
最終結果
fetch-side BTBに加えて、fetch/issue bypassとI-cache follow-on requestを入れた後の結果です。
| variant | Rocket cycles | MiNTs cycles | delta |
|---|---|---|---|
| 1x | 70,045 | 70,014 | -31 |
| 2x | 65,042 | 65,026 | -16 |
| 4x | 62,545 | 62,538 | -7 |
このbranch-heavyな共通assembly benchmarkでは、Rocketとほぼ同等まで来ました。
この結果が示しているのは、
少なくともこのbranch-heavy integer loopでは、
以前MiNTsにあったbranch-frequency-proportional frontend bubbleはほぼ消えた
ということです。
Linuxでも効いたか
この状態で、同じfrontend改善後にOpenSBI + Linux + BusyBoxの100M cycle checkpointを測りました。
構成は以下です。
OpenSBI + Linux 6.12 + BusyBox
cycles: 100,000,000
D-cache: 512 lines x 32B
Store buffer: 8 entries
D-cache: write-through
改善前後はこうです。
| metric | before | after | delta |
|---|---|---|---|
| retired | 39,534,138 | 41,780,831 | +2,246,693 |
| CPI x1000 | 2,529 | 2,393 | -136 |
| IPC x1000 | 395 | 417 | +22 |
| primary ifetch | 19,749,634 | 16,160,494 | -3,589,140 |
| primary mem | 13,068,681 | 13,905,496 | +836,815 |
CPIで見ると、
2.529 -> 2.393
なので、約5.4%改善です。
固定100M cycleでretired instructionも約225万増えています。
また、primary ifetchが大きく減っています。
primary ifetch:
19.75M -> 16.16M
これは、今回のfrontend改善がLinux workloadにも効いていることを示しています。
一方で、primary memは少し増えました。
これは悪いというより、frontendのbubbleが減ったことで、次のボトルネックとしてmemory側が見えやすくなった、と考えています。
frontend bubbleを削る
↓
より多くの命令が進む
↓
memory systemへの圧力が増える
CPUの性能改善ではよくあるボトルネック移動です。
correctnessでハマったところ
fetch-side predictionを入れると、fence.i が重要になります。
fence.i は、instruction memoryを変更した後に、その変更をinstruction fetchへ反映させるために使われます。
例えば、testでは命令列をmemoryに書き換えてから fence.i し、その後に書き換えた命令へ飛ぶケースがあります。
このときbranch predictorやBTBが古い情報を持ったままだと、fetch-side predictionが stale になります。
そこでMiNTs-CPUでは、fence.i をMEM stageでpreciseなfrontend invalidationとして扱うようにしました。
fence.i reaches MEM
-> redirect fetch to fence.i + 4
-> invalidate I-cache
-> invalidate branch predictor state
ここで重要なのは、fence.i と sfence.vma / satp を分けて扱うことです。
fence.i:
instruction fetch / predictor stateの同期
sfence.vma / satp:
address translation / TLBの同期
ここを混ぜると、後でMMUやcacheまわりが読みづらくなります。
修正後は以下を確認しました。
make build PASS
rv64ui-p-fence_i PASS
make test-rv64ui 54 / 54 PASS
Whisper lockstep PASS
今回学んだこと
1. branch predictorは「当たる」だけでは足りない
今回一番大きかったのはこれです。
branch predictorが正しい方向を出していても、それを使うのが遅かったり、正解時にもflushしていたりすると、性能は出ません。
accuracy is not enough
timing matters
という感じです。
2. C benchmarkだけで原因を見るのは危ない
C benchmarkではcompilerやABIの差が混ざります。
今回も最初はCで見ていましたが、途中からcommon assemblyに切り替えたことで、
これはbranch回数に比例している
とかなり明確に言えるようになりました。
CPU同士を比べるときは、
same source
よりも、
same measured instruction stream
の方が強いです。
3. microbenchmarkとLinuxの両方を見るのが大事
microbenchmarkは原因を切るのに向いています。
一方でLinux workloadは、実際のシステムで効くかを見るのに向いています。
今回も、
common assembly:
branch frontend bubbleをほぼ消せた
Linux 100M:
CPI 2.529 -> 2.393
という形で、両方を見たことで納得感が出ました。
4. predictorはhint、EX/MEMがtruth
fetch側のpredictionはどれだけ賢くしても、architecturalな正解ではありません。
今回も設計思想として、
predictor = hint
EX/MEM/CSR = truth
を守るようにしました。
これを守っておくと、BTB、PHT、RASを後で差し替えてもpipeline本体を壊しにくいです。
次に見るところ
branch-heavy loopではかなり改善できたので、次はmemory側をRocketと比較しています。
候補はこのあたりです。
- L1 hit load
- dependent load
- store hit
- pointer chase
- cache miss
- TLB / PTW
実際、次の比較ではstoreやload pathにまだ差が見えています。
なので今後は、
frontend
-> かなり改善
next:
LSU / D-cache / store buffer / memory hierarchy
という流れになりそうです。
まとめ
今回やったことを短くまとめると、
1. Rocketと共通assembly benchmarkで比較した
2. MiNTsの余分なcycleがbranch回数に比例していると分かった
3. fetch-side BTBで約1 cycle / branchを削った
4. fetch/issue bypassとI-cache follow-on requestで残りのbubbleを削った
5. branch-heavy loopではRocketとほぼ同等になった
6. Linux 100MでもCPI 2.529 -> 2.393まで改善した
自作CPUを作っていると、最初は「命令が正しく動くか」が中心になります。
でもLinuxが動き始めると、次は、
なぜ遅いのか
どこで詰まっているのか
どう直すと効くのか
を見る段階になります。
今回のbranch predictor/frontend改善は、その入口としてかなり面白い題材でした。