FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

Meltdown, Spectre で学ぶ高性能コンピュータアーキテクチャ

巷ではIntel, AMD, ARMを巻き込んだCPUのバグ "Meltdown", "Spectre" が話題です。 これらの問題、内容を読み進めていくと、コンピュータアーキテクチャにおける重要な要素を多く含んでいることが分かって来ました。

つまり、このCPUのセキュリティ問題を読み解いていくと現代のマイクロプロセッサが持つ、性能向上のためのあくなき機能追加の一端が見えてくるのではないかと思い、Google, Intelの文献を読み解いてみることにしました。

が、私はセキュリティの専門家ではありませんし、過去にデスクトップPC向けのような大規模なCPU設計に参加したこともありません。 あくまでコンピュータアーキテクチャに比較的近い場所にいる人間として、この問題の本質はどこにあるのか、可能な限り読み解いていき、現代のマイクロプロセッサが持つ高性能かつ高機能な内部実装について解き明かしていきたいと思います。

と偉そうなことを書きましたが、私自身本質的なところの理解はまだ及んでいません。 3つの問題があると書いてありますが、それが全部根本的な原因は同じに見えるし、概念的なところでしか理解が及んでいないのが悔しい。

参考文献

Intel Analysis of Speculative Execution Side Channels

https://newsroom.intel.com/wp-content/uploads/sites/11/2018/01/Intel-Analysis-of-Speculative-Execution-Side-Channels.pdf

Reading privileged memory with a side-channel

https://googleprojectzero.blogspot.jp/2018/01/reading-privileged-memory-with-side.html

用語集

Googleセキュリティチームのブログには、用語集としてCPUの非常に重要な技術についての解説が簡単に書いてある。 これをきちんと理解するためには、現代のCPUが実装しているアウトオブオーダ実行技術と仮想化・キャッシュメモリのレイテンシについてきちんと理解する必要がある。

  • 投機実行
  • リタイア

An instruction retires when its results, e.g. register writes and memory writes, are committed and made visible to the rest of the system. Instructions can be executed out of order, but must always retire in order. (原文より)

現代のアウトオブオーダプロセッサは過度な投機実行を行うため、その投機実行を行った命令が本当に「正しい」命令であるかどうかを確認する必要がある。

アウトオブオーダ実行により外部メモリアクセスや計算に時間のかかる命令のレイテンシを隠蔽するために、長い命令と無関係な命令は順序を逆転して先に実行される。 特に条件分岐命令などは、条件がTrueかFalseかが分かり、さらに分岐先アドレスが決定されるまでにパイプライン中を何段も通過する必要があり、分岐命令の後続の命令は条件次第で実行すべきであったりそうでなかったりする。

従って、アウトオブオーダプロセッサでは、命令の発行は命令の順序を入れ替えても良いが、リオーダバッファなどの方式を用いて最終的には命令の順番をプログラムどおりに戻す。 分岐命令よりも後続の命令が、分岐命令よりも先に計算を終了したとしても、その結果はプログラムとしては確定に張らない。リオーダバッファに溜め込まれ、前の命令(条件分岐命令)の結果が確定したことをもってその命令が有効かどうかを決定する。このステージで「命令がコミット」されると、その命令が実行されることが確定し、リオーダバッファからレジスタファイルへのデータ書き戻しなどの確定処理が行われる。そうでなければ、その命令はリオーダバッファから「破棄される」。

このとき、コミットされた命令は命令の実行が確定したとして、最後の書き戻し処理を行って「リタイア」される。

リオーダバッファについては私のブログでも言及している。

msyksphinz.hatenablog.com

ちなみに上記の解説記事にも出てくるが、ロード命令は投機実行を行っても良い。しかしストア命令はダメだ。 何故かというと、ロード命令はロード値をレジスタファイルに書き込む前にリオーダバッファなどに格納して「破棄」することができる可能性を残しているが、ストア命令は発行してしまうとメモリの状態を変えてしまうため、破棄することが出来なくなる。従って、ロード命令のみ投機実行が行われ、ストア命令は投機実行されないというのが基本だ。

  • 論理プロセッサコア

A logical processor core is what the operating system sees as a processor core. With hyperthreading enabled, the number of logical cores is a multiple of the number of physical cores. (原文より)

いわゆるマルチスレッディング、ハイパースレッディングの技術である。 物理的なコア数よりも多くのコアがオペレーティングシステムからは見えるようになっており、パイプライン中に複数のプロセスが実行される。

1プロセスではパイプラインを埋めることが厳しいようなプログラムでも、独立した複数のプロセスを同時にパイプライン中に時分割で流すことにより、パイプラインを効率的に活用することが出来る。

  • キャッシュデータ・アンキャッシュデータ

In this blogpost, "uncached" data is data that is only present in main memory, not in any of the cache levels of the CPU. Loading uncached data will typically take over 100 cycles of CPU time. (原文より)

組み込み業界だけの話かと思ったらそうでもない。

一般的にリアルタイムデータや制御データなどのタイムクリティカルなデータは、キャッシュに入れてしまうと実際にコアの外のバスに流れるのがいつになるのか分からないため、アンキャッシュなデータとしてレジスタに持ってきたり、レジスタからストアする。

このようなアンキャッシュなデータはキャッシュを汚すことがないというのが1つの利点であり、またすぐにコア外のバスまで出て行くのでタイミングクリティカルな制御信号などを流すのに使われる。

f:id:msyksphinz:20180105230453p:plain
  • ミスプレディクションウィンドウ

The time window during which the CPU speculatively executes the wrong code and has not yet detected that mis-speculation has occurred.

上記の投機実行では、分岐予測が完了するまでとりあえず次の命令をフェッチして発行し続けるが、実際にはこれらの命令は条件分岐予測が外れることにより破棄されるかもしれない。

ミスプレディクションウィンドウは、この条件分岐命令において分岐予測に失敗することで、どれくらいの後続の命令が発行されるかを示しており、このウィンドウが大きいほど多くの命令が破棄される。

通常のレジスタ比較の命令ではレジスタリードしてから比較するだけのため、このウィンドウは比較的小さいと思われるが、例えばインダイレクトジャンプ命令(レジスタ間接分岐)の場合で、ターゲットのレジスタを外部の遠いメモリからロードしている場合はアドレス確定までかなり時間がかかる。 分岐の成立・不成立だけでなく、正しく分岐アドレスを予測できるのかが重要な鍵となる。

条件分岐予測って一見単純なようだが、

  • 条件を正しく予測できるか
  • 分岐先アドレスを正しく予測できるか

の2つが入り混じっており、結構面倒くさい分野であったりする。

バリアント1: Bounds check bypass

まず最初はこれ。理屈としては結構分かりやすい。

現代のアウトオブオーダプロセッサには、投機実行およびハードウェアプリフェッチという機能がある。 Intelのマニュアルにあるとおり、

Implicit caching occurs when a memory element is made potentially cacheable, although the element may never have been accessed in the normal von Neumann sequence. Implicit caching occurs on the P6 and more recent processor families due to aggressive prefetching, branch prediction, and TLB miss handling.

つまり、キャッシュ可能な領域であれば、ハードウェアが自動的にプリフェッチを走らせることもあれば、投機的にメモリフェッチを行うことがある。 これを、命令順どおりに実行されるわけではないという意味で「von Neumannシーケンス」ではないとしている。 分岐予測のペナルティを軽減するための機能でもあるし、TLBミスが発生する前にハードウェアプリフェッチを行っておくという機能もあるのかもしれない。

つまり、現代の高性能プロセッサはプログラムの意図しないところで勝手にプリフェッチを実行し、なるべくミス時のペナルティを軽減しようとしている。

これが間接分岐予測だとさらに問題は面倒になる。 レイテンシが長いため、もしL1→L2→L3と全てミスして外部までデータを取りに行き、順番にキャッシュを汚していく可能性があり、意図しないデータをキャッシュに持ってきている可能性がある。

以下の例が分かりやすい。

struct array {
 unsigned long length;
 unsigned char data[];
};
struct array *arr1 = ...; /* small array */
struct array *arr2 = ...; /* array of size 0x400 */
/* >0x400 (OUT OF BOUNDS!) */
unsigned long untrusted_offset_from_caller = ...;
if (untrusted_offset_from_caller < arr1->length) {
 unsigned char value = arr1->data[untrusted_offset_from_caller];
 unsigned long index2 = ((value&1)*0x100)+0x200;
 if (index2 < arr2->length) {
   unsigned char value2 = arr2->data[index2];
 }
}

条件分岐(if文)にarr1->lengthの要素が使われているが、この要素は実際に値を取ってくるまで分からない。

しかしプロセッサはif文が成立すると予測した場合、勝手にarr1->data[untrusted_offset_from_caller]をハードウェアがフェッチを行い、そのデータをキャッシュまで持ってきている可能性があるということだ。

バリアント2: Branch target injection

これも分岐予測についての基本的な考え方を理解するための良い教材だ。 ってか自分も良く分かっていないことが多い。

KVM(Kernel VM)という機構については少しだけ聞いたことがあるのだが、しっかり調べてみると以下のウェブサイトに行き着いた。 http://www.atmarkit.co.jp/ait/articles/0903/12/news120.html なるほど、要するにハードウェアの仮想化支援機能を使った仮想化であり、ベースにはLinuxなどのOSが存在する。 VMwareVirtualBoxと違い、ホストOSの上に仮想化層が必要ない、これによりオーバヘッドを削減することができる。

Haswellの分岐予測機構の構造

ここから、Haswellの分岐予測機構について怒涛の解説が始まる。

分岐予測といっても、その方式は1つではなく、命令の種類によって多くの分岐予測機構が存在し、その特性によって使い分ける。

通常の分岐予測機構

PC相対、レジスタ値やフラグなどの値に応じて分岐が成立するかを決める。この場合は分岐先アドレスは固定(PC相対)であることが多い。

MIPSRISC-V命令では、BEQ, BNEなどの命令がこれに該当し、レジスタ値を比較してPC相対でジャンプする。

間接ジャンプ(間接呼び出し)

関数呼び出しや関数ポインタをイメージすればよい。関数の存在場所はメモリ中にアドレスリストとして格納されており、CPUはそのアドレス情報をロード命令を使ってレジスタに取得し、レジスタ相対でジャンプする。

