FPGA開発日記

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

Computer Architecture 6th Editionの7章"Domain-Specific Architecture" を読む (7.7章 Pixel Visual Core, パーソナルモバイル画像処理ユニット)

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.7章は DSAの一つの例としてPixel Visual Coreを取り上げている。

あまりネット上で見たことのない情報が公開されているが、参考文献はどこなのだろうか? あるいは、David.A Patterson 先生はGoogleにも所属しているので、そこからの情報なのかな。 用語集とか、かなりありがたい。

目次

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


7.7章 Pixel Visual Core, パーソナルモバイル画像処理ユニット

Pixel Visual CoreもGoogleの開発したモバイル向けのDSAユニットである。 これは、コンピュータビジョン処理に最適化したDSAであり、携帯電話やタブレット上のチップとして、Androidによって制御されるk、音を想定している。

マルチコアのデザインになっており、2から16コアの構成をサポートしており、TPUというよりもSystem on Chip(SOC)として動作することを想定している。

モバイル向けのためTPUよりも構成としては非常に小さく、消費電力も小さく構成されている。

Pixel Visual Coreについて理解するために、まずは用語集を作成した。この用語を参照しながら解説を読み進めていってほしい。

用語 略語 簡単な説明
コア プロセッサ。Pixel Visual Coreは2~16コアを持っている。最初の実装では8コアが使われた。これは「ステンシルプロセッサ(Stencil Processor:STP)」とも呼ばれている。
Halide 画像処理向けのドメイン固有プログラミング言語で。アルゴリズムの形式と実行スケジュールを分離することを目的としている。
Halo 16×16の計算アレイにおいてステンシル計算を実行するにあたり、アレイの境界に近い場所を拡張した領域。この領域は値を持っているが、計算はしない。
画像信号処理プロセッサ ISP 画像の品質を向上させるための固定機能を持ったASIC。カメラを搭載しているすべてのPMDで見つけることができる。
画像処理ユニット IPU GPUと逆の問題を解決するためのDSA。入力画像を解析しコントラストなどを変更することで出力画像を生成する。
Line Buffer Pool LB ラインバッファ処理中の画像を中間結果を格納し、次のステージをすぐに実行することができるようにするためのバッファ。すべてのラインを保持できるように、十分な大きさを用意している。
ネットワークオンチップ NOC Pixel Visual Core内のコアを接続するためのネットワーク
物理ISA pISA ハードウェアで実行される、Pixel Visual Coreの命令セットアーキテクチャ(ISA)
プロセッシングエレメントアレイ 16×16のプロセッシングエレメントとhaloによって処理される16bitの積和演算。各プロセッシングエレメントには、ベクトルレーンとローカルメモリが搭載されている。4方向のどちらにも、データをシフトして転送することができる。
シートジェネレータ SHG 1×1から31×31ピクセルのブロックのメモリアクセスのことを「シート」と呼ぶ。Haloの領域を搭載するかを含めて、他のサイズはオプションである。
スカラーライン SCL ベクトルレーンと演算としては同一なのだが、ジャンプ、分岐、例外、生後命令によりベクトルアレイを制御できる命令が加わっていることが異なる。すべてのシートジェネレータのロードストアをスケジュール管理する。小さな命令メモリも含んでいる。スカラプロセッサ中のベクトルアーキテクチャと同じような役割である。
ベクトルレーン VL プロセッシングエレメントの一部分で、計算を行う。
仮想ISA vISA コンパイラによって生成されるPixel Visual CoreのISA。命令実行前に、物理ISAにマッピングされる。

Pixel Visual Coreは新しいクラスのドメイン固有アーキテクチャで、画像処理のために画像処理ユニット(Image Processing Unit:IPU)というものを搭載している。 IPUはGPUと逆の問題を解決するためのDSAで、入力画像を解析しコントラストなどを変更することで出力画像を生成する。 IPUはDSAなので、CPUやGPUなどが、DSAが苦手とする領域の処理を行ってくれるためすべての処理をDSAで実行する必要はない。 IPUはCNNの項目で開設した、CNN計算に依存している。

Pixel Visual Coreの新しいところは、SIMD命令のような1次元の処理だけでなく、2次元の処理も実行できるようになっている点である。 PEのネットワークは2次元で構成されており、これによりオフチップのメモリにアクセスする必要性も最小化される。 このアーキテクチャにより、CNNアルゴリズムや画像処理の中心であるステンシル計算を、ハードウェアを使ってシンプルに実行することができるようになる。

ハードワイヤードなIPUであるISP

