後藤弘茂のWeekly海外ニュース
AMDがZen 2で採用した現在最強の分岐予測「TAGE」
2019年6月25日 11:00
AMDは新CPU「Zen 2」マイクロアーキテクチャにおいて、現状で最強と言われる分岐予技術「TAGE(テイジ)」を採用した。
TAGEは「TAgged GEometric history length branch prediction」の略で、“タグ付けした幾何級数的な履歴長(History Length)による分岐予測”と言う意味だ。説明はあとに回すが、学会レベルでは、TAGEは最強の分岐予測技術とされており、2006年の発表以来、派生や改良技術が次々に発表されている。
IPCをZenからさらに引き上げたZen 2マイクロアーキテクチャ
AMDのZenは、ニューラルネットワーク系の「パーセプトロン(Perceptron)」分岐予測を搭載しているが、Zen 2からはパーセプトロンとTAGEの2階層構成の分岐予測となる。パーセプトロンがL1分岐予測、TAGEがL2分岐予測だ。
パーセプトロンも比較的新しい技術で、Zen 2は分岐予測の新技術を2つ搭載するというじつに贅沢な構成となった。もっとも、TAGEの実装は「重い」ので、Zen 2での実装がどこまでのものか、まだわからない。
AMDは、Zen世代のCPUマイクロアーキテクチャになってから、IPC (Instruction-per-Clock)の向上にフォーカスしている。
前世代(Bulldozer)のCPUでは、シングルスレッド性能を抑える代わりに、マルチスレッドの性能密度を高めることに集中した。それに対して、ZenではIPCを高めてシングルスレッド性能を引き上げる。
これは、クライアントPC市場では、非常に競争力を増す特徴だ。Zen 2では、さらにそれを推し進め、IPCとシングルスレッド性能をアップさせている。
AMDを率いるLisa Su氏(President and Chief Executive Officer,AMD)は、「E3 (Electronic Entertainment Expo) 2019」に合わせて行ったイベント「AMD Next Horizon Gaming」で、Zen 2ではZenからIPCをさらに15%引き上げたと高らかに宣言した。
これが真実なら、かなり異例だ。CPUのIPCを引き上げることはかなり難しいので、Zenの延長線の改良で15%というのは、何か大きな技術要因がなければ難しい。その要因は、まず間違いなくTAGE分岐予測だ。
数%の分岐精度の向上が性能を左右する
AMDで技術開発を統括するMark Papermaster氏(Chief Technology Officer and Executive Vice President, Technology and Engineering, AMD)は、「我々は多くの時間を分岐予測のステージの改良に費やした。(履歴)テーブル群を追加し、ビット(タグビットのことを指すとみられる)を追加し、コードストリームがどちらへ向かうのかをより正確に推測できるようにした。その結果、IPCが顕著に上がった」と語る。
AMDによると、TAGE分岐予測の導入などの分岐予測の拡張による、分岐予測ミスレート(Mispredict Rate)は最大30%低減がターゲットだという。
「(このスライドで)言おうとしたのは、おおむね予測ミス率が30%ほど下がる、ということだ(What we tried to generally say you get about 30% lower mispredict rate)」とZenのアーキテクトであるMike Clark氏(Corporate Fellow & Zen Architect, AMD)は語る。
ちょっと奥歯に物が挟まったような言い方だが、分岐ミス率はワークロードによって変動が大きく、言い切りにくいというのもあるだろう。
TAGEなら30%よりもっと下がるのでは、という見方もあるかも知れないが、30%でもインパクトは大きい。
もちろん、30%低減は予測ミスのレートに対してなので、たとえばあるプログラムで97%の予測精度だった場合は、98%に精度が向上するという意味になる。このケースでは、予測精度では1%の差だ。
しかし、分岐予測ミスのペナルティは非常に大きいため、この程度予測精度の向上が性能に与える影響は大きい。
まだ細かな性能は出ていないのでわからないが、AMDはZen 2のIPC向上率を、Zenに対して15%、Zen+に対して10数%の向上としている。
分岐予測の精度で大きく変わるCPUの性能
現在の高性能CPUにとって、条件分岐命令は鬼門だ。分岐命令を実行するまで、分岐する(Taken)か分岐しない(Not Taken)かわからないからだ。
高性能なスーパースカラCPUでは、性能を高めるために深いパイプラインで命令を並列に実行する。パイプラインにつねに命令を供給することが、性能の維持に必要となる。
ところが、条件分岐命令が来ると、分岐が判明するまで、次にどの命令をフェッチすればいいのかわからなくなってしまう。
そこで、現在の高性能CPUでは、予測した分岐先の命令を実行する投機実行を行なっている。分岐の結果がわかる前に、予測した命令ストリームをCPUに取り込んでパイプラインに流している。
投機実行の問題は、分岐の予測を間違えると、フェッチしてパイプラインに取り込んだ命令をすべてフラッシュして、正しい命令をフェッチし直さなければならないことだ。
CPUの記事では、投機実行とアウトオブオーダ実行を混同しているケースがあるが、両技術は異なり、投機実行はミス時のパイプラインフラッシュがあることが重要な問題となっている。
現在の高性能CPUでは、分岐予測ミスのペナルティは非常に大きい。(ミスプレディクション)パイプラインが10段以上と深く、複数の命令を並列に処理しているからだ。予測をミスした場合は、10数サイクル以上のロスとなり、命令並列性を考えると、最大で数10命令をフラッシュしなければならない。
このように、分岐予測ミスのペナルティが極めて大きいため、分岐予測精度の向上は大きな課題となっている。たとえば、95%程度の予測精度の場合は、CPUのIPCは、理想値から30%程度も下がってしまうと言われている。そのため、精度の違いが1%程度でも性能を大きく左右する。
Zen 2では分岐予測を2段階に再編成
AMDは、Zen 2において、フロントエンドの分岐予測(Branch Prediction)を大幅に手直しする道を選んだ。
AMDは、Zenで分岐予測に、単階層のニューラルネットワークである「パーセプトロン分岐予測ユニット」を導入した。AMDは、それ以前に低電力のJaguar系のCPUコアで、ニューラルネットワークベース(パーセプトロン)の分岐予測を採用しており、Zenの分岐予測はその流れにあった。つまり、Zenの分岐予測はJaguarを搭載するPlayStation 4の分岐予測の拡張版だった。
だが、AMDは、Zen 2でパーセプトロン分岐予測に加えて、「TAGE」分岐予測を導入することで、分岐予測を新たなステップに引き上げた。
「Zen 2では、TAGE分岐予測を加えた。しかし、Zen 2では、依然としてパーセプトロン分岐予測も備えている。TAGE分岐予測は、セカンドレベルのプレディクタ(予測器)であり、分岐予測が2段階になった。TAGEは、より多くのテーブルとタグを使うことで、命令ストリームのフローをよりよく予測できるようにする」(Mike Clark氏)。
TAGE分岐予測は、従来のパーセプトロン分岐予測を置き換えるものではなく、追加の分岐予測ユニットの位置付けだ。AMDによると、パーセプトロンがL1分岐予測で、TAGEがL2分岐予測だという。
ちなみに、L1とL2というのは分岐予測で読み込むキャッシュレベルの話ではなく、分岐予測のレイテンシの話だ。
L1キャッシュからの命令フェッチがパーセプトロンプレディクタに行き、L2キャッシュからの読み込みをTAGEプレディクタをかけるといった話ではない。また、単純に分岐履歴を2段階にしたという話でもない。予測アルゴリズム自体が2種類の異なるものを備えている。
Zen 2フロントエンドでは、命令フェッチラインから、まずL1パーセプトロンで予測した値を得て、遅れてL2 TAGEの値を得ている。両者の予測が異なった場合は、L2 TAGEの値を採用する。
「TAGEでは、非常に多くのテーブルで大きな(履歴の)参照をするので、シングルサイクルなどでの予測ができない。だから、我々はパーセプトロンを迅速な予測に使い続けることにした。そのうえで、TAGEプレディクタで予測をする。すると、(パーセプトロンによる)最初の予測が正しいかどうか検証できる。間違えていた場合は、正しい予測へと戻すことができる」(Clark氏)。
Zen 2は、パーセプトロン分岐予測とTAGE分岐予測の2段階の構成となっているが、TAGE分岐予測は、もともとベースとなる分岐予測(TAGEのタグを使わない)と組み合わせるのが基本なので、2段階は一般的な構成だ。
たとえば、TAGEを採用するRISC-Vの「BOOM2」CPUでは、GShare分岐予測が1次、TAGE分岐予測が2次となっている。つまり、TAGE分岐予測は、もともとレベル2のレイテンシのある予測として使うことが想定されている。
ただしTAGEの論文では、ベース分岐予測は、通常もっとシンプルな方式を仮定しているので、L1に複雑なパーセプトロン分岐予測が入るのは異例ではある。
パーセプトロン分岐予測とTAGE分岐予測が2つの新技術の流れ
そもそもの技術的な動向から見ると、CPUの分岐予測には、比較的新しい流れとして2つの技術が浸透しつつある。1つはニューラル系分岐予測で、もう1つはTAGE分岐予測だ。
ニューラルネットワークベース分岐予測は1999年に「Towards a High Performance Neural Branch Predictor」(Vintan, L. and Iridon,M., IJCNN, 1999)で、TAGE分岐予測は2006年に「A case for (partially) TAgged GEometric history length branch prediction」(A. Seznec, and P. Michaud. J. Instruction-Level Parallelism, 2006)で世の中に出た。
シンプルなニューラルネットワークであるパーセプトロンを使った分岐予測は、AMDのZenとBobcat/Jaguar、Samsungの「Exynos M1」、Oracleの「Oracle SPARC T4」のS3コアなどに採用されている。それなりに採用例がある技術だ。
一方のTAGEは、分岐予測という狭い領域では有名な手法だ。非常に高い分岐予測精度を達成できるためだ。分岐予測には「CBP(Championship Branch Prediction)」と呼ばれる精度を競うイベントがある。TAGEはこのCBPでチャンピオンシップを取っており、予測精度は学会レベルでは認知されている。
それなのに、TAGEやTAGEから派生した分岐予測は、実際のCPUへの採用例はこれまで少なかった。それは、TAGEの実装に、トレードオフがあるからだ。
機構はあとで解説するが、TAGEでは異なる履歴長に対して、並列にルックアップを行なうため、ハードウェア規模が大きくなる。ハードウェアが並列化するため、電力消費が多くなる。多くのテーブルを参照するため、高い精度の最終結果が得られるまでのレイテンシも長くなる。
だがここへ来て、採用が進み始めた。判明している採用では、Zen 2以外に、RISC-VのスタートアップであるEsperantoの高シングルスレッド性能CPUコア「ET-Maxion」と、その元になったRISC-Vの「Boom2」などがTAGE分岐予測を採用する。また、中国のPhytium TechnologyのArmサーバー「Mars」のXiaomiコアもTAGEを使っていた。
Zen 2とMaxionについては、TAGEの採用は、どちらも7nmプロセスであることと関連していると見られる。7nmプロセスによってTAGEを実装できるだけのトランジスタバジェットが手に入り、電力面のトレードオフも許容しやすい範囲になったと推測される。
Intelとの熾烈な分岐予測技術競争
CPUにとってクリティカルな分岐予測において、AMDはIntelに追いつけ追い越せモードにある。
IntelはSandy Bridge系アーキテクチャからHaswell系アーキテクチャへの移行時に、分岐予測を大きく変更した。その結果、Haswell以降のIntel CPUでは分岐予測精度が極めて高くなり、一部で話題になった。
しかしIntelは、分岐予測アーキテクチャについては秘密を貫いており、Haswellから採用しているアーキテクチャについても一切明らかにしない。このことが、分岐予測という技術の、CPUアーキテクチャの中での重要性を表している。AMDとしては、性能/電力競争でIntelに勝つため、Intel CPUの分岐予測精度に迫る必要がある。
そして、IntelがHaswellで導入したと言われているのが、今回話題となっているTAGE分岐予測だ。
Haswellの分岐予測技術については、TAGEの提唱者などの論文「Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore」(Erven Rohou, Bharath Narasimha Swamy, Andre Seznec,International Symposium on Code Generation and Optimization,Feb 2015)で、TAGEの応用を使っている可能性が高いことが指摘されている。
こうして見ると、分岐予測という技術を巡って、IntelとAMDが熾烈な戦いをしている状況が浮かび上がって来る。
AMDが、Zen 2において、分岐予測という根幹に関わる技術で手を入れたのは、Intelを追っているためだ。IntelがTAGEを導入して成功しているのなら、AMDもTAGE分岐予測を導入するのは自然な流れに見える。
ちなみに、AppleのArm CPUコアも、TAGEを採用しているという噂がある。
それぞれの分岐パターンに最適な履歴長で予測ができるTAGE分岐予測
TAGE分岐予測は「TAgged GEometric history length branch prediction」という名前のとおり、異なる履歴長(幾何級数的な長さの比率)の分岐予測を並列に行なうことで、従来では予測できなかった分岐パターンの検出を可能とする。
現在の動的分岐予測の本質は、パターンの解析だ。単純に言えば、過去の分岐について、分岐(Taken)と分岐せず(Not Taken)の履歴を記録しておいて、そのなかから現在の分岐パターンと一致するパターンを見つけて、次の条件分岐が分岐するかしないかを予測する。一般的にはNot Takenが0、Takenが1だ。
単純化すると、予測しようとしている分岐の直前の分岐パターンが「110001」だった場合、それとマッチするパターンを履歴から探す。「1100011」がマッチした場合は、次の分岐がTakenの1になると予測できる。
しかし、現在の高性能CPUの分岐予測には1つのジレンマがある。大多数の分岐は相対的に短い履歴長(History Length)で予測ができる。ところが、一部、長い履歴長でなければ予測できない難しい分岐がある。しばしば100ビット以上、場合によっては1,000ビットの履歴長が必要な分岐が現れるという。
こうした長い履歴を必要とするパターンをうまく予測できないと、分岐予測の精度を現状以上に上げにくい。しかし、長い履歴長に合わせた設計にすると、短い履歴は逆にうまく予測できなくなったり、予測のコストが上がってしまう。
TAGE分岐予測はこのジレンマを解消し、短い履歴で予測できるパターンと、長い履歴を必要とするパターンの両方をうまく満たす手法を実装している。
まず履歴テーブルにタグをつけ、並列化されたプレディクタ(予測器)がタグ付けされた履歴を使い、異なる履歴長(History Length)でマッチングを行なう。このとき、履歴の長さを幾何級数的に増やすのがポイントで、2倍、4倍、8倍といった長さにしていく。そして、マッチした予測のうち、もっとも長い履歴長の結果を取る。
たとえば、最短の履歴長でパターンがヒットしたが、2番目の履歴長ではヒットせず、3番目の履歴長でパターンがヒットした場合、3番目の履歴長を採用する。
「TAGEでは複数のテーブルを使って、それぞれ異なる量の履歴を参照する。TAGEでは、(コンポーネントの列に)沿って履歴を段々と長くしている。もし、複数(のコンポーネントが)がヒットしたら、もっとも長い履歴の結果を採用する。典型的には、最長の履歴からの予測がもっとも正確な予測だからだ」(Clark氏)。
TAGE分岐予測を採用する、RISC-VのBOOMアーキテクチャのドキュメントでは、分岐パターン毎にもっとも正確な予測ができる履歴長が異なるが、TAGEでは固定された単一の履歴長ではなく、異なる履歴長によってそうした要求に応えることができるとしている。
また、従来では扱えなかった非常に長い履歴長を使うことで、従来の分岐予測の制約を突破できる。
BTBなどの分岐予測リソースも拡張
AMDがZenで採用したパーセプトロン分岐予測も、リソースを増やすことで予測精度を高めやすいという特性を持つ。にも関わらず、AMDがZen 2では、パーセプトロン予測の拡張ではなく、TAGE予測の追加というアーキテクチャ選択に出たのは、それだけTAGEの効果が大きいためだとみられる。
Zen 2の分岐予測では、このほかに分岐の飛び先のバッファである「BTB(Branch Target Buffer: ブランチターゲットバッファ)」などのリソースも拡張された。
Zenアーキテクチャでは、BTBは3レベル構成。L0 BTBは16エントリで、これはZenと変わらない。しかし、L1 BTBはZen 2では512エントリと、Zenの256エントリの2倍になった。L2 BTBはZen 2では7Kで、Zenの4Kの1.75倍だ。
このほか、インダイレクトブランチのためのIndirect Target Array (ITA)も、512エントリから1Kに拡張された。
じっさいには、BTB以上に「BHT (Branch History Table: 分岐履歴テーブル)」が強化されているはずだが、この部分はTAGE分岐予測の実装にも関わる部分だけに、公開されていない。BTBは、言ってみれば公開してもあまり害のない情報で、BHTの方が重要だ。TAGEはタグビットを使う分だけ、よりエクスペンシブだ。
ちなみに、AMDは初代ZenのBHTは、Bulldozer系のPiledriverの2倍のサイズだと明かしている。公開されていないが、Piledriverもパーセプトロン分岐予測を実装していた可能性があり、その場合は同系列アルゴリズムでBHTのサイズを変えて精度を上げたことになる。
Zen 2でのTAGE分岐予測の採用で、分岐予測技術の競争は新しいステージに入った。今後は、TAGEのような複雑な予測技術が商用CPUに浸透していくと見られる。
その背景には、プロセス技術の現状がある。プロセスの微細化と「Design-Technology Co-Optimization (DTCO)」によって、搭載できる回路数は増えるが、電力の壁で動作周波数は上げにくい。分岐予測にトランジスタを費やして、性能効率をアップさせるのは、高性能CPUにとってリーズナブルな選択となる。