従って、この場合はレジスタ相対ジャンプであり、レジスタの値が決定するまでジャンプ先アドレスが決まらない。また、MIPSRISC-V等でいうjal命令のように、条件分岐というよりも分岐することは決まっており、その分岐先アドレスを予測することが重要になる。

関数戻りアドレスを予測する

これは間接ジャンプと考え方は良く似ているが、アドレスが予測しやすいタイプである。 関数呼び出しは、よっぽどのことがない限り関数が終了すると呼び出し元に戻ってくる。 従って、関数呼び出しの命令(例えばjal命令)が実行されれば、関数から戻ってくるときは必ずjal命令の次のアドレスからフェッチが始まるはずだということが分かる。

従って、この関数呼び出しの場所をスタックに保存しておき、関数から戻るとき(ret命令などが実行された場合)は、次の関数フェッチ先をスタックから取り出して命令フェッチに使用する。

一般的な分岐予測機構の仕組み

分岐予測を実現するためにはいくつかの機構が必要だが、ここでは、分岐ターゲットバッファ(Branch Target Buffer:BTB)、分岐履歴テーブル(Branch History Table:BHT)が紹介されている。

分岐ターゲットバッファはその名のとおり、ソースアドレス(現在のPCアドレス)から、次にどの命令をフェッチするか(分岐先はどこか)を記憶しておくバッファである。 Haswellの分岐ターゲットバッファはソースアドレスとしてPCの下位32ビットを使うとしている。例えばPCアドレス 0x4141_0004_1000 で分岐が実行され 0x4141_0004_5123 にジャンプしたとすると、そのジャンプ履歴がBTBに記録される。

PCアドレスのうち32ビットよりも上位のアドレスはBTBの検索には利用しない。とりあえず下位の32ビットを使ってソースアドレスの参照を行い、さらに後続のステージで分岐タグバッファを参照して32ビットよりも上のビットをチェックし、上位ビットもマッチすれば分岐予測がヒットしたとしてBTBのエントリ値が次のフェッチアドレスとして使用される。

しかし、下位32ビットを使うといっても、32ビットのアドレスエントリを持つBTBバッファを作ってしまうと、232のエントリを持つBTBテーブルを作る必要が生じてしまい、ここはエントリアドレスをさらに省略してBTBのエントリ数を減らす。

ここでアドレス圧縮(というかXORによるビット数減らし)が行われる。

bit A bit B
0x40.0000 0x2000
0x80.0000 0x4000
0x100.0000 0x8000
0x200.0000 0x1.0000
0x400.0000 0x2.0000
0x800.0000 0x4.0000
0x2000.0000 0x10.0000
0x4000.0000 0x20.0000

またこの表が非常に分かりにくい。 要するにこの表を使って、アドレスのマスクを行い、bitAとbitBの1になっている部分のアドレスビットを互いにXORし、その結果をBTBのエントリアドレスの一部として利用する。

f:id:msyksphinz:20180105234119p:plain
f:id:msyksphinz:20180105234316p:plain
  • 例その1. アドレス 0x0100_0000 と 0x0180_0000 は、23ビット目と14ビット目のXORが、0 xor 0 = 0, 1 xor 0 = 1 なので互いに異なり識別可能。
  • 例その2. アドレス 0x0100_0000 と 0x0180_8000 は、24ビット目と15ビット目のXORが、0 xor 0 = 0, 0 xor 1=1だが、23ビット目と14ビット目のXORが、0 xor 0 = 0, 1 xor 0 = 1 , なので互いに異なり識別可能。
  • 例その3. アドレス 0x0100_0000 と 0x0140_2000 は、26ビット目と17ビット目のXORが、0 xor 0 = 0, 1 xor 1=0なので識別できない。
  • 例その4. アドレス 0x0100_0000 と 0x0180_4000 は、27ビット目と18ビット目のXORが、0 xor 0 = 0, 1 xor 1=0なので識別できない。

となってしまい、最後の2つのアドレスはBTBエントリにとって区別がつかなくなる。

間接分岐ジャンプにも利用される分岐履歴テーブル

上記の例では、非常に単純なBTBのアドレスエントリ生成方式を見たが、実際には分岐履歴テーブル(Branch History Table:BHT)、もしくは分岐履歴バッファ(Branch History Buffer:BHB)との組み合わせで利用される。

Haswellには、この分岐履歴テーブルが29本あるとしている。 分岐履歴テーブルを利用して過去の29回分の分岐履歴(分岐した場合のみ)を格納している。

29本あるといっても何だか分からないので、もう少し噛み砕いて分岐履歴テーブルを解説してみよう。

局所分岐予測と広域分岐予測の考え方の違い

分岐予測には大きく分けて局所分岐予測と広域分岐予測の2種類の考え方がある。

局所分岐予測というのは、大学の学部の授業でも頻繁に登場する考え方だ。

「このアドレスの分岐命令は過去何度も分岐が成立しているから、次も成立するだろう」という考え方である。つまり、現在のPCアドレスとそのアドレスの分岐命令の結果しか見ないので、局所分岐予測と言われる。

ところが、プログラムのシーケンス的にはそうでない場合も存在する。

「このアドレスの分岐命令を実行する前に、1つ前はAの場所で分岐が成立、2つ前はBの場所で分岐外不成立だった。このパターンを見ると次の分岐は成立と予測できる」なんてケースがある。 これはC言語などで、if文を並べて書いているとこのような状況が普通に起きる。 つまり、今現在のPCアドレスの分岐命令の結果だけでなく、その1つ前に実行された別のPCアドレスの分岐予測の結果、さらに、過去の別PCアドレスの分岐予測の結果まで考慮して分岐予測を実行する。 このためこれを大域分岐予測と呼ぶ。

実際には、局所分岐予測の場合には各分岐命令毎に分岐履歴バッファを持ち、広域分岐予測の場合は、全ての分岐命令で共通の分岐履歴バッファを使うため面積は削減できる。

その代わり、広域分岐予測の場合は分岐履歴バッファを長めに保持する必要があり、履歴バッファが長くなるとそのパタンをアドレスとして用いるパタン履歴テーブルのエントリ数も長くなってしまうという弱点がある。 そして広域分岐予測は、十分テーブルを大きくしても局所分岐予測よりも成績が少し悪い。

このBHBのアップデートを示した擬似コードが、以下だ。分岐を実行したソースアドレスとそのとび先アドレスを次々とXORしていることが分かる。これにより、分岐のシーケンスが記憶され、次の分岐予測に使用される。

void bhb_update(uint58_t *bhb_state, unsigned long src, unsigned long dst) {
 *bhb_state <<= 2;
 *bhb_state ^= (dst & 0x3f);
 *bhb_state ^= (src & 0xc0) >> 6;
 *bhb_state ^= (src & 0xc00) >> (10 - 2);
 *bhb_state ^= (src & 0xc000) >> (14 - 4);
 *bhb_state ^= (src & 0x30) << (6 - 4);
 *bhb_state ^= (src & 0x300) << (8 - 8);
 *bhb_state ^= (src & 0x3000) >> (12 - 10);
 *bhb_state ^= (src & 0x30000) >> (16 - 12);
 *bhb_state ^= (src & 0xc0000) >> (18 - 14);
}
f:id:msyksphinz:20180105235801p:plain

分岐予測器の内部をリバースエンジニアリングする

Googleのチームでは以下のようなテストを行っている。 2つのプログラムを、1つの物理コア(ただし2つのプロセス:論理コア)で実行する。

ここで、ASLRというのはアドレスをランダム化する機構で、これを使ってしまうと2つのプログラムで使用するPCアドレスがずれてしまうためこの機能を無効化している。

ここで再現したいのは、2つのプログラムで分岐予測テーブルが共有されてしまいことにより他のプロセスの情報が見えてしまうことである。

そのために、関数ポインタのコールを行いテスト変数へのアクセスを実行する。これによりテスト変数はキャッシュに格納される。 その後その値をCLFLUSH(これはx86のキャッシュラインのフラッシュ命令である)を使ってフラッシュしてしまう。 次に、「現在の分岐予測器の状態」を作り出すために、必ず成立する分岐命令をN回実行する(ここで「必ず成立する」というのは、上述したとおりBHBは成立した分岐しか記録しないためだ)。

そしてそれぞれインスタンス1とインスタンス2が値をテストしているときに、再びテスト値をキャッシュに読み出す。このとき、インスタンス1とインスタンス2が同じ分岐ヒストリのパタンを使えば、インスタンス2も分岐予測のレイテンシを埋めるために投機的にテスト値を自分のレジスタに持ってくるだろう。

その後インスタンス1とインスタンス2でテスト値を取得したところ、インスタンス2はインスタンス1の値を見ることが出来たというわけか。

ここでNの数を増やしていくことを考える。上述したようにBHBはプログラムのソースアドレスとターゲットアドレスの情報をXORで記録しているはずだ。 N=25とすると、この間違いは発生しなかった。つまり、N=25までは分岐予測器は2つのインスタンスの違いが識別できている。 ところが、N=26とすると途端にこの現象が発生し始めた。 従って、Haswellの場合はこの少なくとも26個までの分岐履歴を保存しているということになる。

バリアント3: Rogue data cache load

バリアント3の解説について指摘があり、少なくとも過去の解説について重大な誤りがありました。申し訳ありません。文献をよく読み直し修正しましたが、この解説も疑問が残り誤っている可能性があります。鵜呑みにしないようよろしくお願いします。

こちらも投機的実行を使ったもので、ユーザモードのプログラムが、カーネルモードの領域を参照するプログラムの投機実行を行った途中結果までを利用してデータを読み取るという巧妙なものになっている。

まずは以下の解説を読むべし。

投機的実行のハードウェア構造

こちらは原文から参照させてもらっている、アウトオブオーダプロセッサの構成だ。

これを見ると、パイプラインを流れていく命令は、リオーダバッファを通過した後に命令の種類ごとに異なるユニットに発行されることが分かる。 ポートは0から8まで用意されており、整数命令はポート0,1、ロードストアは2,3といった具合だ。

そして重要な点は、違うポートに発行された命令は、プログラムの順番とは独立に実行が進んでいき、ポーとさえ違っていれば、レイテンシの短い命令はレイテンシの長い命令を追い越すことができる。 これが非常に重要な役割を持つ。

