後藤弘茂のWeekly海外ニュース

AMDの次世代CPUコア「ZEN」のニューラルネットワーク分岐予測機能

ニューラルネットワークをCPUコアに内蔵したZEN

 AMDは、来年(2017年)の第1四半期に予定する「ZEN」マイクロアーキテクチャCPUの投入に力を入れている。第1弾となる、8コアの高性能デスクトップCPU「Summit Ridge」は、新ブランド「Ryzen」で投入される。AMDにとって、6年ぶりのCPUマイクロアーキテクチャの大刷新。そして、シングルスレッドパフォーマンスでIntel CPUに対抗できるコアとあって、AMDにとっては久々に強力な武器となる。

 ZENマイクロアーキテクチャは、Intelも採用した内部命令(マイクロOPs:Micro-OPs)のキャッシュ「OPキャッシュ」など、高性能化と低電力化に大きな効果があるテクニックを導入。また、Intel同様にSMT(Simultaneous Multithreading)も導入する。パッと見ると、AMDがIntelアーキテクチャの利点を取り入れたように見える。しかし、ZENには、それらのテクニックを、フロムスクラッチのクリーンなアーキテクチャで実現した利点がある。

AMDのZENマイクロアーキテクチャのブロックダイアグラム図
PDF版はこちら
AMDのCPUマイクロアーキテクチャの変遷の概要
PDF版はこちら

 AMDは、段階的にZENマイクロアーキテクチャの詳細を明らかにしつつある。最近、AMDが明らかにしたマイクロアーキテクチャの大きな特徴は、「ニューラルネットワーク分岐予測ユニット」だ。AMDはZENの分岐予測(Branch Prediction)には、ニューラルネットワーク型の技術が使われており、オンザフライで分岐パターンを学習して精度を向上させると説明した。

ZENマイクロアーキテクチャはニューラルネットワーク分岐予測を採用
ZENマイクロアーキテクチャの新機能

 現在のCPUはパイプライン化されており、プログラムの連続した命令をパイプライン上でどんどん実行する。問題は条件分岐で、条件が判定され分岐命令で分岐するかしないかが決定した段階で、既に10サイクルかそれ以上の命令がパイプラインに流れている。分岐しないと予想して、分岐命令の後続の命令を実行していた場合、パイプライン上の命令を全部フラッシュして、分岐先の命令を取りこむことから始めなければならない。その間、CPUのパイプライン処理はストール(停止)してロスが生じる。ロスは、CPUを空回りさせて性能を落とすだけでなく、無駄な動作により消費電力も増やすことになってしまう。

 そこで、条件分岐命令でどちらに分岐するのかを予測することで、分岐のロスを減らす分岐予測が必要となる。分岐方向を予測して、予測した先の命令ストリームを実行する「投機実行(Speculative Execution)」を行なう。CPUの記事では、アウトオブオーダ(Out-of-Order)実行と投機実行が混同されることがあるが、両テクニックは異なる。

 分岐予測の精度が高ければ、CPUのパイプラインは円滑に動作を続けることができる。その分、性能が上がり、消費電力が下がる。電力効率が命となっている現在のCPUにとって、分岐予測は最も重要な技術だ。CPU設計で、各社が最もしのぎを削っているのが分岐予測だと言ってもいい。x86 CPUの場合は命令デコードとデコード済み命令キャッシュも同様に重要で、ZENでは、この2つの改良に大きな特徴がある。

PlayStation 4(PS4)も採用したニューラルネットワーク分岐予測

 ZENアーキテクチャでは、分岐命令の予測アルゴリズムに、“ニューラルネットワーク”のアプローチを使っている。しかし、ZENのニューラルネット分岐予測は、最近のニューラルネットワークブームに乗って実装されたものではない。ニューラルネットワークベースの分岐予測自体は、新しいテクニックではないからだ。……特に、AMDにとっては。

 というのは、AMDは、既に「Jaguar」系のCPUコアで、ニューラルネットワークベース(パーセプトロン)の分岐予測を採用しているからだ。JaguarはIntelのAtomにあたる省電力CPUコアで、省電力APU(Accelerated Processing Unit)や組み込み、ゲーム機に使われている。身近なところで言えば、JaguarコアのPlayStation 4(PS4)は、ニューラルネットワーク分岐予測を使っている。

PlayStation 4(PS4)のAPUに使われているJaguar CPUコアのマイクロアーキテクチャ
PDF版はこちら

 ZENのニューラルネットワーク分岐予測は、同社の低電力CPUコアから持ってきた技術ということになる。PS4は、ZENの分岐予測技術を先取りしているとも言える。ただし、AMDのBulldozer系のCPUコアの分岐予測技術も全てが公開されているわけではない。そのため、Piledriver世代からニューラルネットワーク分岐予測が導入された可能性もある(そうした報道もある)。

 CPUの分岐予測テクニックについて悩ましいのは、CPUメーカーがひたすら隠したがることだ。分岐予測の一般的なテーブルのサイズなどは明らかにするが、具体的なアルゴリズムになると、口を閉ざす。分岐予測アルゴリズムは、CPUマイクロアーキテクチャの差別化のキモであり、他社に知られたくないためだ。

 Jaguarのニューラルネット分岐予測についても、学会等でのJaguarの技術発表の際は公開されなかった。しかし、AMDの「APU 101: All about AMD Fusion Accelerated Processing Units」などのドキュメントでは、片隅に、Series CとSeries EのAPUには、ニューラルネットロジックの分岐予測(Neural Net Logic Branch Predictor)が組み込まれていると書かれている。公式に発表はしないが、ポロっとこぼすイメージで、実に歯がゆい。