カメラを搭載しているモバイルデバイス(Personal Mobile Device: PMD)には必ず、ハードワイヤードなアクセラレータであるISP(Image Signal Processor)が搭載されている。 ISPは固定機能を持ったASICで、仮想的にすべてのISPに搭載されている。

図7.30は基本的な画像処理システムの構成を示している。 画像処理システムには、レンズ、センサー、ISP、CPU、DRAM、ディスプレイなどが搭載されている。 ISPは画像を受け取ると、レンズとセンサーから人工物を除去し失われた色を補完する。 そして、全体的な画像の品質を向上させる。 PMDは小さなレンズを使うのでピクセルにゴミが乗りやすくなり、したがって高い品質の画像とビデオを生成するためにはこれらの処理は不可欠である。

f:id:msyksphinz:20180106225337p:plain
図7.30 一般的な画像処理プロセッサの構成。画像処理プロセッサ(ISP)、CPU、DRAM、レンズ、センサで構成されている。

ISPプロセッサはハードウェアビルディングブロックをソフトウェアでコンフィグレーションしながら処理を進める。 一般的には、各ステージをパイプライン化してメモリトラフィックを最小化するように設計され、少しのピクセルを入力し、少しのピクセルを出力する。 計算内容は主に隣接したピクセルとのステンシル計算であるが、これらの計算の結果は「ラインバッファ」と呼ばれるバッファに格納される。 ラインバッファにより隣接するピクセルの局所性を使用して、中間画像を保持することによってすべてのラインをキャプチャ氏、中間結果を次のステージに転送することができる。

ISPは効率的であるが、2つの問題点がある。 ポータブルデバイスの処理能力が向上するにつれ、画像の品質は向上していき、ISPのフレキシビリティの無さが問題となってくる。 特に新しいISPをSOC上に設計するためには、数年の歳月を要することになる。 2つ目の問題は、この計算リソースが、画像の品質を向上させるためだけに利用されるということである。 これはPMDにおいて常に必要とされる処理ではない。 現在の世代のISPは高性能向けのPMDでは2Tops/sの処理を実行することができ、DSAに置き換えても同様の処理能力と効率性を達成することができる。

Pixel Visual Coreのソフトウェア

Pixel Visual Coreを一般的なハードワイヤードなパイプライン構成と考えると、ISPと同様に有効非巡回グラフ(directed acyclic graph:DAG)に落とし込むことができる。 Pixel Visual Coreの画像処理プログラムは一般的にHalideで記述される。 Halideはドメイン固有向けの関数型プログラミング言語で、画像処理に適している。 図7.31に画像をぼかす処理をHalideで記述した例を示す。 Halideはプログラムの機能を示す領域と、プログラムのスケジューリングを行う領域を分離して記述することができ、ハードウェア上で機能をどのようにして最適化するかを指定することができる。

Func buildBlur(Func input)
    // 機能記述領域 (ターゲットプロセッサとは独立している)
    Func blur_x("blur_x"), blur_y("blur_y");
    blur_x(x,y) = (input(x-1,y) + input(x,y)*2 + input(x+1,y))/4;
    blur_y(x,y) = (input(x,y-1) + input(x,y)*2 + input(x,y-1))/4;
    
    if (has_ipu) {
        // スケジューリングの領域(ターゲットプロセッサに対してどのように最適化を行えばよいかを示している)
        blur_x.ipu(x,y)
        blur_y.ipu(x,y)
    }
    
    return blur_y;
}
図7.31 画像をぼかす処理をHalideで記述した例

Pixel Visual Coreのアーキテクチャ哲学

Pixel Visual CoreはPMDデバイスで実行されるため、10~20秒で6~8Wを消費し、スクリーンが消されると10mW程度に消費電力が減る。 これらのPMDの消費電力に対応するため、Pixel Visual Coreは相対的なエネルギーコストにおいて調査を行っており、図7.32に示す。 単一の8-bit DRAMアクセスは、12,500個の8-bit加算もしくは7~100回の8-bit SRAMアクセスと同一の消費電力である。 また、IEEE 754の浮動小数点演算のコストは8-bitの整数演算の22倍から150倍の電力を消費し、ダイサイズは大きくなる。

操作 エネルギー(pJ) 操作 エネルギー(pJ) 操作 エネルギー(pJ)
8b DRAM LPDDR3 125.00 8b SRAM 1.2-17.1 16b SRAM 2.4-34.2
32b Fl. Pt. muladd 2.70 8b int muladd 0.12 16b int muladd 0.43
32b Fl. Pt. add 1.50 8b int add 0.01 16b int add 0.02
操作ごとのエネルギーコスト。TSMC 28-nm HPMプロセスでの測定結果。このプロセスはPixel Visual Coreで実際に使用している。