もう一つの特徴は、ある命令で例外が発生したとしても、実際に例外が発生するのは命令が実行ユニットを通過し、命令がリタイアするときにのみ例外が発生するということだ。

例えば極端な例を挙げてみる。

load  dst1, mem[A]      // dst2 <- mem[A] のメモリロード
add.f dst2, dst2, 10.0  // dst2 <- dst2 + 10.0 の浮動小数点演算

ここで、2番目のadd.fで浮動小数点例外が発生したものとしよう。 ところがレイテンシ的にloadのほうが時間がかかり、add.fの方が先に命令の実行が終了し、例外を検出できたものとする。

しかし1番目のloadの完了を待たずに、add.fの例外に飛んでしまうと、プログラムの意味的におかしなことになってしまう。 ソフトウェア的にみると、loadが完了していないのに勝手にadd.fの例外が発生したとして誤動作としてとらえられてしまい、これを防ぐために、必ず例外はリオーダバッファによって命令が完了するときに実行される。

リオーダバッファが命令を完了させるときは、必ず命令はプログラムの順番通りに戻っているため、add.fの例外発生(つまりadd.fが完了しリタイアする)ときは、それよりも前に発行されたloadも必ず終了しており、プログラム的に意味を損なわない、という訳だ。

f:id:msyksphinz:20180106190624p:plain

さて、以上の前提に基づいて、最初の原文に戻って問題を解析してみる。

アウトオブオーダによってカーネルモード命令を結果をうまく使いまわす仕組み

まず、以下のプログラムを考えてみる。

mov rax,[somekernelmodeaddress]

これをユーザモードで実行した場合、余裕で例外が発生する。ダメに決まってる!

しかし、例外が発生するのは、「リオーダバッファに入って命令が完了するとき」であるということを思い出してほしい。 つまり、実際にカーネルモードにアクセスを行い、データをリオーダバッファ中、もしくはキャッシュに持ってきている可能性がある。 これを原文中では、「マイクロアーキテクチャの状態を変更している可能性」としている。

次のプログラムだ。

mov rax, [Somekerneladdress]
mov rbx, [someusermodeaddress]

上記のアウトオブオーダ実行の図を見ると、ロードストアの命令ユニットは2つあるようだ。 しかも上記の2命令には依存関係がないので、この2つは同時に実行することができる。 そして1番目の命令は例外を発生しているのだが、2番目の命令はすでにロードを行っているか、少なくともキャッシュに[someusermodeaddress]のデータをロードしているかもしれない。 これは例外が発生した後に、当該キャッシュをアクセスしてみると確認することができる。

次のプログラムだ。これは上記と違って依存関係を持っている。

mov rax, [somekerneladdress]
and rax, 1
mov rbx,[rax+Someusermodeaddress]

ここで、2番目と3番目の命令が同時に発行されているものとする。

重要なのは2番目のmovの実行結果は、raxつまりsomekerneladdressの値に依存しているということだ。 つまり、アウトオブオーダで2番目のmovの途中結果がキャッシュに保存されていると、その情報を頼りにsomekerneladdressの値を特定することが可能になる!

ここで原文の著者が随分と苦労しているのが、じゃあ1番目の命令が例外を発生させる前に、どうにかして2番目と3番目の命令を実行させなければならない。

これを行うために、mov命令で使用するLoad/Storeとは別のユニットを使って実行するand命令を挿入してある。 Load/Storeユニットを使う命令とは別の命令挿入することで、CPUはこれらの命令を投機的に実行することができるようになる。 (筆者の解釈: ここの説明は正直よく分からない。別のユニットを使っても、投機的な実行を確認することにはならないのでは?)

正しく理解できているか微妙だが、おそらくこういうことだ。

最初のmov命令がカーネル領域のデータをraxにロードするが、実際にはこの命令は例外を発生させる。 この例外が発生する前に、投機的実行によりand命令と次のmov命令を実行することができれば、その痕跡をキャッシュに残すことができるだろう、という考え方だろう。

f:id:msyksphinz:20180106190644p:plain

ただし、この考え方も合っているかは疑問が残る。 そもそも、最初のmovがリタイアするまでに十分な時間が確保したい場合、最初のmovの前にさらに時間がかかる処理を挿入すれば、リタイアまでの時間を大幅に稼ぐことができるのではないか? その間に2番目と3番目の命令を投機実行させることで、ユーザモードのデータ領域をL1に十分な余裕をもって残すことができそうなのだが...

// この部分に非常にレイテンシの長い命令を挿入する。
mov rax, [somekerneladdress]       // ↑の命令の影響でこの命令はなかなか例外を出すことができない
and rax, 1                         // その間に、この命令と
mov rbx,[rax+Someusermodeaddress]  //           この命令がkerneladdressのデータに基づいてユーザ領域のデータを取り出す。

まあ、分からん。

マイクロアーキテクチャから見たこれらの脆弱性の修正方法

また、Intelの公式声明でもこれらの解決法(Mitigation:緩和法?)について言及されている。

Bound check Bypass の解決方法

基本的にはソフトウェアによる解決法が望まれている様子。 実際にアクセスを行ってはいけないシーケンスについては、FENSE命令を使って明示的にメモリアクセスの同期を行い、ハードウェアプリフェッチを防ぐという方式。

Branch Target Injection の解決方法

こちらはあまりパッとしないのだが、プロセッサとシステムソフトウェアの間に新しいインタフェースを仕込むという風になっている。 マイクロコードによるアップデートとしては、

  • Indirect Branch Restricted Speculation (IBRS): 間接分岐の投機実行を制限する。
  • Single Thread Indirect Branch Predictors(STIBP): 間接分岐の投機的移行は、1つのスレッドのみが実行できるように制約する。
  • Indirect Branch Predictor Barrier(IBPB): 前のプログラムの挙動が、間接分岐の分岐予測に影響しないようにする。

Rogue Data Cache Load の解決方法

これはユーザモードとスーパバイザモードのページ構造を分け、分離することで解決できるとしている。

まあどっちにしても、ソフトウェアによる修正が必要ということだな。

Computer Architecture 6th Editionの7章"Domain-Specific Architecture" を読む (7.6章 Intel Crest, 学習のためのデータセンタアクセラレータ)

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

7.6章は DSAの一つの例としてIntel Lake Crestを取り上げている。こちらはかなり情報が限られている。ってか2017年中にリリースって言ってるのに2018年になってしまいましたね。

目次

これは著者が読んだ内容をまとめているだけなので、誤訳、理解不足により誤っている可能性があります!鵜呑みにしないようにお願いします。


7.6 Intel Crest, 学習のためのデータセンタアクセラレータ

7.3章の最初の引用にあるように、IntelはDNNのためのDSAを製造することをプレスリリースした。 最初の例は、私たちがが本書を執筆している最中にアナウンスされたCrestである。 まだ情報が少ないながら、私たちがこのプロジェクトについて言及しようと思ったのは、Intelというマイクロプロセッサの伝統的な供給メーカがDSAとタッグを組むという重要なステップに踏み出したからである。

CrestはDNNの学習フェーズをターゲットとしている。 IntelのCEOは、3年で機械学習の学習フェーズの速度を100倍にすることが目標であるといった。 図7.6によると、DNNの学習には1か月程度必要である。 このDNNの学習時間を、CEOが言及した通り、1/100であるたった8時間に短縮するということ自体には需要がある。 間違いなく、次の3年でより複雑になり、学習にはより多くの時間が必要となるだろう。 したがって、学習時間を100倍高速化するということについて、過度の危険性はない。

Crestの命令は32×32の行列のブロックを操作する。 Crestは「flex point」と呼ばれる数値形式を用い、これは固定小数点をスケーリングしたものである: 16bitデータを持つ32×32の行列は命令セットの一部から供給される5ビットの指数部を共有する。

図7.28はLake Crestチップのブロックダイアグラムを示している。 これらの行列を計算するために、図7.28に示すようにCrestは12個のプロセッシングクラスタを用意している。 各クラスタには大容量のSRAM、代数用のプロセッシングユニット、オンチップ・オフチップ用ルーティング用の少量の論理が搭載されている。 4つの8GBのHBM2 DRAMモジュールが搭載されており、1TB/sのメモリバンド幅を供給しており、これによりCrestチップは魅力的なRooflineモデルを提供している。 Lake Crestチップは高いバンド幅のインターコネクトをサポートしており、プロセッシングクラスタ内のコアの計算や、共有メモリを介在しないコア間の通信もサポートしている。 Lake Crestの目標はGPUと比較して学習速度を10倍高速化することである。

図7.28には、12個のチップ間リンク(Inter Chip Link:ICL)と、2個のチップ間コントローラ(Inter Chip Controller)を搭載しており、Crestは他のCrestチップと強調して動作することができる。 これは48個のFPGAが専用ネットワークを通じて強調動作するMicrosoftのCatapultと考え方が似ている。 学習速度の100倍の高速化には、いくつかのCrestチップによる強調動作が必要とされる。

図7.28 Intel Lake Crestsプロセッサのブロックダイアグラム。Intelの資料より抜粋。CrestはTSMC28 nmプロセスの古レチクルで実装され、ダイサイズは600から700m2になる予定。このチップは2017年に供給される予定である。IntelはKnights Crestと呼ばれる、Xeon x86コアとCrestアクセラレータのハイブリッドチップも設計している。

Computer Architecture 6th Editionの7章"Domain-Specific Architecture" を読む (7.5章 Microsoft Catapult, フレキシブルなデータセンタアクセラレータ)

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

7.3章はがっつりディープニューラルネットワークの内容だ。今回はMicrosoft Catapult, フレキシブルなデータセンタアクセラレータ。

目次

これは著者が読んだ内容をまとめているだけなので、誤訳、理解不足により誤っている可能性があります!鵜呑みにしないようにお願いします。


7.5 Microsoft Catapult, フレキシブルなデータセンタアクセラレータ

