Zen 5の2-Aheadブランチ予測器: 30年前のアイデアが開く新たな可能性
(chipsandcheese.com)- AMD Zen 5はZenアーキテクチャの全面的な再設計の中で2-Ahead Branch Predictorを導入し、1990年代のマルチブロック先行分岐予測研究を現代x86フロントエンド拡張へ再び持ち込んだ
- 分岐予測は、条件分岐の結果が出る前でもCPUフロントエンドが命令を取り続けられるようにする仕組みであり、予測失敗はパイプラインフラッシュと再開コストにつながる
- Zen 5は32KBのL1命令キャッシュに32バイト/サイクルのfetch pipeを2本備え、それぞれを4-wide decode clusterに接続し、Op Cacheもdual-portedの6-wide構成で最大12個のoperandをOp Queueへ供給する
- 新構造は1サイクルにtaken branchを2個、非連続の命令ブロックにまたがって処理し、5ビット長フィールドで3つ目の予測ウィンドウの開始位置を見つけて、デコードおよびOp Cache資源の過剰使用を抑える
- x86は可変長命令のため命令境界判定の並列化が難しく、2-Ahead Branch Predictorと二重のfetch・decode構造がZen系フロントエンド拡張の中核的な変化となっている
Zen 5フロントエンドで変わった点
- AMDはZen 5をZenアーキテクチャの全面的な再設計として紹介しており、2-Ahead Branch Predictorはその中でも目立つ要素となっている
- この構造は30年前の論文で扱われたアイデアを土台に、単一コア性能をさらに引き上げようとする流れの中で再登場した
- 複数のtaken branchを一度に予測できれば、フロントエンドはより先にある命令ストリームまで先読みできる
分岐予測がCPUパイプラインに必要な理由
- 現代のCPUは、命令取り出し(fetch)、デコード、実行を複数段階に分けるパイプライン構造を採用している
- 条件分岐があると、フロントエンドは条件評価が終わる前に次に取り出す命令位置を決めなければならない
- 可能な選択肢は大きく2つある
- 分岐結果が出るまで停止する
- 次の経路を予測し、外れた場合は誤った作業を捨てて確実な地点から再開する
- 予測が外れると、その推測に依存した作業をパイプラインから除去するflushが必要になる
- 分岐条件で停止するコストは、instruction fetchとbranch condition評価完了の間にあるパイプライン段数に比例する
- 結局のところCPUは、プログラムの命令フローを可能な限り正確に予測しなければならない
2-Aheadというアイデアが登場した文脈
- 単純な予測方式として、短いbackward jumpを常にtakenとみなす戦略があり、常に次のアドレスを取りにいく方式より歴史的に大きな利点を持っていた
- 直近の分岐履歴やアドレス記録のような小さな状態を維持すれば、実際のプログラムでより良い結果を得られる
- 数十KB規模の構造だけでも90%台後半の分岐予測率が可能だった
- 2-Ahead Branch Predictorは1990年代初頭から議論されていた提案であり、当時から8-wide以上へアーキテクチャ幅を広げる問題とあわせて扱われていた
- その後、商用CPUがマルチコアへ移行すると個々のコア面積の重要性が増し、学術界ではより面積効率の高いTAGE predictorの改善に注力するようになった
- プロセス微細化によって同じ面積により多くのトランジスタを載せられるようになり、数百個規模のout-of-order CPUへ拡張する流れとともに、単一コア性能への関心も再び高まった
x86フロントエンドがより難しい理由
- 64-bit Armのように固定長命令を使うISAは、instruction cache lineの任意部分を並列にデコードしやすい
- 入力データを保証された命令バイト境界で分割し、decoder logicを複製すればよい
- x86は命令長が可変のため、各命令の次の境界を知るにはinstruction byteを線形に解析しなければならない
- prefixを先に部分デコードするようなパイプライン化である程度の並列化は可能だが、x86ではそのコストは低くない
- 性能重視のx86コアで4-wide decodeが長らく一般的だった背景もここにある
- Intel Golden Coveの6-wide decodeのような設計は、最新プロセスでの論理密度向上によって実用化できたが、monolithic parallel x86 decodingの面積・電力コストはwidthの増加に対してsuper-linearに増える
- 一般的なアプリケーションの整数コードは、おおむね5〜6命令ごとに1つのbranchという程度のbranch densityを持ち、decoder幅をさらに大きく広げる動機を弱めている
- x86フロントエンドには、命令境界判定という並列化しにくい段階を飛び越え、安全に次の命令境界へ到達する手段が必要になる
Zen 5の二重fetch・decode実装
- “Multiple-block ahead branch predictors” by Seznec et al. は、2-Ahead Branch Predictorの理由と実装方法を扱った中核的な論文である
- 複数のtaken branchを処理するpredictorだけでは不十分であり、Seznec et al.は、面積要求を爆発させずに活用するにはinstruction fetch dual-portingが必要だと考えた
- Zen 5はinstruction fetchとOp Cacheをdual-port構造に変更した
- 32KBのL1 instruction cacheから32バイト/サイクルのfetch pipeを2本使用する
- 各fetch pipeは独自の4-wide decode clusterに接続される
- Op Cacheはdual-portedの6-wide設計で、Op Queueへ最大12個のoperandを供給できる
- Branch Target Bufferもdual-portingの対象に含まれる
- Zen 5のL1 BTBがアクセス可能な16K entriesという大規模さは、dual-ported L1 BTBの可能性を説明できる
- L2 BTBは8K entriesで、L1 BTBより小さい
- AMDはL2 BTBをvictim cacheに近い形で使っており、L1 BTBからevictされたentryがL2 BTBへ移動する
1サイクルでtaken branchを2個処理する方式
- Zen 5は、非連続の命令ブロックにまたがって1サイクルでtaken branchを2個処理できる
- この変化により、taken branchに遭遇した際のfetch帯域損失を減らし、2つのtaken branchの先まで予測できるようになる
- 2つ目のtaken branch以降のinstruction streamをより遠くまで見通せるため、3つのprediction windowを持てる
- 3つのprediction windowはいずれもdecode用の命令生成に活用できる
- 2つ目のprediction windowには5ビット長フィールドが付く
- decodeまたはOp Cache資源が過剰予約される状況を防ぐ
- ポインタより小さいが、3つ目のprediction windowの開始位置を提供する
- 3つ目のprediction windowがcache line boundaryをまたぐ場合でも、次サイクルのprediction lookup indexのために追加状態を保存する必要がない
- 3つ目のprediction windowが1つ目または2つ目のprediction windowと同じcache line内にある場合、その部分的な3つ目のwindowは完全な3つ目のprediction windowほど有効ではない
SMTで残る制約
- Zen 5では2つのスレッドがアクティブになると、decode clusterに結び付いたfetch pipeは静的に分割される
- この状態でdual fetch coreのように動作するには、L1 instruction cacheとOp Cacheの両方からfetchする必要がある
- AMDがOp Cacheをdual-port化した理由は、dual fetch pipelineをより良く維持するためかもしれない
あわせて言及された関連論文
- “Multiple-block ahead branch predictors” by Seznec et al. – ASPLOS 1996: 2-Ahead Branch Predictorの理由と実装方針を扱う
- “Optimization of Instruction Fetch Mechanisms for High Issue Rates” by Conte et al. – ISCA 1995: 高いissue rateに向けたinstruction fetch機構の最適化を扱う
- “Increasing the instruction fetch rate via multiple branch prediction and a branch address cache” by Yeh et al. – ICS 1993: multiple branch predictionとbranch address cacheによるfetch rate向上を扱う
- “Out-of-Order Instruction Fetch using Multiple Sequencers” by Oberoi and Sohi – ICPP’02: multiple sequencerを活用したout-of-order instruction fetchを扱う
- “Parallelism in the Front-End” by Oberoi and Sohi – ISCA 2003: CPUフロントエンドの並列性を扱う
1件のコメント
Hacker News のコメント
分岐予測について初期の実装から分かりやすく説明している記事としては、https://danluu.com/branch-prediction/ が良い
[0]: https://www.youtube.com/watch?v=nhXevKMm3JI&list=PLzH6n4zXuc...
[1]: https://www.youtube.com/watch?v=nczJ58WvtYo&list=PLzH6n4zXuc...
SMT 性能がどうなるのか気になるし、今回のアプローチが利益をもたらしつつ、次世代でさらに磨き込まれることを期待している
Zen5c は 192 コアまたは 384 vCPU まで行き、来年の Zen 6c では 256 コアが可能になりそうだ。デュアルソケットの 1U サーバーなら、潜在的には 512 コア、1024 vCPU になる
2014 年に直面していた Web アプリのスケーリング問題は、今では冷却さえできればサーバー 1 台に収められる。vCPU あたり 1 RPS と見積もっても、キャッシュヒットを除いて 1000 RPS で、HN のフロントページでさえサーバーに秒間 1000 ページビューを叩き込むわけではない
HPC 性能がどうなるのか気になる。冷却自体は大きな問題ではないかもしれないが、ある時点からは直接液冷（DLC）が必要になる「ウェット」な問題になるかもしれない
GPU を搭載した高密度サーバーラックを 1 台のマシンと見なすなら、すでに数百キロコアまで来ている
Wikipedia 規模のサービスをサーバー 1 台で提供できるという考えを理解できない人と議論したことがあるが、かなり面白かった。すでにしばらく前から簡単なことで、ただ可用性やコスト効率といった現実的な理由でそうしていないだけだ
直感的には、同じ問題を半分の速度で処理する作業が増えるならメモリ使用のコストがあるはずだと思うが、SMT を有効にしたときに速度面の利益なしにメモリだけ多く使うアプリがよくあるのか気になる
公開されているベンチマークの多くでは、ほとんどのアプリが実行速度で目に見える利益を得ていないように見える
何十年も前の論文が当時は大して注目されずに発表され、ハードウェアが十分に強くなって突然最先端になるのを見るのは、いつも興味深い
例えば Z-buffer がある。3D ビデオゲームで使われているが、最初に論文に登場したときは、テーマとしてではなく、メモリを大量に必要としすぎるという理由で脇道のように扱われていた
数十年後にはメガバイトがかなり安くなり、結局すべてのリアルタイム 3D レンダラーが使うようになった
David MacKay が再発見するまで、文献上では 38 年ほど空白があったようだ
最初の主流での利用は 2003 年で、今では WiFi、Ethernet、5G で使われている
[1] https://en.wikipedia.org/wiki/Low-density_parity-check_code
[2] https://scholar.google.com/scholar?q=%22low+density+parity+c...
図書館に行って、コンピューターサイエンスの研究者たちが紙の論文として発表していたものを読んでみれば、当時は非現実的だったが今なら実装可能なアイデアがあるかもしれない
この 20 年、単一コア性能は水平スケール、つまりより多くのコアを優先する中で抑えられてきたため、個々のコアの複雑さとダイ面積が問題になった。こうした流れがなく、CPU 設計者が主に単一コア性能を追求していたなら、もっと早い実装を見ていたと思う
Z-buffer は単純な概念なので、論文では脇道のように見えたのだろう。より良い例はレイトレーシングかもしれない。3D グラフィックスの背景がなくても概念自体はかなり明快だが、最近までリアルタイムレンダリングには性能面で非現実的だった
興味深いのは、現実に近いレンダリングを近似するもっと単純なアプローチを見つけられず、古く、やや素朴で高価な解法へ戻らざるを得ない点だ
多くの研究者は、部分構造型システムは事実上ガベージコレクションに押されて死んだと見ていたが、Rust が当時の C++ の新しいアイデアと組み合わせて復活させた
この追加のメモリ帯域要求が、きちんと実装することを難しく高価にした。高級な実装では専用 RAM チャネルを使っていたが、低価格のハードウェアでは共有メモリインターフェースの帯域を大きく奪っていた
例えば一部の N64 ゲームは、深度情報を読み出して更新するコストを避けるために Z-buffer をオフにし、背景／前景の描画をソフトウェアで管理するよう最適化していた
投機予測器は、プライベートデータを抜き出すためのさまざまな攻撃対象になってきた
一般的な ISA の多くが脆弱なら、こうした攻撃の影響を減らすための対策をしているのか気になる
これを防ぐ方法は、海を沸騰させるレベルのアプローチ[0]を除けば存在しない。投機実行は性能面であまりに価値が大きく、これがないコンピュータはまったく使い物にならないほどだ。本当に投機実行のないプロセッサが欲しいなら、古い初代 Pentium を買えばよい
実際的な緩和策はいろいろあるが、少なくとも秘密を持つ被害者プロセスと、被害者の実行に影響を与えられる潜在的な攻撃者との間で、プロセス分離を保証する必要がある
Intel はリングをまたいで投機実行してしまったため、ユーザー空間からカーネルやハイパーバイザーのメモリを読み取れた。設計がまともな CPU なら、主に心配すべき対象は HTML iframe だ
異なるオリジンは HTTP リクエストを自由に送ることはできないが[1]、許可なしに互いを含めることはできる[2]。従来はその情報が攻撃者プロセスにロードされ、タイミング攻撃で漏えいし得た
Web の初期の解法は、iframe をプロセス分離するのではなく、共有メモリのマルチスレッディング自体を取り除くことだった。攻撃者からタイミング基準を奪えば、被害者が何を投機実行しても問題は小さくなる。ただし、そのためにはマルチスレッディングをなくす必要がある。そうしないと、あるスレッドが既知のデータをループ内で繰り返し書き込んで時計を作れてしまうからだ
[0] https://hackaday.com/2013/08/02/the-mill-cpu-architecture/
[1] 少なくとも対象オリジンが CORS で許可していない限り不可能
[2] 例: 画像の直リンクや iframe 埋め込み
予測そのものに内在する脆弱性ではない
この分野の初心者としては、記事を読んでも 2-ahead 分岐予測器が正確に何なのかはっきりしない
90 年代にはどちらか一方に近かったが、現代のプロセッサはほとんどが両方を備えているようだ
“Multiple-block ahead branch predictors” の要旨では、現在の命令ブロックの情報を次の命令ブロックのアドレス予測に使うのではなく、その次のブロックを予測する方式だと説明している。これにより、広いディスパッチを持つ “brainiac” プロセッサで命令フェッチのボトルネックを減らし、1 サイクルに 2 つの命令ブロックアドレスを効率的に予測できる
また “speed demon” プロセッサでは、分岐予測プロセスをパイプライン化することで、より高いクロックや、より大きな予測構造による精度向上を得られるという。従来の複数予測器方式と異なり、複数ブロック先読み分岐予測器はどんな分岐予測方式でも利用できる
[0] https://dl.acm.org/doi/10.1145/237090.237169
付け加えると、eyegor がすでにリンクを投稿していたようだが、せめて要旨だけでも読んでほしいという意味だ
次の分岐予測よりはるかに難しいだろうが、より深いパイプラインに供給するコードをずっと早くフェッチできるようになる
そのため、通常の分岐予測のように n+1 だけを事前評価するのではなく、n+2 の結果まで事前評価できる。これが L1 キャッシュを壊さずにどう動くのかはよく分からない
n+1 の先まで先読みする方式なら、キャッシュ追い出しがずっと増えそうなので、何か見落としている気がする
Zen 5 は 2 つ目の taken branch の先にある命令ストリームまで、さらに遠くを見られ、その結果、デコードする命令を作るうえで有用な予測ウィンドウを 3 つ持てるという
元論文はオープンアクセス可能だが、まだあまり読めていない: https://dl.acm.org/doi/10.1145/237090.237169
分岐の各方向は新しい命令ブロックの開始へつながり、そのようなブロックの最後の命令は通常また別の分岐になる
つまり分岐予測器は、次のブロックのアドレスを当てる装置だ。2-ahead 分岐予測器も同じことをするが、後続の 2 つのブロックについて行う
論文の表現どおりなら、「現在の命令ブロックの情報が、次の命令ブロックの後に来るブロックのアドレスを予測するために使われる」
一般的な分岐予測器と違い、次のブロックの命令がデコードされるまで待たなくても可能だ。そのため、複数の命令デコーダに同時に供給できる
これは、命令デコーダがボトルネックになっている現代 CPU で特に有用だ。サイクルあたり 1 命令しかデコードしないデコーダ 1 個では、サイクルあたり 4〜6 個のような多くの命令を実行できる広いフロントエンドに追いつくのが難しいためだ
分岐ヒントがもっと必要かもしれない: https://github.com/ziglang/zig/issues/5177
cold、warm、warmer を用意し、hot はデフォルトなので省略する、といった形にできるのではないかと思う。場合によっては、1 つを除くすべての分岐を cold に指定することもあり得る
たぶん悪い考えなのだろうけれど、理由を知りたい
条件分岐があるとき、可能な両方の分岐の命令をどちらもフェッチして準備しておき、間違った側を捨てる、というのはなぜダメなのか気になる
それがずっと難しいことなのか、それとも価値がなくなる別の理由があるのか知りたい
現代の TAGE 分岐予測器は 99% をはるかに超える精度で当てる。だから反対側の分岐の追加命令は、ほとんど常に捨てられる
さらに悪いのは、フロントエンドが、バックエンドで実際の方向を確認できる地点よりも数十個の分岐ぶん先までフェッチすること。次の分岐ではどうするのか？ 可能な分岐を 4 個デコードし、その次は 8 個、16 個、32 個をデコードするのか？ ほとんどは捨てることになる
複数の命令ストリームを並列にフェッチできるハードウェアがあるなら、Intel Gracemont/Goldmont/Skymont や AMD Zen 5 のように、より良い戦略は分岐予測器が 100% 正しいと仮定すること。一方の分岐をたどり、その次もたどる
Intel Skymont には 3 個のデコーダがあり、それぞれ 3-wide なので、次の 3 個の分岐先を並列にデコードする。Intel は大きなコードブロックを分割するために偽の分岐まで入れて、3 つのデコーダが今後来る命令ストリームの異なる部分を常にデコードするようにしている。その後、3 つのマイクロ演算ストリームをマージし、Skymont がサイクルあたり 9 命令の有効デコード帯域を維持できるようにする
両方の分岐を実行しても、分岐予測が外れるまれな場合に遅延を少し減らすだけ。一方、片方向に次の 2、3 回の予測を続けてたどれば、Intel と AMD は複数のデコーダを並列に働かせられる。Intel はより単純な 3-wide デコーダ 3 個で 9-wide を作り、AMD はより単純な 4-wide デコーダ 2 個で 8-wide を作れる
コンパイラ、ランタイム、CPU などは、どちらの結果がよりありそうかをよく当てられるし、そもそも追加作業をしないほうがたいてい良い戦略。外れた場合に備えて、シリコンと熱を間違った答えに使うよりまし
多くの人は、分岐予測がどれほど正確になり得るかについて直感がないように思う。自分のコードを見るだけでも、「ほとんどの制御フローはこちらへ行き、この分岐は例外的な状況を処理するためにあるのだな」とすぐ気づく
最近のコンパイラもこれをかなりうまく推論するし、CPU/JIT/ランタイムも印象的なヒューリスティックを作れる。それでも失敗する場合は、コードに明示的なヒントを入れて、コンパイラなどに期待される方向を伝えられる
現代 CPU の命令リオーダバッファは数百命令の深さがあり、その中に条件付きジャンプが 8 個あるだけで、プログラムが取り得る経路は 256 個になる
分岐予測器が 8 個すべてを当てる確率が 50% を超えるなら、実際そうなのだが、備えるために256 倍の作業をする価値はない
より多くのマイクロアーキテクチャ状態を保持するためのシリコンと、その手法を完全に活用するためのより多くの実行ユニットが必要になる。だがスーパースカラ CPU では、分岐の少ないコードで命令レベル並列性を活用するために、そうしたものはすでに必須なので備わっている
残りはエイリアシングや割り込みのような複雑なものを処理する厄介な作業だが、ハードウェアエンジニアは魔法使いのようなもので、こういうこともやってのける
ただし投機実行はキャッシュタイミングのサイドチャネルを悪用して、投機的に実行されただけでアーキテクチャ上の副作用はコミットされていないコードが触れたデータから、情報を抜き出せる可能性を開く。つまり「実際には」実行されなかったコードからでも情報が漏れ得る
これには条件チェック、たとえば権限チェックのために明示的には実行されなかったコードも含まれる
よく知られた攻撃例が Spectre: https://en.m.wikipedia.org/wiki/Spectre_(security_vulnerabil...
だから基本的にまったく割に合わない。そのチップ資源は別のスレッドやコアに使うほうがずっとよい
良いアイデアか判断するには、まず性能データを見たい。このアプローチの分岐予測ペナルティに関する情報もない
いずれにせよ、このアプローチの直感は、L1 命令キャッシュやマイクロ演算キャッシュにまだないかもしれない命令を、積極的にフェッチしてデコードすることにあるように思う
これは x86、そしておそらく RISC-V でも重要。どちらも命令長が可変なので、命令キャッシュブロックを見るだけでは、コアはそのブロック内の命令をどうデコードすべきか分からない。どちらの ISA でも、命令キャッシュブロックのデコードを始めるには、少なくとも 1 命令の PC を知る必要がある
そのため、アプリケーションが 2 ブロック先でどこへジャンプできるか分かれば、現在のアプローチよりさらに先までフェッチしてデコードする助けになる
このアプローチは命令プリフェッチに似ているが、命令プリフェッチは開始地点の情報をコアに与えない
高性能 ARM コアは、すべての命令長が 32 ビットなので「開始地点探し」の問題に遭遇しない可能性が高い。したがって開始地点を知らなくても、デコード手順を並列化できる
この方式は、フロントエンドの比重が大きいアプリケーション、たとえばホットなコードブロックがバイナリ全体に散らばっているクラウドワークロードに恩恵を与えそう。他の種類のアプリケーションでは性能上の利益や損失があるのか気になる
いまだに2-ahead 分岐予測器が何なのかまったく分からない
一般に古い研究論文は、読者がこうした話題についてずっと少ない知識しか持っていないと想定している。当時はこうした知識がはるかにニッチだったから
いま必要なのは メモリ帯域幅。コンシューマー向け AM5 ソケットのメモリチャネル 2 本は、この程度の演算性能に比べると、特に基本的な Apple Silicon と比べても見劣りする。
重厚な Zen 構成から M2 Max に移行したが、メモリ帯域幅の向上が集中的なデータ処理をどれほど高速化するのか、あらためて驚かされた。かなり重いマルチタスクでも、Zen 構成の狭いメモリパイプは頻繁に詰まっていた。
人々が特に LLM のために Apple Silicon に注目する理由は、LLM は GPU により適しているものの、大量の VRAM も必要で、NVIDIA が VRAM の多い GPU に法外な価格を付けているからだ。
AMD が本気で NVIDIA の勢いを削ぎたいなら、64〜128GB の VRAM を搭載したコンシューマー向け GPU を売るべきだ。