SamsungのGalaxy S7もニューラルネットワーク分岐予測を採用

 分岐予測では、ニューラルネットワークと言っても、ディープな「コンボリューショナルニューラルネットワーク(CNN:畳み込みNN)」などを使うわけではない。最もシンプルな「パーセプトロン(Perceptron)」を使う。1999年には原型となるアイデアが論文発表されている。2001年の論文「Dynamic branch prediction with perceptrons」(Daniel A. Jimenez and Calvin Lin, the 7th International Symposium on High Performance Computer Architecture (HPCA-7), January 2001)で広く知られるようになった。その後も研究と改良が進められており、注目されている予測テクニックの1つだ。

 実際のプロセッサでも、AMD以外にも複数の製品でニューラルネットワーク分岐予測技術が採用されている。AMDの低電力CPUコアであるJaguarと「Bobcat」、Oracleの「Oracle SPARC T4」のS3コア、そして、Samsungの「Exynos M1 Processor」だ。M1は、SamsungのSoC(System on a Chip)「Exynos 8890」に搭載されており、同社のスマートフォン「Galaxy S7」などに使われた。

 ちなみに、BobcatとM1のメインのアーキテクトは同じBrad Burgess氏(現VP, Chief CPU Architect Samsung Austin R&D Center(SARC))だ。分岐予測が似通うのも当たり前と言える。さらに元を辿ると、Burgess氏はIntelのキャンセルになったCPU「Tejas」のアーキテクトであり、その前はMotorola PowerPCのアーキテクトだった。

 ニューラルネットワーク分岐予測は、上にリストしたCPU以外にも採用されている可能性はある。ただし、分岐予測については、各社が秘密のベールに包むため、分かりにくい。Intelが協力している論文も複数出ており、Intelも熱心に研究していることが分かる。

ニューラルネットワーク分岐予測を搭載したSamsungのM1は元AMDアーキテクトが開発
ニューラルネットワーク分岐予測の発案者であるDaniel A. Jimenez氏(Department of Computer Science and Engineering, Texas A&M University)の「Championship Branch Prediction 2016」でのスライド(「Multiperspective Perceptron Predictor」)には、同系のアイデアを採用したCPUの一覧がある

パターン認識型の機械学習問題である条件分岐の予測

 なぜ、分岐予測でニューラルネットワークなのか。それは、原理的に相性がいいからだ。分岐予測のアルゴリズムは、もっとも基本的な2ビットのバイモデル(Bimodel)分岐予測の場合は、下のようなステイトで予測を行なう。

・高い可能性で分岐する「Strongly taken」
・低い可能性で分岐する「Weakly taken」
・低い可能性で分岐しない「Weakly not taken」
・高い可能性で分岐しない「Strongly not taken」

 4値のステイトマシーンで、分岐が成立すると分岐の予測可能性が高いステイトへと遷移する。この基本のバイモデルを見ると、ニューラルネットワーク(NN)の重みの変化による予測を適用できそうな気がしてくる。実際の分岐予測アルゴリズムには、より多様なパターンに対応できる2レベル適応型分岐予測、さらに、広域分岐履歴を使うグローバル分岐予測、そして、そこから発展した「gshare」とさまざまな予測テクニックが発展、組み合わせられている。バイモデルほど単純ではない。

 しかし、分岐予測というものの根源は、典型的な機械学習問題(Machine Learning Problem)だと見ることができる。分岐予測の目的は、プログラムのストリームの中で、条件分岐命令が分岐するパターンを解析することだからだ。ニューラルネットワークベース分岐予測の最初の論文「Towards a High Performance Neural Branch Predictor」(Vintan, L. and Iridon,M., IJCNN, 1999)でも、分岐予測はパターン認識問題の1つだと論じている。それなら、ニューラルネットワーク型の学習アルゴリズムで、分岐のパターンを認識し分類できれば、予測精度が高まるというストーリーだ。簡単に言えば、ニューラルネットワークによって画像の中からパターンを抽出して認識できるのなら、分岐命令の分岐パターンも抽出して予測できる、ということになる。

ニューラルネットワーク分岐予測の発案者の1人のJimenez氏は、分岐予測がマシンラーニング問題だと指摘する。「Perceptrons for Dummies」(Daniel A. Jimenez, Championship Branch Prediction,2004)