GoogleがカスタムASICをデータセンタにデプロイすることを考えているまさにその時、Microsoftは彼らのためのアクセラレータについて考えていた。 Microsoftの視点は、以下のガイドラインに沿った解決策を考えることであった。

  • マシンの短期間での再デプロイを可能にするためにサーバのホモジニアス性を保持する必要があり、より複雑なマシンメンテナンスとスケジューリングが発生する必要を避ける必要がある。そのことがDSAにとって少し奇妙なことであっても、この方針を維持する必要があった。
  • すべてのアプリケーションを複数のアプリケーションに焼きこまずに単一のアクセラレータを使用するよりも、多くのリソースが必要なアプリケーションにとってスケーリングができる必要があった。
  • 電力性能が必要だった。
  • ある一か所で問題が発生しても、ディペンダビリティの問題が発生しないようにする必要があった。
  • 既存のサーバに対して、スペース的な問題と電力的な問題がうまくフィットする必要があった。
  • データセンタのネットワーク性能と信頼性を低下させない必要があった。
  • アクセラレータはサーバのコストパフォーマンスを向上させる必要があった。

最初のループは、ASICをデプロイするとサーバ上で動作するいくつかのアプリケーションにのみ限定される。これはGoogleが選択したケースである。

MicrosoftはCatapultというプロジェクトをスタートさせ、PCIeバスを搭載したFPGAボードをデータセンタサーバに設置した。 これらのボードは複数のFPGAが動作するのに必要なネットワーク能力を持っていた。 FPGAのフレキシビリティを使用して複数のアプリケーションを異なるサーバ上で使用し、同じサーバ上でリプログラミングして異なるアプリケーションプログラムを高速化させる、という計画である。 このアクセラレータによる恩恵を増大させた。 FPGAのもう一つの利点はASICよりもNREが低いことであり、投資の恩恵を増大させることができる。 私たちはCatapultによる2つのジェネレータについて評価を行い、WSCの必お由奈性能をどのようにして満たすのかについて議論を行った。

FPGAの一つの面白い特徴として、各アプリケーション~あるいはアプリケーションの各フェーズですら~一つのDSAとして考えることができるということである。 したがって本節では、1つのハードウェアプラットフォーム上で多くの優れたアーキテクチャの例について見ていくことができる。

Catapultの実装とアーキテクチャ

図7.19はMicrosoftが彼らのサーバに適合するように設計したPCIeボードである。 電力のことを考えて25Wで設計してある。 この制約により、最初のCatapultの実装ではFPGAはAlteraのStratix V D5 FPGAに限定された。 このボードは32MBのフラッシュメモリを装備しており、2バンクのDDR3-1600 DRAMを持ち8GBの容量を持っていた。 FPGAは3926個の16bit ALUを持っており、5MBのオンチップメモリを持っていた。またDDR3 DRAMとの接続バンド幅は11GB/sであった。

f:id:msyksphinz:20180103210136p:plain

図7.19 Catapultのボード設計 (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/Catapult_ISCA_2014.pdf より抜粋)

データセンタのラックの半分である48個のサーバにCatapultのボードが実装された。 Catapultは、複数のFPGAアプリケーションに対してデータセンタのネットワークに影響を与えないというガイドラインに従っている。 独立した低レイテンシの20Gbit/sのネットワークによって48個のFPGAを接続した。 ネットワークのトポロジは6×8のトーラスネットワークであった。

一か所の故障により全体が影響を与えないというガイドラインに従うため、このネットワークは1つのFPGAが故障しても再構成できるようになっている。 ボードは、FPGAより外部のすべてのメモリに対してSECDED保護がかけられており、非常に大きなデータセンタに対してもデプロイが可能になっている。

プログラマビリティを確保するためにFPGAはチップ上のメモリを利用しているため、プロセスの進化に伴う放射線の影響により、ASICに比べてSingle-event upsets(SEUs)に対して脆弱である。 Catapultで使用しているボードのAltera FPGAは、FPGA内部にSEUを検出して訂正するメカニズムを実装しており、FPGAのコンフィグレーション状態が切り替わるときにSEUにより問題が発生する可能性を削減している。

独立したネットワークを追加することにより、データセンタネットワークと比較して、通信性能が変動する可能性を防いでいる。 ネットワークは予期せずそのレイテンシが増加することがある。これは特にエンドユーザが使用するアプリケーションにとって有害なものとなる。 したがって分離されたネットワークによりCPUからアクセラレータに、簡単にタスクをオフロードできるようになっている。 このFPGAネットワークは、エラー率がデータセンタのプロトコルよりも低く、トポロジがうまく定義されているため、データセンタのプロトコルよりもより簡単なもので動作するようになっている。

FPGAを再コンフィグレーションする場合には弾力性について考慮する必要があり、隣接するノードが故障やクラッシュを起こしてもホストサーバや隣接するノードが巻き込まれないようにする必要がある。 Microsoftは高レベルなプロトコルを開発し、複数のFPGAが再構成する場合でも安全性を保証している。

Catapultのソフトウェア

CatapultとTPUの最も大きな違いがあるとすれば、プロ蔵身をVerilogもしくはVHDLで記述するというところである。 Catapultの著者が書いているように(Putnam et al., 2016):

ゆくゆくは、データセンタにFPGAを幅広く適用するための最も大きな障害はプログラマビリティになるだろう。FPGAの開発は、幅広いレジスタトランスファレベルのハンドコーディングや、マニュアルチューニングが必要である。

Catapult FPGAプログラマビリティの問題を削減するために、図7.20に示すようにレジスタトランスファレベル(Register Transfer Level:RTL)のコードを「シェル(shell)」と「ロール(role)」に分割した。

シェルのコードは、組み込みCPUで動作するライブラリのようなものである。 シェルには、同じFPGAボード上で、データの整列、CPUとFPGAの通信、FPGAFPGAの通信、データの移動、再コンフィグレーション、モニタリング、などのアプリケーションを通して再利用することのできるRTLコードが含まれている。 シェルのRTLコードはAlteraのFPGA上で23%を占めている。 ロールのコードはアプリケーションの論理で、Catapultのプログラマは残りの77%のFPGAのリソースを使用して記述する。 シェルは標準APIや、アプリケーションの標準的な動作のような役割を持っている。

f:id:msyksphinz:20180103210151p:plain

図7.20 Catapultのコンポーネントである、シェルとロールによりRTLコードが分割される(https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/Catapult_ISCA_2014.pdf より抜粋)

Catapult上でのCNN

MicrosoftはCatapult向けにコンフィギャラブルなCNNアクセラレータを開発した。 コンフィグレーションのパラメータにはニューラルネットワークのレイヤと、それらのレイヤの次元、そして計算精度なども含まれている。 図7.2はCNNアクセラレータのブロックダイアグラムである。 カギとなる特徴は、

  • ランタイムに構成を変更することができるデザインである。FPGAのツールを利用して再コンパイルする必要はない。
  • メモリアクセスを最小化するために、CNNデータ構造を効率的にバッファしている。
  • Processing Element(PE)の2次元アレイを、数千のユニットまでスケーリングすることができる。

f:id:msyksphinz:20180103210207p:plain

