Building an Out-of-Order CPU

第59回 情報科学若手の会でのショート発表資料です．

Transcript

1. 自作 CPU を Out-of-Order にする RISC-V CPU beigecore の OoO 化で学んだこと Latte72 (@Latte72R)
2. 01 自己紹介 自己紹介 名前: Latte72 趣味 所属: 慶應義塾大学理工学部 情報工学科 3 年 低レイヤー全般が好き X / GitHub: @Latte72R ます Web: https://latte72.net/ 自作 OS や自作コンパイラもやってい インターンとか 大学の機関のサーバーチームで LLM の運用などを担当しています 2
3. 01 自己紹介 セキュリティ・キャンプ 2026 L2 プロセッサゼミ（CPU 自作班）に参加！ 参加の動機 自作 OS on 自作 CPU をしたい ゼミでの成果 3 人で各自 RV64 CPU を自作してベンチマークで競い合う 最終日に自作 OS on 自作 CPU を達成！ 本日の発表内容 その beigecore をさらに Out of Order にした記録！ 3
4. 02 Veryl について Veryl について モダンな Hardware Description Language SystemVerilog を基礎に，Rust など現代的な言語の影響を受けた構文を採用 人間が読める SystemVerilog へトランスパイル Compiler 自体が Rust で実装 パッケージマネージャやフォーマッタなどの開発環境が最初から充実している メンテナー メンテナーに日本人が多く，公式 Discord に japanese というチャンネルがある！ 4
5. 02 Veryl について Generics SystemVerilog のコード例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 function automatic logic [20-1:0] FuncA_20 (input logic [20-1:0] a); return a + 1; endfunction Verilog function automatic logic [10-1:0] FuncA_10 (input logic [10-1:0] a); return a + 1; endfunction logic [10-1:0] a; logic [20-1:0] b; always_comb begin a = FuncA_10(1); b = FuncA_20(1); end ビット幅ごとに別々の関数を個別定義する必要があり，記述が冗長になりやすい 5
6. 02 Veryl について Generics Veryl のコード例 1 2 3 4 5 6 7 8 9 10 11 12 function FuncA::<T: const> ( a: input logic<T>, ) -> logic<T> { return a + 1; } Veryl var a: logic<10>; var b: logic<20>; always_comb { a = FuncA::<10>(1); b = FuncA::<20>(1); } ジェネリクスにより，ビット幅違いの関数やモジュールを共通コードでスマートに定義可能 6
7. 02 Veryl について Type inference Explicit 1 2 3 4 5 6 7 8 var a: logic<8>; Veryl let b: logic<8> = a; let c: logic<8> = 8'd10; let d: logic<8> = Func(a); let e: logic<8> = GenericFunc::<8>(a); 従来の書き方では，代入や関数の戻り値を受けるたびに型（ビット幅）の明示が必要 7
8. 02 Veryl について Type inference Inferred 1 2 3 4 5 6 7 8 var a: logic<8>; Veryl let b = a; let c = 8'd10; let d = Func(a); let e = GenericFunc(a); 右辺の式や関数定義から型・パラメータが自動推論され，宣言を大幅に簡潔化できる 8
9. 02 Veryl について Veryl に Contribute してみた 簡単なことしか貢献できていないが，コミュニティの方が親切でやりやすい～ 9
10. 余談はさておき… CPU の話をします！ 10
11. 03 自作 CPU 自作 CPU「beigecore」 言語: Veryl で実装 ISA: RV64IMAC + Zicsr / Zifencei 特権: 最低限の特権機構 (M-mode, U-mode, S-mode) OS: OpenSBI + 自作 OS が起動可能！ 構造: 元はシンプルな 5 段階 In-Order パイプライン 実はもともと若干 Out of Order っぽい実装を入れていた 本発表の内容 In-Order な beigecore を，Out-of-Order へ改造していった過程と学びを紹介 ハードウェアの記述の話からしていて，実は OoO の話は少なめですがご了承ください… 11
12. 04 ハードウェア設計 ソフトウェアとハードウェアの違い (1) 理論上の実行時間 ＝ サイクル数 × クロック周期 クロック周期を決めるのが「クリティカルパス」 レジスタから次のレジスタまでの間で，最も伝搬遅延が長い組合せ回路の経路 どんなにサイクル数を減らしても，クリティカルパスが伸びれば全体は遅くなる！ 12
13. 04 ハードウェア設計 ソフトウェアとハードウェアの違い (2) C 言語（ソフトウェア） 1 2 a = b + c; d = e + f; Veryl（ハードウェア） C 1 2 assign a = b + c; assign d = e + f; 基本的には「何をどの順番で実行するか」 2 つの加算器回路が物理的に存在し， という時系列を記述 毎サイクル同時に動く Veryl ソフトウェアのような実行順序ではなく，回路が同時に動くことを意識する 13
14. 04 ハードウェア設計 クリティカルパスとは何か？ 「最も伝搬遅延が長い経路」がクロック周波数を決める Reg A (FF) NOT ... AND 遅延: 0.8 ns Reg B (FF) AND ... OR MUX 次段 Reg群 遅延: 1.5 ns Reg C (FF) NOT MUX AND ... (Capture) OR 遅延: 2.2 ns Reg D MUX AND MUX OR MUX (FF) 遅延: 3.8 ns（クリティカルパス） ... MUX ※ 遅延値は例 回路全体のクロック周期は，最も遅延の長い「クリティカルパス」で決まる 他の経路にどれだけ余裕があっても，この 1 箇所が全体の動作周波数を制限する 14
15. 04 ハードウェア設計 ソフトウェアとハードウェアの違い (3) 愚直に複数候補から最優先を選ぶ 1 2 3 4 5 6 7 8 9 10 let result: data_type = switch { select[0]: data[0], select[1]: data[1], select[2]: data[2], select[3]: data[3], select[4]: data[4], select[5]: data[5], select[6]: data[6], default : data[7], }; Veryl select は one-hot ではなく，複数 bit が同時に 1 になる（優先順位つき選択） 順に条件分岐する switch を書くと，前の条件の不成立待ちが数珠繋ぎに直列化される 15
16. 04 ハードウェア設計 ソフトウェアとハードウェアの違い (3) トーナメント方式で選択を高速化 1 2 3 4 5 6 7 8 let select_low : logic = select[0] || select[1] || select[2] || select[3]; let low_data01 : data_type = if select[0] ? data[0] : data[1]; let low_data23 : data_type = if select[2] ? data[2] : data[3]; let high_data45: data_type = if select[4] ? data[4] : data[5]; let high_data67: data_type = if select[6] ? data[6] : data[7]; let low_data : data_type = if select[0] || select[1] ? low_data01 : low_data23; let high_data : data_type = if select[4] || select[5] ? high_data45 : high_data67; let result : data_type = if select_low ? low_data : high_data; Veryl 空間的な配置を意識し，トーナメント方式で並列に選択 4 並列（1 段目）→ 2 並列（2 段目）→ 最終段 と段階的に絞り込む 16
17. 04 ハードウェア設計 直列 MUX の回路構造 8 候補から順に選ぶと 7 段 switch 構文で生成される直列回路 d[7] d[6] d[5] d[4] d[3] d[2] d[1] d[0] 2:1 MUX 2:1 MUX 2:1 MUX 2:1 MUX 2:1 MUX 2:1 MUX 2:1 MUX sel[6] sel[5] sel[4] sel[3] sel[2] sel[1] sel[0] result 信号が 7 個の MUX を直列に通過し，ロジックデプス（段数）は最大 7 段 遅延が 𝑂(𝑁 ) で累積し，クリティカルパスとなると動作周波数（Fmax）が悪化 17
18. 04 ハードウェア設計 並列 MUX の回路構造 トーナメント方式ならわずか 3 段 トーナメント方式による並列選択 【1段目: 4並列】 d[0] d[1] 2:1 MUX 【2段目: 2並列】 【3段目: 最終選択】 low_data01 / 23 2:1 MUX d[2] d[3] d[4] d[5] d[6] d[7] low vs high 2:1 MUX 2:1 MUX 2:1 MUX result high_data45 / 67 2:1 MUX 2:1 MUX トーナメント方式で並列評価し，ロジックデプスを 3 段に短縮 データ選択の遅延を𝑂(log 𝑁 )に短縮し，高クロック動作を維持できる 18
19. 05 パイプライン化 5 段階パイプライン構造（元の beigecore） 各ステージ間をレジスタで区切り，それぞれ別の命令を同時に処理する IF Reg ID Reg EX Reg MEM WB Reg 命令フェッチ 命令デコード 演算実行 メモリアクセス レジスタ書き戻し (組合せ回路) (組合せ回路) (組合せ回路) (組合せ/SRAM) (RegFile) 1 クロックの区切り ＝「Register → 組合せ回路 → Register」 ステージ間の Pipeline Register で区切ることで，複数命令の並行処理を実現 各ステージは「Register → 組合せ回路 → Register」のクリティカルパス単位 19
20. 05 パイプライン化 パイプライン化で嬉しいこと 改善する主対象は 1 命令の完了時間ではなく「スループット」 パイプラインなし（直列実行：5サイクルに1命令完了） 命令 1 C1 C2 C3 C4 C5 IF ID EX MEM WB 命令 2 C6 C7 C8 C9 C10 IF ID EX MEM WB 5段階パイプライン（並行処理：毎サイクル1命令完了！） 命令 1 命令 2 命令 3 命令 4 C1 C2 C3 C4 C5 C6 C7 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM C8 WB 1 命令のレイテンシは変わらないが，理想的には毎サイクル 1 命令を完了できる 20
21. 05 パイプライン化 OoO 化前の性能（ベースライン） CoreMark cycles Critical Path 969,835 3.770 ns 5 段階 In-Order パイプライン構成におけるベースライン（理論上の実行時間：3.66 ms） この時点を性能比較の出発点とします 21
22. 07 Out-of-Order 化 In-Order パイプラインの限界 命令レベル並列性（ILP）が存在していても，十分に活用できない 1 2 3 ld add xor x1, 0(x2) x3, x1, x4 x5, x6, x7 # メモリアクセス待ち # x1 に依存 # 上2命令とは独立 RV64 ld x1 読み出し待ち RAW 依存 先行する add がデータ待ちになると，後続の xor が実行可能でも先に進めない （パイプラインが停止） add Wait （実行不可） xor Ready （独立なのに停止！） 実行可能な後続命令を，先に実行できないか？ → 依存関係のない命令を追い越して実行する Out-of-Order 実行 へ 22
23. 06 Out-of-Order 化 Out-of-Order（OoO）実行とは？ 実行順序を崩しながら，結果の確定だけは元の順序を守る 1 サイクル目 2 サイクル目 3 サイクル目 ld x1, 0(x2) 実行 ld x1, 0(x2) add x3, x1, x4 x1 待ち add x3, x1, x4 x1 待ち（停止） add x3, x1, x4 xor x5, x6, x7 待機 xor x5, x6, x7 先行実行！ xor x5, x6, x7 メモリ読出中 ld x1, 0(x2) 完了 実行（x1 到着） 完了 beigecore では，実行順を変えても Commit は元の順番で行う 23
24. 06 初期 OoO 化の試み 当初の目標：手軽に OoO っぽくしてみたい 最初から本格的な構成を作ったわけではない 最初は「手軽に OoO っぽくできないか？」と考え，最小限の拡張から着手 行ったアプローチ ① メモリアクセス中に独立した演算を進める（ROB 導入＋MEM 分離） ② 演算結果をすぐ後続で使えるようにする（Forwarding / Bypass 追加） ③ 分岐によるパイプライン停止を減らす（動的分岐予測＋BTB） 24
25. 06 初期 OoO 化の試み 初期 OoO 実装後の性能 CoreMark cycles Critical Path 679,953 3.875 ns cycles は 970k ⇒ 680k で減少 Critical Path は 3.770 ns ⇒ 3.875 ns で増加 理論上の実行時間は 3.66 ms ⇒ 2.63 ms で短縮 ROB・Forwarding・分岐予測（Bimodal/BTB）により cycles を大幅削減 25
26. 07 主要コンポーネント Reorder Buffer (ROB) 演算が終わっても，それ以前の命令が確定するまで待つ Reorder Buffer（プログラム順のキュー） [0] LOAD x2, 0(x1) 未完了 (メモリ待ち) ← Head [1] XOR x5, x6, x7 完了 (Complete ✓) 先行完了！ [2] ADD x3, x4, x5 完了 (Complete ✓) [3] MUL x8, x9, x10 実行中... Head が未完了のためCommit停止 先頭の LOAD が終わるまで 後続はコミット（確定）できない！ [1] XOR は実行終了済み しかし前の命令が終わるまで 確定を待たされる 演算は完了順に進むが，Commit（確定）はプログラム順に行う 26
27. 07 主要コンポーネント Writeback と Tag Broadcast 「値」は PRF へ，「タグ」は Issue Queue へ送る Physical Register File (PRF) result value Execution Unit PRF[p42] に実行結果の「値」を直接書き込み（Writeback） Issue Queue（待機中のエントリ群） 演算完了 (例: p42) tag: p42 Tag Broadcast を受信 各エントリの待ち物理レジスタ番号 (rs1/rs2_preg) と p42 を比較 該当エントリを Wakeup！ ready bit を立て，次cycle以降のIssue候補にする 演算結果の「値」は PRF に直書きし，待機中の命令へデータそのものは送らない キューには「タグ番号（p42）」だけを broadcast し，結果値の wide broadcast を避ける 27
28. 07 主要コンポーネント Register Renaming 偽の依存関係を解消する 元の命令列（論理レジスタ名） add x1, x2, x3 mul x1, x4, x5 同じ「x1」への書き込み（WAW依存） Free List: [ p32, p33, p34, ... ] RAT (論理 → 物理 写像表) x1 (初期) → p1 ADD後 → p32 MUL後 (最新)→ p33 名前が同じだけでデータは無関係！ Rename後（物理レジスタ） add p32, p2, p3 mul p33, p4, p5 保存先が p32 と p33 に分離！ → 偽の依存が消え、並列実行可能に！ 潤沢な物理レジスタに割り当て直すことで，レジスタ名の使い回しによる依存をなくす beigecore では物理レジスタは 64 本 28
29. 07 主要コンポーネント RAT と Free List Register Alias Table (RAT) 論理レジスタ（x0〜x31）が現在どの物理レジスタ（p0〜p63）を指すかの写像表 Free List（空き物理レジスタのキュー） デコード時に Free List から新しい物理レジスタを取り出す 注意: 古い物理レジスタは，上書きした命令が Commit するまで解放してはいけない！ （先行命令がまだ古いレジスタの値を読んでいる可能性があるため） 29
30. 07 主要コンポーネント Register Renaming へ移行後の性能 CoreMark cycles Critical Path 625,089 4.253 ns cycles は 680k ⇒ 625k で減少 Critical Path は 3.875 ns ⇒ 4.253 ns で増加 理論上の実行時間は 2.63 ms ⇒ 2.66 ms で増加 Register Renaming により WAW / WAR の偽依存を解消したものの，遅延が増加 30
31. 07 主要コンポーネント Issue Queue（スケジューラ） 準備ができた命令から順不同に実行ユニットへ送り出す Issue Queue（実行待ち行列） [0] ADD src1: Wait src2: Ready 入力待ち（待機） [1] XOR src1: Ready src2: Ready READY → Issue ! [2] SUB src1: Wait src2: Ready 入力待ち（待機） 実行ユニットへ [1] XOR を先行発行！ FIFO ではない 先頭が待機中でも 揃った後続を先に実行 プログラム順に投入されるが，オペランド（入力値）が揃った命令から先行実行 先頭がデータ待ちで止まっていても，準備完了した中から最も古い命令を Issue 31
32. 07 主要コンポーネント 再掲：ソフトウェアとハードウェアの違い (3) Issue Queue で Ready な最古命令を選ぶ 1 2 3 4 5 6 7 8 let select_low : logic = select[0] || select[1] || select[2] || select[3]; let low_data01 : data_type = if select[0] ? data[0] : data[1]; let low_data23 : data_type = if select[2] ? data[2] : data[3]; let high_data45: data_type = if select[4] ? data[4] : data[5]; let high_data67: data_type = if select[6] ? data[6] : data[7]; let low_data : data_type = if select[0] || select[1] ? low_data01 : low_data23; let high_data : data_type = if select[4] || select[5] ? high_data45 : high_data67; let result : data_type = if select_low ? low_data : high_data; Veryl 空間的な配置を意識し，トーナメント方式で並列に選択 4 並列（1 段目）→ 2 並列（2 段目）→ 最終段 と段階的に絞り込む 32
33. 07 主要コンポーネント Issue Queue 導入後の性能 CoreMark cycles Critical Path 564,984 4.470 ns cycles は 625k ⇒ 565k で減少 Critical Path は 4.253 ns ⇒ 4.470 ns で増加 理論上の実行時間は 2.66 ms ⇒ 2.53 ms で短縮 トーナメント選択で Ready な命令から順不同に Issue し，サイクル数削減が遅延増加を上 回る 33
34. 08 投機実行の制御 分岐予測ミスの Rollback RAT と Free List の Rollback 機構 ROB 内の命令列（Commit 待ち） 分岐より古い命令（保持） beq x1, x2, target RAT (写像表) の復元 ROB 末尾から 逆順に走査 ・命令 B の mapping 取消: x2 → 旧物理レジスタ ・命令 A の mapping 取消: x1 → 旧物理レジスタ ↳ 分岐直前の正しいマッピング状態へ復帰！ Mispredict! ② A を戻す 若い命令 A: x1 → p40 wrong path 若い命令 B: x2 → p41 wrong path Free List (空き物理レジスタ) の回収 ① B を戻す ・投機的に確保した p40, p41 は不要に ・Free List へ返却して再利用可能に （物理レジスタ枯渇によるストールを防止） ※ 分岐より古い命令は巻き戻さない 分岐予測ミス時，wrong-path の若い命令のレジスタ名前付けを取り消す必要がある ROB を末尾から逆順に走査し，RAT 写像と Free List を分岐直前の状態へ復帰 分岐より古い命令は巻き戻さず，安全かつ正確に復元 34
35. 08 投機実行の制御 Rollback 導入後の性能 CoreMark cycles Critical Path 506,847 4.870 ns cycles は 565k ⇒ 507k で減少 Critical Path は 4.470 ns ⇒ 4.870 ns で増加 理論上の実行時間は 2.53 ms ⇒ 2.47 ms で短縮 分岐予測ミス時に wrong-path 命令のみを巻き戻すことで，投機実行の無駄を削減 35
36. 10 おわりに 現状の beigecore の制約 現状の実装では，未完了の先行 Store がある場合は，先行 Store とのアドレス重複の可能性 を排除できないため待機が必要 Store Buffer を導入するとさらにサイクル数を減らせる 現状の実装では，分岐予測を Decode 時に行っている 実は，分岐予測は Fetch 時にも行うことができる 本当はもっとクリティカルパスも気にするべき 36
37. 10 おわりに まとめ 自作 CPU の OoO 化で得られた知見 1. 実際にパイプラインの流れを見ることが大切 Konata でパイプラインの流れを見ることで，高速化できそうなところを探せる 2. サイクル数とクリティカルパスの両立 サイクル数を減らしても，クリティカルパスが伸びると性能が悪化することがある 3. Veryl による快適な開発 モダンな構文や機能により，複雑な OoO パイプラインも楽しく実装できた 皆さんもぜひ，自作 CPU に挑戦してみてください！ 37
38. ご清聴ありがとうございました 質問・コメントなどお気軽にどうぞ！ Latte72 (@Latte72R)
39. 10 おわりに 補足など 説明を簡略化するため，中間の実装・修正 commit は省略しています． 性能値は各 checkpoint を基準に，既知の局所バグ修正，一部後続改善の backport，cycles を増やさない局所的な組合せ経路の整理を適用した benchmark 用 RTL による比較です． CoreMark の値は workload の cycle 比較であり，公式 CoreMark score ではありません． とても雑ですが，Critical Path をクロック周期とみなして，「推定実行時間 = サイクル数 × クロック周期」という式で比較しています． 39