ハードウェアリソースが大きくなると予測精度が上がる

 ニューラルネットワーク分岐予測の基本的なアイデアは、1層のパーセプトロン(Perceptron)で、分岐パターンを学習するものだ。最も基本的なアプローチでは、分岐履歴からのインプット、つまり過去の分岐の履歴それぞれに、オンラインでの学習結果の重み(weight)を付けて推論を行なう。実際には、ニューラルネットワークベースの分岐予測も、過去10年以上の間に発達しており、さまざまな論文が発表されている。

 ニューラルネットワーク分岐予測にもいくつか問題点が指摘されている。リソースの増大とレイテンシはこのアプローチの課題で、これについては改善する手法がいくつも提案されている。ニューラルネットワークなので、履歴に対して重みデータが必要となり、その分リソースを食うことになる。また、学習(Training)は履歴が長ければ長くかかる。

分岐予測をパーセプトロンモデルで実現する。「Multiperspective Perceptron Predictor」(Daniel A. Jimenez, Championship Branch Prediction 2016, 2016)

 もっとも、Jimenez氏は、ニューラルネットワーク分岐予測の利点は、履歴の長さに応じて精度を上げることができることだとしている。ニューラルネットワークでは、必要とするリソースは履歴サイズに対してリニアにしか増えないが、従来アプローチでは指数関数的に必要リソースが増えてしまうためだという。そのため、ニューラルネットワーク分岐予測の方が、一定以上の精度向上に対しての必要リソースが相対的に少なくて済むという。ハードウェアリソースの増加によって、一般的なアルゴリズムであるGshareやBi-Modeよりも予測精度が上がるシミュレーション結果などが報告されている。

パーセプトロン分岐予測はハードウェア規模が大きくなるにつれて、既存のアルゴリズムよりも予測精度が上がる。「Perceptron Learning for Predicting the Behavior of Conditional Branches」(Daniel A. Jimenez and Calvin Lin, IJCNN '01. 2001)

 上のグラフは、同じハードウェアリソース量の枠内での予測精度を比較したものだ。分岐予測ユニットのハードウェア規模が小さい場合は、ニューラルネットワークベースの方が余計なリソースを必要とする分、精度が落ちてしまう。しかし、リソースの規模が大きくなると、相対的に予測精度が上がるという構図となっている。こうしたシミュレーションの通りなら、分岐予測ユニットの規模が大きくなれば、ニューラルネットワークベースの方が予測精度が上がることになる。

分岐履歴のテーブルを長くしたZENアーキテクチャ

 AMDは、ZENにおいて、従来のAMD高性能CPUコアよりも、ブランチヒストリテーブル(Branch History Table)のサイズを2倍にしたと説明している。ニューラルネットワーク分岐予測が、リソースが増えれば予測精度が上がりやすいとすれば、ZENでは、従来の分岐予測アルゴリズムの場合より、予測精度が向上していることが期待できる。ちなみに、こうした性格から、ニューラルネットワーク分岐予測は、ほかのシンプルなアルゴリズムと組み合わせて使われていると見られる。

パーセプトロンのコンセプトを分岐予測に適用。「Perceptrons for Dummies」(Daniel A. Jimenez, Championship Branch Prediction,2004)

 AMDのニューラルネットワーク分岐予測の実装の詳細は分からない。しかし、通常の分岐予測のテーブル以外に、パーセプトロンの重みデータを持つバッファを持つことは確実だ。これについては、AMDの特許に記述がある。「US20150121050 Bandwidth increase in branch prediction unit and level 1 instruction cache」。

 この特許では、重みアレイを含むテーブルを持つ「Hash Perceptron(HP)」が説明されている。ちなみに、特許では、HP自体も、L1とL2の2層構造になっており、ZENの実装が2レベルのニューラルネットワーク分岐予測になっている可能性を示している。特許では、L1 HPによる予測は1バブルとなっており、特許通りなら高速な予測が可能だ。L2に行くとレイテンシが最大4バブルと長くなる。

ZENマイクロアーキテクチャのフロントエンド

 ZENの分岐予測ユニットの基本は、Jaguarとよく似ている。分岐先の予測アドレスを保持する「Branch Target Buffer(BTB)」はL1命令キャッシュと密接に統合されていると見られる。BTBは1エントリにつき2ブランチをトラックできる、つまり2つの分岐を1サイクルに予測できる。BTBのサイズは、まだ明らかにされていない。このほか、間接分岐に対する「ITA(Indirect Target Array)」、リターンスタックに対する32エントリのテーブルも持つ。

 ちなみに、ZENは実行ユニット群に分岐ユニットを2ユニット持つ。2つの分岐ユニットは、SMT(Simultaneous Multithreading)で2スレッドがそれぞれ分岐を実行することも、1スレッドで2つの分岐を実行することもできる。後者の1スレッドで2分岐の場合は、おそらく、先行する分岐命令の予測が分岐しない(not taken)場合のみ、といった制約がある可能性がある。ZENの場合は、1サイクル2分岐マシンであるため、分岐予測の精度はさらに重要となる。