図7.21 Catapult向けのCNNアクセラレータ (https://www.microsoft.com/en-us/research/wp-content/uploads/2014/06/HC27.25.432-Catapult_HOTCHIPS2015_Chung_DRAFT_V8.pdf より抜粋)

画像はDRAMに転送され、FPGA中の複数バンクのバッファに入力される。 入力値は複数のPEに転送され、特徴マップを出力するためにステンシルが計算される。 図7.21左上のコントローラにより各PEのデータフローを制御する。 最終結果はCNNの次のレイヤで再利用するために、入力バッファに再挿入される。

TPUの様に、PEはシストリックアレイの形式で設計されている。 図7.22はPEのデザインの詳細である。

f:id:msyksphinz:20180103210222p:plain

図7.22 Catapult向けCNNアクセラレータのProcessing Element(PE)のデザイン (https://www.microsoft.com/en-us/research/wp-content/uploads/2014/06/HC27.25.432-Catapult_HOTCHIPS2015_Chung_DRAFT_V8.pdf より抜粋)

Catapultによる検索の高速化

Catapultによる投資の効果を、評価するための主要なアプリケーションは、Microsoft検索エンジンであるBingの中心となるアプリケーションである「ランキング」と呼ばれる処理である。 ランキングは、検索からその結果をランク付けする機能である。 その結果はドキュメントのスコアでありウェブページ上のドキュメントの位置づけであり、この情報がユーザに提示される。 アルゴリズムは3つのステージを踏む。

  1. 特徴抽出: ドキュメント中から、サーチクエリという情報に基づいて何千という興味深い特徴を抽出する。例えば、クエリのフレーズがドキュメント中に何度登場したかなどの情報である。
  2. 自由形式表現 : 1.の情報に基づいて、何千もの特徴の組み合わせを計算する。
  3. 機械学習スコアリング : 機械学習アルゴリズムを利用して、1.2.のステージの情報を評価しドキュメントの浮動小数点のスコアを計算する。このスコアがホストのサーチソフトウェアに返される。

ランキングのCatapult実装では、Bingのソフトウェアと同一の結果が得られた。それどころか、既存のソフトウェアのバグまで再現した!

前述したガイドラインの1つの恩恵を得るために、ランキングの関数は単一のFPGAにフィットする必要はない。 ランキングのステージは、以下のようにして8つのFPGAに分割された。

  • 1つのFPGAを用いて特徴抽出を実装する。
  • 2つのFPGAを用いて自由形式表現を実装する。
  • 1つのFPGAを使って圧縮ステージを実装し、スコアエンジンの効率を向上させる。
  • 3つのFPGAを使って、機械学習によるスコアリングを行う。

残りの1つのFPGAは、故障時に対応するための予備である。 1つのアプリケーションに対して複数のFPGAを使用しても、専用のFPGAネットワークを構築しているためにうまく動作させることができた。

図7.23は特徴抽出のステージの構成を示している。 43個の特徴抽出のためのステートマシンを実装しており、ドキュメントとクエリのペアに対して並列に4500個の特徴を抽出している。

f:id:msyksphinz:20180103210240p:plain

図7.23 特徴抽出ステージのFPGA実装のアーキテクチャ

次に、自由形式表現のステージである。 ゲートやステートマシンを実装するのではなく、Microsoftは60コアのプロセッサを実装し、マルチスレッドによる長いレイテンシを隠ぺいした。 GPUとは異なり、MicrosoftのプロセッサはSIMD実行は必要なかった。 このプロセッサはレイテンシが重要となるターゲットに対して以下の3つの特徴を持っていた。

  1. 書くコアは4つの同時スレッデングを持っており、1つのスレッドがレイテンシが長い処理によりストールしても他のスレッドが動作するようになっていた。すべての機能ユニットがパイプライン化され、新しい処理を毎サイクル実行することができた。
  2. スレッドはプライオリティエンコーダにより性的に優先度がつけられていた。最もレイテンシ長い表現は、すべてのコアにおいてスレッドのスロット0を使用する。次に遅い表現はすべてのコアにおいてスレッド1を使用した。
  3. 自由形式表現を使用するために、表現データが多すぎて同時に一つのFPGAにフィットしない場合は2つのFPGAに分割することができた。

FPGAにおける再プログラマブル可能なシステムの1つの負荷は、あまり動作周波数を上げることができないということである。 機械学習スコアリングでは、2つの形式の並列性をし応して、この問題を解決しようとしている。 1つはアプリケーションの並列性を利用して、マシンの得られるパイプラインを使って処理をパイプライン化している。 ランキングでは、ステージ当たり8usが限界であった。 2番目の並列性は、殆ど見ることのないMultiple Instruction Streams, Single Data Steram(MISD)並列性である。 これは、非常に多くの独立した命令ストリームを動作させ、1つのドキュメントを処理するというものであった。

図7.24はCatapultのランキング関数の性能を示している。 7.9節でみるように、エンドユーザ向けのアプリケーションでは厳しいレスポンスタイムが要求される; 締め切り時間を過ぎると、いくらスループットの高いシステムでも出目なのである。 x軸はレスポンス時間の限界地であり、1.0以上となってはならない。 最大レイテンシで言うと、CatapultはホストのIntelサーバに対して1.95倍高速であった。

f:id:msyksphinz:20180103210254p:plain

図7.24 レイテンシ境界におけるCatapultで実装したランキング関数の性能

SSDとメモリを購入

人権を購入した。人権はとても費用が掛かる。 これで我が家のメインメモリは32GBになり、ハードディスクからSSDデビューだ! (プライベートのSSDデビューは初めて)

f:id:msyksphinz:20180103211046p:plain

とりあえず、これまでのHDDは何だったのか。ベンチマークを取得してみると爆速になっている。これはすごい。

f:id:msyksphinz:20180103214631p:plain

Computer Architecture 6th Editionの7章"Domain-Specific Architecture" を読む (7.4章 Google's Tensor Processing Unit)

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

7.3章はがっつりディープニューラルネットワークの内容だ。今回は多層パーセプトロン、畳み込みニューラルネットワーク再帰ニューラルネットワーク

目次

これは著者が読んだ内容をまとめているだけなので、誤訳、理解不足により誤っている可能性があります!鵜呑みにしないようにお願いします。 長々と書いたけれども、Tensor Processing Unitの論文よりも詳細なことは書いていない。そりゃそうか。


GoogleTensor Processing Unit, データセンタの推論アクセラレータ

Tensor Processing Unit(TPU)はGoogleの最初のWSC向けDSAのASICである。 個のチップのターゲット領域はDNNの推論フェーズであり、またDNN向けに設計されたTensorFlowフレームワークを使ってプログラミングを行うことが出来る。 TPUの第1弾は2015年にGoogleのデータセンタにデプロイされた。

TPUは65,536(256×256)個の8-bit 行列積ユニットALUを備え、ソフトウェア管理のオンチップメモリが搭載されている。 TPUはシングルスレッドで、決定的な実行モデルは、99パーセンタイルのレスポンスタイムが必要とされる典型的なDNNの推論アプリケーションにうまく適合している。

TPUの由来

2006年に、GoogleのエンジニアはデータセンタにおけるGPUFPGA、カスタムASICのデプロイについて議論を行った。 彼らは、特殊なハードウェアを必要とするアプリケーションで、大容量データセンタの過剰な計算能力を使っても仮想的に実行することが出来るものは少なく、これらを自由に改善することは難しいとの結論に達した。 2013年にはこの議論の結論は変わり、ユーザが1日に3分ほどDNNの音声検索を使用するならば、その計算能力を間に合わせるためにはGoogleのデータセンタを倍増しなければならないという結論に達した。 このデータセンタの増強は伝統的なCPUを使って達成するには非常にコストのかかるものであった。 Googleは推論処理を実行するためのカスタムASICチップを開発するためのプロジェクトを急ピッチに立ち上げた(と、トレーニングに必要なGPUの在庫を購入した)。 目標はGPUの10倍以上のコスタ性能を達成することであった。 この目標を元に、TPUは設計、検証、組み立て、デプロイがたった15ヶ月の間に行われた(Steinberg, 2015)。

TPUのアーキテクチャ

デプロイが遅延することを避けるために、TPUはPCIe I/Oバスに接続されるコプロセッサとして設計され、既存のサーバに接続されるように設計された。 さらに、シンプルなハードウェア設計とデバッグ機能をもっており、ホストサーバがPCIeバスを通じてTPUに指令を転送する。 これはTPU自身が命令をフェッチする機構を取っているわけではない。 したがって、命令をメモリから自分でフェッチするGPUとは異なり、TPUはFPU(浮動小数点ユニット: Floating Point Unit)コプロセッサのような考え方を元に設計されている。

図7.12はTPUのブロックダイアグラムを示している。 ホストのCPUはPCIeバスを通じてTPUの命令バッファに命令を転送している。 内部ブロックは256バイト(2048ビット)幅で接続されている。 右上ブロックから始まって、「行列積ユニット(Matrix Multiply Unit)」がTPUの心臓部である。 行列積ユニットは256×256個の符号あり・無しの8-bit整数積和演算ALUが内蔵されている。 32-bit幅の、4MBのアキュムレータによって、16ビットの結果が格納される。 8bitの重みと16bitの値を使って、ビット幅を混在させた場合は、行列積ユニットは半分の速度で実行する。 また、両方とも16bitの値を使った場合は行列積ユニットは4分の1の速度で計算を実行する。 1クロック当たりに256個の値を読み書きし、行列積と畳み込みのどちらかを計算することが出来る。 「活性化(Activation)」ユニットを使って、非線形関数の計算が行われる。

図7.12 TPUのブロックダイアグラム (https://cloud.google.com/blog/big-data/2017/05/an-in-depth-look-at-googles-first-tensor-processing-unit-tpu より抜粋)

行列ユニットの重みデータは、オンチップメモリの「重みFIFO(Weight FIFO)」を通じて格納される。 この値は重みメモリ(Weight Memory)と呼ばれるオフチップの8GBのDRAMから読み込まれる(推論用で、重みは読み込み専用、8GBはは多くのアクティブモデルをサポートしている)。 中間結果は24MBのオンチップの「ユニファイドバッファ(Unified Buffer)」に格納され、行列積ユニットの入力値として使用される。 プログラマブルDMAコントローラはデータをCPUホストメモリとユニファイドバッファの間を転送する役割を持っている。

TPUの命令セットアーキテクチャ

TPUの命令は比較的低速なPCIeバスを通じて転送されるため、TPU命令は伝統的なCISC命令形式であり、リピートフィールドを持っている。 TPUはプログラムカウンタを持っておらず、分岐命令も持っていない; 命令はホストCPUから転送され、これらのCISC命令の命令辺りに必要なクロックサイクル数(CPI)は典型的に10~20サイクルである。 命令種類は1ダース程度であるが、5つのカギとなる命令がある。

  1. Read_Host_Memory 命令はCPUのホストメモリからユニファイドバッファにデータを転送する。
  2. Read_Weights 命令は重みメモリから重みデータを重みFIFOに転送し、行列ユニットの入力値として使えるようにする。
  3. MatrixMultiply/Convolve命令は行列積ユニットを実行し、ユニファイドバッファのデータを使用して行列積、ベクトル行列積、要素毎の行列積、要素毎のベクトル積、もしくはの畳み込み演算を実行し、結果をアキュムレータに格納する。行列の演算は可変サイズを取ることが出来、B*256の入力と、256×256の行列積を実行し、B*256個の結果を出力する。これにはBサイクル必要である。例えば、入力が256要素の4ベクタであるならば、Bは4であり、計算の完了までに4サイクルが必要である。
  4. Activate命令は人工ニューロンのための非線形関数を実行し、ReLU、シグモイド、tanhなどを実行することが出来る。このユニットの入力はアキュムレータから提供され、計算結果はユニファイドバッファに格納される。
  5. Write_Host_Memory命令はデータをユニファイドバッファからCPUのホストメモリに書き込む。

TPUのマイクロアーキテクチャ

TPUのマイクロアーキテクチャの哲学は、なるべく行列積ユニットを動作させ続けるということである。 他の命令の実行を、行列積の実行であるMatrixMultiply命令とオーバラップさせて隠すという考え方である。 したがって、実行命令以外の、4つの一般的なカテゴリの命令は個別の命令ハードウェアを持っている(ホストメモリとの読み書きは、同一のユニットを使って実行される)。 命令並列性を向上させるためには、Read_Weights命令はDecoupledアクセス/実行方式(Smith, 1982b)に則って設計されている。 これは計算を完了するのは、アドレスを転送した後であるが、計算完了前に重み情報は重みメモリからフェッチされるという方式である。 行列ユニットはNot-Ready信号をユニファイドバッファからもらっており、重みFIFOは行列ユニットにストール信号を転送し、重みデータの到着を待たせることが出来る。

ここでTPUの命令は複数クロックサイクルで実行され、伝統的なRISCパイプラインのように1サイクルで1ステージを通過していくわけではないということに注意である。

大きなSRAMから読み書きを行うことは、演算よりもコストが高いため、行列積ユニットはシストリック実行方式を取っており、ユニファイドバッファからの読み書きの回数を削減している(Kung and Leiserson, 1980; Remacher et al., 1991; Ovtcharov et al., 2015b)。 「シストリックアレイ(Systoric Array)」は2次元状に演算器を並べており、各演算器は独立して計算を実行し、関数の部分計算結果を次の演算ユニットに転送する。 データは異なる方向からセルに対して一定の間隔で転送で転送される。 アレイ内のデータフローはウェーブフロントのように転送されるため、人間の血管構造に似ており、この構造がシストリックと呼ばれる由来になっている。

図7.13はシストリックアレイが動作する様子を示している。 下側の6つの丸が積和演算ユニットであり、重みw_iで初期化されている。 ステージングされたデータx_iが、このアレイの上側から転送されてきている。 この図では10ステップ毎のデータ転送の様子を示している。 シストリックアレイは入力値を下側に転送し、積と和を右側に転送している。 シストリックアレイは入力データはメモリからのみ読み込まれ、出力データは1度だけメモリに書き込まれることに注意である。

TPU内では、シストリックアレイはローテートされる。 図7.14では、重みデータは上部からロードされ、入力データは左側から転送されアレイ中を通過する。 256要素の積和演算器は行列中を通過し、斜め方向にウェーブフロントとして通過する。 重みデータはあらかじめロードされ、ウェーブ中でデータブロックの最初のデータとして進んでいく。 制御情報とデータも一緒に転送され、256個のアキュムレータのメモリのデータをアップデートしてく。 正確性という面からはソフトウェアは行列ユニットのシストリックの構成については意識しないが、ユニットのレイテンシについて考慮する必要がある。

f:id:msyksphinz:20180102134155p:plain
図7.13 シストリックアレイの動作
図7.14 行列積ユニットのシストリックデータフロー (https://cloud.google.com/blog/big-data/2017/05/an-in-depth-look-at-googles-first-tensor-processing-unit-tpu より抜粋)

TPUの実装

TPUチップは28-nmプロセスを使って製造されている。 動作周波数は700MHzである。 図7.15はTPUのフロアプランを示している。 ダイサイズは公表されていないが、Intel Haswellサーバマイクロプロセッサの662mm2の半分以下の大きさである。

図7.15 TPUダイのフロアプラン (https://cloud.google.com/blog/big-data/2017/05/an-in-depth-look-at-googles-first-tensor-processing-unit-tpu より抜粋)

24MBのユニファイドバッファが1/3を占めており、行列乗算ユニットが1/4、データパスが台の2/3を占めている。 24MBの大きさは行列ユニットの大きさと適合するようにできており、コンパイラを単純化することで開発期間を単純化している。 制御ユニットは全体の2%である。 図7.16はTPUのプリント基板であり、既存のSATAディスクスロットに挿入して使用する。

図7.16 TPUのプリント基板 (http://hexus.net/tech/news/industry/104299-google-benchmarks-tensor-processing-unit-tpu-chips/ より抜粋)

TPUのソフトウェア

TPUのソフトウェアスタックはCPUでの開発やGPUでの開発と互換性があり、アプリケーションを短期間で移植することが出来る。 典型的に、アプリケーションをTPU上で実行するときはTensorFlowとそのコンパイルされたAPIを使ってGPUもしくはTPU上で実行する(Larabel, 2016)。 図7.17はTesorFlowを使ってMLPを実行するコードである。

GPUのように、TPUスタックはユーザスペースドライバとカーネルドライバに分かれている。 カーネルドライバは軽量で、メモリ管理と割り込みを管理するだけである。 これは長期間において安定するように設計されている。 ユーザスペースドライバは頻繁に変更される。 ユーザスペースドライバはTPU実行のセットアップと制御を担当し、TPUの形に合うようにデータを変換し、APIコールをTPUの命令に変換してアプリケーションバイナリに変更する。 ユーザスペースドライバは、コードが評価されると、まずモデルをコンパイルし、プログラムイメージをキャッシュして重みイメージをTPUの重みメモリに書き込む; これにより2番目以降の評価ではフルスピードで動作することが出来る。 TPUは入力から出力までほとんどのモデルを完全に実行することができ、TPUの実行時間とI/O時間の比率を最大化する。 計算はしばしば一度に1レイヤで終了し、クリティカルパスではない処理によって行列演算の処理をオーバラップしてレイテンシを隠蔽する。

TPUの向上

TPUアーキテクトはTPUをより向上させるために多くのマイクロアーキテクチャを検討した。

FPUと同様にTPUのコプロセッサは比較的簡単なマイクロアーキテクチャである。したがってTPUアーキテクトは性能モデルを作成し、メモリのバンド幅、行列ユニットのサイズ、クロックレートとアキュムレータの数を利用して性能を見積もった。 TPUハードウェアカウンタを使った測定では、作成したモデルとハードウェアとは約8%の誤差が存在した。

図7.18は、これらのパラメータによりTPUの性能にどの程度影響があるかを0.25倍から4倍の間で比較したものである(7.9章のベンチマークを使用した)。 クロックレートを向上させたもの(図.18のClock)に加えて、図7.18ではクロックレートを向上させたものとアキュムレータの数を増やしたものを追加しており、したがってコンパイラは実行中のメモリ参照を増やすことが出来る。 同様に、図7.18はアキュムレータの数が2乗に増加した場合に行列ユニットを拡張した場合の性能向上を示している。 一方で"matrix"は行列ユニットを向上させただけである。

まず、メモリバンド幅を向上させた場合(memory)は最も大きなインパクトがあった: メモリバンド幅を4倍にすると、性能は4倍になり、これは重みメモリの待ち時間が削減されたからである。 次に、アキュムレータの数を変更せずにクロックレートのボトルネックはわずかであったであるということである。 3番目に、行列ユニットを256×256から512×512にしても、アキュムレータの数を増やしてもそうでなくても、図7.18の平均的な性能はわずかに低下するだけであった。 この問題は大きなページを扱った場合の内部フラグメンテーションの問題に似ている。 TPUでは2次元のデータしか扱わないためである。

LSTM1において600×600の行列を使った場合は、256×256の行列ユニットでは600×600の行列を全て計算するために9ステップ必要で、合計で18usとなる。 より大きな512×512の行列ユニットを使った場合は4ステップで完了させることが出来るが、各ステップの計算時間が4倍になり、32usの時間がかかる。 TPUのCISC命令は長いため、デコードはDRAMからのロードのオーバヘッドを隠蔽することはできない。

性能モデルから得られる結果を見て、TPUアーキテクトはもしさらに15ヶ月を使って設計した場合の仮説を立てた。 よりアグレッシブな論理合成と、ブロックデザインのクロック周波数を約50%向上することが出来たと考えている。 アーキテクトは、K80で使われているようなGDDR5メモリのインタフェースを設計することで、重みメモリのバンド幅を5倍近く向上させることが出来ると考える。図7.18に示すように、クロックレートを1050MHzにしても、メモリの支援が無ければ性能にほとんど影響を与えない。 もしクロックレートが700MHzのままでも、GDDR5を重みメモリに使用すると、性能は約3.2倍に向上する。 これらを両方実施しても、さらに性能を向上させることはない。

f:id:msyksphinz:20180102134528p:plain

Computer Architecture 6th Editionの7章"Domain-Specific Architecture" を読む (7.3章 多層パーセプトロン、畳み込みニューラルネットワーク、再帰型ニューラルネットワーク)

ヘネパタ第6版こと、"Computer Architecture 6th Edition" では、第7章でドメイン固有アーキテクチャの章が新設された。 これを機会に、しっかり読んでいこう。

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

7.3章はがっつりディープニューラルネットワークの内容だ。今回は多層パーセプトロン、畳み込みニューラルネットワーク再帰ニューラルネットワーク

目次

これは著者が読んだ内容をまとめているだけなので、誤訳、理解不足により誤っている可能性があります!鵜呑みにしないようにお願いします。 2018/01/03 追記。フューチャーマップ(future map)→特徴マップ(feature map)の誤訳でした。訂正します。


多層パーセプトロン

MLPはDNNの原型である。 それぞれ新しいレイヤは非線形関数Fの集合であり、ひとつ前のレイヤの全ての出力と重みを掛け合わせた値 y_n=F(W\times y_{n-1}) で構成されている。 重み付き加算値は、出力値と重みのベクトル-行列積で構成されている(図7.7を参照のこと)。 このようなレイヤは"Fully-Connected"と呼ばれており、これは各出力ニューロンの結果は、前のレイヤの入力ニューロンに依存しているからである。

DNNの形によって、レイヤ当たりのニューロン量、演算量、重みの量は計算することが出来る。 最も簡単なのはMLPで、入力ベクトルと重み行列のベクトル-行列積を実行するだけである。 以下に、推論に必要な重みの数と演算量のパラメータと式を示す(ここでは、積和演算については2演算として計算している)。

  • \text{Dim}[i]: 出力ベクタの次元数。ニューロンの数と同様である。
  • \text{Dim}[i-1]: 入力ベクタの次元数
  • 重みの数:  \text{Dim}[i-1]\times \text{Dim}[i]
  • 演算量:  2\times\text{重みの数}
  • 演算量/重み: 2

最後の項は「演算強度(operational intensity)」と呼ばれ、第4章でルーフラインモデルとして議論したものである。 私たちは、通常、チップに収まらない何百万という重みが存在する可能性があるため、重みあたりの演算量という指標を用いる。 例えば、1ステージ当たりでMLPの次元数は7.9章で \text{Dim}[i-1]=4096, \text{Dim}[i]=2048 であり、したがってニューロンの数は2048個、そして重みの数は8,388,608であり、演算量は16,777,216であり、演算強度は2である。 ルーフラインモデルで述べたように、演算強度が低い場合は、高い演算性能を出すのが難しくなる。

f:id:msyksphinz:20180101175455p:plain
図7.7 MLPは左側の入力レイヤ[i-1]からのデータを受け取り右側のレイヤ[i]に出力する。

ReLUはMLPでは有名な非線形関数である。多くの場合は入力レイヤと出力レイヤの次元数は異なる。このようなレイヤはfully connectedレイヤと呼ばれ、これは出力レイヤは前のレイヤのすべての入力に依存しているからである。これは殆どの値がゼロでも同じことがいえる。ある研究では、前のレイヤの値の44%がゼロであるが、これはReLUにより負の数がすべてゼロにされるからであると推定することが出来る。

畳み込みニューラルネットワーク

CNNはコンピュータビジョンのアプリケーションにおいて広く利用されている。 画像は2次元の構造をしており、隣接するピクセルは関係性を見出しやすい。CNNは前のレイヤからの出力値のうち、空間的に隣接する領域の情報を非線形関数を受け取り、何度も再利用している重みを掛け合わせる。

CNNのアイデアの背景には、各レイヤは画像の抽象レベルに対応していると考えることが出来る。 例えば、最初のレイヤは水平方向と垂直方向のラインを特定するためのレイヤと考えることが出来る。 2番目のレイヤは、コーナーを検出するためにこれらの情報を組み合わせるためのレイヤである。 次のステップでは四角形と丸を識別するためのレイヤである。 次のレイヤは犬の部品、例えば目屋耳などを識別するためのレイヤである。 より高いレイヤでは、犬の種類名の違いなどの特徴を識別するためのレイヤである。

各ニューラルレイヤは2次元の「特徴マップ(feature map)」と呼ばれる、特徴マップの各セルが入力画像の対応する領域化から1つの特徴を識別するための情報を生成する。

図7.8は入力画像から2×2のステンシル計算を行い、最初の特徴マップの要素を生成するための最初のポイントを示している。 「ステンシル計算(stencil computation)」は固定のパタンから、隣接するセルを使って、アレイ中のすべてのエレメントを更新する。 出力された特徴マップの数はあなたが画像から何個の異なる特徴を抽出するかと、ステンシルを抽出するために利用するストライドの量に依存する。

f:id:msyksphinz:20180101181613p:plain
図7.8 CNNの最初のステップの簡単な図。この例では、入力画像の4つのピクセルのすべてのグループは同じ4つの重みと掛け合わされ、出力セルの特徴マップを生成する。この図では入力ピクセルを2ストライドずつグループにしているが、他の可能性もありうる。MLPと比較するためには、2×2の畳み込みを小さなfully connectedな演算として1出力を生成するものと考えることが出来る。図7.9では特徴マップを3次元のベクトルに変換する方法について示している。

通常、画像は単一のものでは無く、フラットな2次元のレイヤであるため、この処理はより複雑なものになる。 典型的には、画像データは赤、青、黄色の3レベルの情報を持っている。 例えば、2×2のステンシルは12個の要素にアクセスすることになる: 2×2の赤ピクセル、2×2の青ピクセル、2×2の緑ピクセルである。 この場合には、2×2のステンシルで3レベルの3つの竜力レベルの画像では、出力特徴マップ当たり12個の重みが必要である。

図7.9は入力と、最初のレイヤから生成された出力特徴マップの任意数について示している(xxx)。 計算は1組の重みを有するすべての入力特徴マップに対する3次元ステンシルであり、1つの出力特徴マップを生成する。

数学が好きな読者のために説明すると、もし入力特徴マップと出力特徴マップが同一で1であり、ストライドが1である場合、2次元CNNの単一レイヤは2次元の離散した畳み込みである。

図7.9に見るように、CNNはMLPよりも複雑である。 重みと演算量についてパラメータと等式を示す。

  • \text{DimFM}[i-1] : (正方形の)入力特徴マップの次元数
  • \text{DimFM}[i] : (正方形の)出力特徴マップの次元数
  • \text{DimSten}[i] : (正方形の)ステンシルの次元数
  • \text{NumFM}[i-1] : 特徴マップ入力の数
  • \text{NumFM}[i] : 特徴マップの出力の数
  • ニューロンの数 : \text{NumFM}[i]\times\text{DimFM}[i]^2
  • 出力特徴マップあたりの重みの数 : \text{NumFM}[i-1]\times\text{DimSten}[i]^2
  • レイヤ当たりの重みの数 : \text{NumFM}[i]\times\text{出力特徴マップあたりの重みの数}
  • 特徴マップあたりの演算量 : 2\times\text{DimFM}[i]^2\times\text{出力特徴マップあたりの重みの数}
  • レイヤあたりの演算量 : \text{NumFM}[i]\times\text{出力特徴マップあたりの演算量}=2\times\text{DimFM}[i]^2\times\text{NumFM}[i]\times\text{出力特徴マップあたりの重みの数}=2\times\text{DimFM}[i]^2\times\text{DimFM}[i]^2\times\text{レイヤ当たりの重みの数}
  • 演算量/重み : 2\times\text{DimFM}[i]^2

7.9章のCNNは、\text{DimFM}[i-1]=28, \text{DimFM}[i]=14, \text{DimSten}[i]=3, \text{NumFM}[i-1]=64(入力特徴マップの数), \text{NumFM}[i]=128(出力特徴マップの数)である。 このレイヤでは25,088個のニューロン、73,728個の重み、28,901,376演算量が必要である。したがって演算強度は392である。 私たちの例では、CNNはMLPのfully connectedなレイヤよりも重みの量は少なく、高い演算強度を持っている。

f:id:msyksphinz:20180101181633p:plain
図7.9 CNNのレイヤ[i-1]における入力特徴マップ(左側)からレイヤ[i]の出力特徴マップへの一般的なステップ。

3次元の入力特徴マップから、単一の出力特徴マップへの生成を行う。各出力特徴ーマップはそれぞれ独立した重みの集合を持っており、ベクトル―行列積によりすべての要素が演算される。点線は将来衛星される特徴マップである。この図が示しているように、入力および出力特徴マップの次元及び数はしばしば異なるものになる。MLPと同様に、ReLUはCNNのための有名な非線形関数である。

再帰ニューラルネットワーク

3番目のDNNの型はRNNである。これは音声認識や言語翻訳などの分野で有名なネットワークである。 RNNはDNNモデルに対してステートを追加して順次入力を追加することにより、RNNが事実を記録することが出来るようになる。 これはハードウェアにおける組み合わせ論理とステートマシンの違いと似ている。 例えば、あなたが非との性別を学習したい場合、翻訳した言葉を記憶しておき、あとでもう一度パスさせたいということもあるであろう。 RNNの各レイヤは前のレイヤで生成した重みと入力の掛け合わしたものと、前の状態を入力として受け取る。 重みは、時間のステップで再利用される。

「Long short-term memory(LSTM)」はRNNの種類としては現在断然有名なネットワークである。 LSTMはこれまでのRNNが重要な長期情報を記憶することが出来なかった問題に解決策を示した。

これまでの2つのDNNと異なり、LSTMは仮想的なデザインである。 LSTMは「セル(cell)」と呼ばれるモジュールから構成されている。 セルは完全なDNNモデルを生成するためのテンプレートもしくはモデルと考えることが出来る。 これはMLPを並べて完全なDNNモデルを生成させる問題と似ている。

図7.10はLSTMセルがどのようにお互いにリンクしているのかを示している。 各セルは左から右に接続されており、ひとつのセルの出力が次のセルの入力へ接続されている。 またこれは図7.10においてトップダウンで時間軸として展開されている。 したがって、文章はアンロールされたループの1回の繰り返し当たりの入力となる。 LTSMの名前が示す通りの長期記憶と短期記憶の情報は、トップダウンであるイタレーションから次のイタレーションへ渡される。

f:id:msyksphinz:20180102003210p:plain

図7.10 互いに接続されたLSTMセル

図7.11にLSTMセルの内容を示す。 図7.10に示したように、入力値は左側、出力値は右側に示しており、2つのメモリの入力は上側、2つのメモリの出力は下側に示している。

f:id:msyksphinz:20180102003237p:plain

図7.11 LSTMセルは5つのベクトル行列積、3つの要素幅乗算、1つの要素幅加算、6つの非線形関数を含んでいる。

各セルには5つのベクトル行列積を実行し、5つの独立した重み値を使っている。 入力値の行列積は図7.7のMLPのようになっている。 3つのそれ以外の行列積は「ゲート(gates)」と呼ばれており、あるソースから標準出力もしくはメモリ出力として渡される際の情報をゲートもしくは制限するためのものである。 ゲートあたりに通過する情報はこれらの重みにより設定される。 もし重みがほとんどゼロ、もしくは小さな値であった場合、多くの情報は通過しない; 一方で、これらの重みがほとんどが大きければ、ゲートはほとんどの情報を通過させる。 3つのゲートは「入力ゲート(input gate)」「出力ゲート(output gate)」「忘却ゲート(forget gate)」と呼ばれている。 最初の2つのゲートは入力と出力をフィルタリングし、最後のゲートはLong-termメモリパス中で何を忘却するかを決定する。

Short-termメモリの出力はShort-Termの重みとベクトル行列積を通じて、そのセルの出力となる。 SHort-termラベルはセルの入力を直接使用されないため適用される (xxx)。

LTSMセルの入力と出力はすべて互いに接続されているため、3つの入力・出力のペアのサイズは同一である。 セルの中身を見てみると、すべての入力と出力はしばしば同じサイズであるという十分な依存が存在する。 これらはすべて同じサイズ出ると仮定し、これを text{Dim} とする。

たとえそうであっても、ベクトル―行列積はすべて同じサイズではない。 3つのゲートの乗算は3\times\text{Dim}である。なぜならば、LSTMはすべての3つの入力を接続するからである。 入力のベクトルは 2\times\text{Dim} である。なぜならばLSTMは入力とShort-termメモリの入力を1つのベクトルとして接続するからである。 最後の乗算の入力は単純に出力に接続されるため 1\times\text{Dim} である。

したがって、重みと演算量は以下のように計算できる。

  • セル当たりの重みの数 : 3 \times(3\times\text{Dim}\text{Dim})+(2\times\text{Dim}\times\text{Dim})+(1\times\text{Dim}\text{Dim})=12\times\text{Dim}^2
  • 1セルあたりの5つのベクトル行列乗算量: 2\times\text{セル当たりの重みの数}
  • 3要素の乗算及び1回の加算に演算量(ベクトルはすべて出力のサイズ): 4\times\text{Dim}
  • セル当たりの演算量(5ベクトル行列積と4要素幅の演算): 24\times\text{Dim}^2+4\times\text{Dim}
  • 演算量/重み: ~2

7.9章のLSTMでは6つのセルを持っておりDimは1024である。 重みの量は12,582,912であり、演算量は25,169,920である。演算強度は2.0003である。 LSTMはMLPと同様に重みを多く保持しており、CNNよりは演算強度が低い。

Computer Architecture 6th Editionの7章"Domain-Specific Architecture" を読む (7.3章 DNNのニューロン・トレーニングと推論)

ヘネパタ第6版こと、"Computer Architecture 6th Edition" では、第7章でドメイン固有アーキテクチャの章が新設された。 これを機会に、しっかり読んでいこう。

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

Computer Architecture, Sixth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

7.3章はがっつりディープニューラルネットワークの内容だ。用語集も入っている。これを機にしっかり勉強しよう。

目次

これは著者が読んだ内容をまとめているだけなので、誤訳、理解不足により誤っている可能性があります!鵜呑みにしないようにお願いします。


7.3 例 : ディープニューラルネットワーク

人工知能(Artificial Intelligent:AI)は次世代のコンピューティングの次なるビッグウェーブであるだけでなく、人類の歴史の大きなターニングポイントかもしれない...知能の進化は、データ、ニューラルネットワーク、そして計算パワーによって起きるのかもしれない。 IntelはAIに投資している... 我々は、AIの普及と発展に必要な最新のアクセラレータを開発した。

人工知能は正規の切り替わりをまたいで、ドラマティックな返り咲きをした。 人工知能を、多くのロジカルループとして「組み立てる」代わりに、議論の焦点は人工知能を通過させるサンプルデータから、「マシンラーニング(Machine Learning)」へと移り変わった。 学習に必要なデータの量は考えていたものよりも非常に多くのものが必要であった。 今世紀のウェアハウススケールコンピューティング(Warehouse Scale Computing: WSC)により、数十億のユーザと彼らのスマートフォンから、十分な量のデータがインターネット上で見つかったペタバイトの情報を収納して格納し、十分なデータ量を提供している。 私たちはこの非常に多くのデータから学習を行うのに必要な計算の量を低く見積もった。 しかし、GPUというWSCのサーバに組み込まれている単精度浮動小数点の計算コストが非常に高い計算機を使うことにより、十分な計算量を提供できるようになった。

機械学習の一部分であるDNNと呼ばれる領域は、過去5年間でAI分野のスターということが出来る。 DNNは例えば言語翻訳の能力を向上させ、過去10年間の進歩に比べて、さらに進歩を遂げている(Tung, 2016; Lews-Kraus, 2016); DNNに切り替えることにより、過去5年間で達成している画像認識のエラー率は26%から3.5%に減少した(Krizhevsky et al., 2012, Szegedy et al, 2015; He et al., 2016); そして2016年には、DNNは囲碁の分野において初めて人間を倒すことが出来るプログラムを生成することが出来るようになった(Silver et al., 2016)。 多くのこれらの技術がクラウドで実行されているが、第1章で述べたように、これらはスマートフォン上でGoogle翻訳を実行することが出来る。 2017年には、新しい重要なDNNの研究結果が毎週発表されるようになっている。

本章に書かれていること以上に、DNNについて興味を持った読者は TensorFlowのチュートリアルをダウンロードして実行してみるべきだ (TensorFlow Tutorials, 2016)。そこまで野心的でない場合でも、DNNの無料のオンラインテキストを読んでみることをお勧めする。

DNNのニューロン

DNNは脳のニューロンからインスパイアされている。 人工ニューロンはデータ値と「重み(weights)」もしくは「パラメータ(parameters)」を掛け合わせたものを加算し、それを非線形関数に通して結果を出力する。 これから見ていくように、人工ニューロンはファンインとファンアウトが大きい。

画像認識のためのDNNでは、入力値は画像のピクセルであり、ピクセル値は重みが欠けられる。 多くの非線形関数が施行されたが、現在広く使われているのはf(x)=max(x, 0)というシンプルなものであり、これはxが負数であれば0となり、整数であればxそのものの値が返される。 この関数はRectifier Linearユニットもしくは ReLUという複雑な関数名で呼ばれている。

人工ニューロンクラスタは、入力値のそれぞれ異なる場所を処理し、クラスタの出力は次の人工ニューロンクラスタの入力値となる。 入力レイヤと出力レイヤの間のレイヤは「隠しレイヤ(hidden layer)」と呼ばれる。 画像処理のためには、各レイヤは異なるタイプの形を認識するレイヤと考えることが出来、エッジや角度などを認識する低レベルのレイヤから、目や鼻を認識する高レベルのレイヤへと進んでいく。 もし画像処理アプリケーションが、犬が移っている画像を認識する場合は、最後のレイヤの出力は0から1までの確率の値で表現されるか、どの犬の品種であるかを示す確率のリストとして表現される。

DNNではレイヤの数により名前が付けられる。 データ数と計算能力が低い時代には、ニューラルネットワークの層数は比較的浅かった。 図7.5は際k人のDNNのレイヤ数、重みの量およびフェッチされる重みあたりの演算量が示されている。 2017年では、いくつかのDNNは150のレイヤ数を持っている。

名前 DNNレイヤ 重みの数 演算量/重み
MLP0 5 20M 200
MLP1 4 5M 168
LSTM0 58 52M 64
LSTM1 56 34M 96
CNN0 16 8M 2888
CNN1 89 100M 1750

トレーニング v.s. 推論

前章までの議論は、既にプロダクションレベルに入っているDNNについての議論であった。 DNNの開発はニューラルネットワークアーキテクチャ; レイヤの数とその型、各レイヤの次元とデータのサイズを決めることから始まる。 専門家は多くの新しいニューラルネットワークアーキテクチャを開発するが、ほとんどの、実際にニューラルネットワークを使用する人は、既存の類似の問題に対するニューラルネットワークと同様のネットワークを選択することになる(例えば、図7.5)。

一度ニューラルネットワークの形を選択すると、次のステップでは、ニューラルネットワークグラフの各エッジの重みを決めていくことになる。 重みによって、モデルの挙動が決定される。ニューラルアーキテクチャの選択に依存して、単一のモデルで数千から何億個もの重みを決めていく必要が生じる(図7.5を参照のこと)。 トレーニングは、これらの重みをチューニングするためのプロセスであり、DNNが複雑な関数を近似するためにコストのかかる処理である (例えば、画像からその画像内のオブジェクトをマッピングする処理など)。

この開発フェーズは一般的に「トレーニング(training)」あるいは「学習(learning)」と呼ばれ、一方でプロダクションフェーズは多くの名前で呼ばれている「推論(inference)」「予測(prediction)」「scoring(採点)」「実装(implementation)」「評価(evaluation)」「実行(running)」「テスト(testing)」である。 殆どのDNNは「教師あり学習(supervised learning)」と呼ばれる、データがあらかじめ処理されており正しいラベルを取得することのできるデータ群を使って訓練が実行される。 したがって、ImageNet DNNのコンペティションではトレーニングセットは120万枚の画像と各画像は1000カテゴリに渡ってラベルが振り分けられている(Russakovsky et al., 2015)。 いくつかのラベルは非常に詳細に記述されており、例えば犬や猫の種類まで記述されている。 優勝者は、別に用意された50,000毎もの画像をDNNに通して、最も低い誤認識率を得られるかによって決定される。

ニューラルネットワークの重みづけは、トレーニングセットを使用してニューラルネットワーク内の「バックワード(backward)」処理を繰り返すことによって設定される。 この処理のことを「バックプロパゲーション(backpropagation)」と呼ばれる。 例えば、トレーニングセット内で犬の種類について情報が得られれば、DNN内でこの画像が何であるかが分かり、今後より正確な答えが出せるようにDNN内の重みが調整される。 驚いたことに、トレーニングプロセスの最初に重みを最初にランダム値で設定すべきであり、トレーニングセット内で誤認識率が十分に小さくなるまで繰り返して学習させるべきである。

数学が好きな読者のために説明すると、学習の目標は入力値が複数レイヤのニューラルネットワークアーキテクチャを通して正しい出力値にマッピングさせることである。 バックプロパゲーションは「誤差のバックプロパゲーション(back propagation of errors)」の略である。 バックプロパゲーションはすべての重みについて、入力値の勾配を計算し重みを更新することで、誤認識率を最小化させるためのアルゴリズムである。 DNNにおいてもっとも有名な最適化アルゴリズムは「確率的勾配降下法(stochastic gradient descent)」である。 このアルゴリズムによって、バックプロパゲーションによって得られた降下の勾配を最大化するような重みを比例的に設定する。 より詳細に学びたい読者はNielsen(2016)もしくはTensorFlowのチュートリアル(2016)を参照されたい。

図7.6に示すように、トレーニングには数週間を要する場合がある。 推論フェーズは、データあたりで100ms程度であり、数百万分の一の時間である。 トレーニングは、一回の推論操作に対して非常に多くの時間がかかるが、推論のための全体の計算時間はDNNを使用するユーザの数の積となり、DNNをどの程度使用するかに依存している。

トレーニングが終了すると、あなたはあなたが使用したトレーニングセットが実際に推論を実行するデータを代表したものである事を願ってDNNをデプロイする。 あなたのDNNは非常に人気があり、あなたが開発に費やした時間よりもはるかに多くの時間ユーザに使用される!

図7.6 いくつかのDNNにおけるトレーニングセットの大きさ及びトレーニングに必要な時間(landola, 2016)

データタイプ 問題領域 ベンチマークトレーニング セットのサイズ DNNアーキテクチャ ハードウェア トレーニングの時間
text[1] 単語の推論 (word2vec) 1000億単語 (Wikipedia) 2レイヤ skip gram 1 NVIDIA Titan X GPU 6.2時間
audio[2] 音声認識 2000時間の音声 (Fisher Corpus) 11レイヤ RNN 1 NVIDIA K1200 GPU 3.5日
images[3] 画像分類 100万画像 (ImageNet) 22レイヤ CNN 1 NVIDIA K20 GPU 3週間
video[4] アクティビティ認識 100万動画 (Sports-1M) 8レイヤ CNN 10 NVIDIA GPU 1ヶ月

トレーニングデータセットの無いタスクというものも存在する。例えば、現実世界のイベントにおいて未来を予測するようなタスクである。 ここでは言及しないが「強化学習(reinforcement learning(RL)」という有名なアルゴリズムが2017年には使用されるようになっている。 トレーニングセットによって学習する方式の代わりに、RLは現実世界において動作し、報酬関数と呼ばれる、あるアクションから状況が良くなるか悪くなるかを決定する関数から信号を受け取る。

急速に変化するフィールドにおいて予測をすることは難しいが、3種類のDNNが2017年には主流になっている: 「多層パーセプトロン(MultiLayer Perceptron:MLP)」、「畳み込みニューラルネットワーク(Convolutional Neural Networks: CNNs)」、「再帰ニューラルネットワーク(Recurrent Neural Networks: RNNs)」である。 これらはすべて教師あり学習であり、トレーニングセットに依存するものである。