7.2章のガイドラインに加えて、Pixel Visual Coreは以下の観点により設計されている。

  • 2次元は1次元の構成よりも良い
    • 2次元の構成により、画像処理にのデータコミュニケーションの距離を最小化することができる。
  • 遠いよりは、近いほうが良い: データの移動は高価である
    • さらに、データをALUに移動するコストも増加する。DRAMの処理時間とエネルギーコストは、ローカルストレージでのデータ移動に比べるとずっと高い。

IPUの目的は、ハードウェアプログラマビリティを与えることにより画像処理以外の用途にも使うことができるようにすることだ。 Pixel Visual Coreには以下の3つの用途がある。

  1. 2次元構成は1次元の構成よりも優れているという考え方により、Pixel Visual Coreは2次元のSIMDアーキテクチャを採用している。
  2. 2次元アレイ上にプロセッシングエレメント(PE)を配置している。
  3. PEは以下の要素で構成される。
  4. 16-bitというデータ幅は、このドメインで必要なデータ精度を考慮したうえで決定されている。

  5. Pixel Visual Coreは各PEに一時記憶保存が必要である。PEのメモリはコンパイラにより制御されるスクラッチパッドメモリである。PEメモリの論理的なサイズは、16bit×128エントリで、256バイトである。各PEに分離した小さなSRAMを搭載することは実装的に非効率なため、Pixel Visual CoreはPEメモリを8つのPEでグループ化し、1つの幅広いSRAMブロックとして構成している。

  6. PEはSIMDの形式で処理するため、Pixel Visual Coreはすべての読み込みと書き込みの処理をまとめてSRAMにリクエスト薄ことができる。
  7. これはより小さな複数個のSRAMを使うよりも効率的である。
  8. 図7.33に4つのPEの例を示している。

  9. すべてのPEで同時にステンシル計算を実行するため、Pixel Visual Coreは隣接するPEから入力データを集める必要がある。

  10. このために、NSEW(North, South East West)のネットワークを持っている。
  11. PE間でデータを任意の方向にシフトすることができ、このため画像をシフトして行っても、画像が端でロストすることはない。
  12. Pixel Visual Coreはネットワークの一番後ろでトーラス構造をとっている。

ソフトウェアは明示的にデータを所望の方向に移動させることができる。 一方でハードウェアによって制御される死すトリックアレイは、2次元のパイプラインは一方にのみ転送され、ソフトウェアからは見ることができない。

Pixel Visual CoreのHalo

3×3、5×5、7×7のステンシルでは、入力データとして1、2、3個の余分なピクセルを入力する。 Pixel Visual Coreは、

  • 入力値のみを渡すために境界付近でハードウェアを利用する。
  • ALUを除去した単純なPEを使ってわずかに2次元コアを拡張する。

単純なPEと通常のPEは2.2倍の面積の違いがあるため、Pixel Visual Coreは8×8のPEの外に2行2列のPEを拡張している。 この拡張された領域をhaloと呼んでいる。 図7.34は2行2列の拡張を行っており、左上で5×5のステンシル計算を行っている。

f:id:msyksphinz:20180106225320p:plain
図7.34 Pixel Visual Coreの2次元アレイは、中央のPEと周囲のHaloと呼ばれるシンプルなPEコアで構成されている。

Pixel Visual Coreのプロセッサ

16×16個のPEと1次元当たり4つのHaloによって、PEアレイもしくはベクトルアレイと呼ばれ、Pixel Visual Coreの主要な計算ユニットである。 シートジェネレータ(Sheet Generator: SHG)というロードストアユニットを持っている。 SHGは1×1から256×256ピクセルのブロックのメモリ中で参照することができる。

Pixel Visual Core内部は2コア以上のPEを含んでいるので、PE間はNOCで接続されている。 NOCは基本的に隣接PEとの接続する構成となっている。 このNOCは2次元メッシュ状に構成されている。

Pixel Visual Coreはスカラレーンというプロセッサも持っている。 このスカラレーンは、ベクトルアレイに普通のプロセッサのように、ジャンプ、分岐、割り込み、命令制御フローなどの処理を実行してはならない。 このスカラレーンは小さな命令メモリを持っており、これはスカラプロセッサのSIMD命令のフローに似ている。

さらに、Pixel Visual CoreはDMAエンジンを持っており、DRAMとラインバッファの転送を高速に実行することができる。

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よりは演算強度が低い。