先が見え始めた LUT-Network について再整理（中間報告）: Ryuzのブログ

（この記事はまだ推敲予定です）

　ここ数ヶ月こればっかりやっている気がしますが、ようやく畳込みの学習が動くようになり、先が見え始めてきました。

　目標は、

1) 「既存の積和型演算によるDNNのFPGAでの高効率でのマッピング」
2) 「LUT型演算による機械学習自体の新しい方式の探求」

　の２点です。
　前者はインプリメントの話で、実装効率が飛躍的に上がる可能性を秘めているというだけで、従来技術の延長に近い話ではあります（ビジネス的には美味しいかもですが）。
　後者は、現実的にはFPGAが前提になりますが、機械学習自体に対して、積和型のニューラルネットでは行えない範囲を攻めようと言う少し非連続な進化を狙ったアグレッシブなもので、「学習データで近い結果が出る」ってとこだけ縛ってもっと論理圧縮しちゃえというものです。

　本サイトでは２点を同じプラットフォームで同時に探っているので、混乱させさている部分はあるかと思いますが、今回はず前者の話です。

　ざて、前回も表を作りましたが、本サイトで考案した LUT-Network について、畳込み層の動作確認が出来ましたので、下記のように更新しました。

　LUT-Networkの特徴として、Weightを実数で計算しても、活性化をバイナリにした上で、接続数を6とかに制限した疎行列であれば効率的にFPGAのLUT１個にマップできるというものがあります。

　で、こんな疎な結合のネットのままで本当に畳込み層が学習できるのかやってみたのが、下記のログ画面です(執筆時なお計算続行中)。

（なお、ソースは随時 github にはpush しながら進めていますので、masterブランチはいつも散らかっていますが、興味のある方はどうぞ。）
　

　　なんと先ほど80%の正解率になりました(追記：その後85%も達成)。これでネット構造として確認できていないのは、深いネットワークの学習が出来るかどうかだけになりました(効率検証は後で少し述べます)。

　上記は、MNISTに対して、 Conv-Conv-MaxPool-Conv-Conv-MaxPool-Conv-Conv の構成で、6つのConv層があり、全ての層はチャネル数30で設定しており、入力が1チャネルの1段目のみLUT:30個、残り5段は、LUT:210個、つまり重み演算に使っているLUTはトータル 1080個のみと言う微小回路です。Cnvのフィルタサイズは 3x3、MaxPoolは2x2です。

　MaxPool は、単なるORなので、チャネル数分のLUT(30個)あれば実装できます。また畳込みのためのラインバッファも、3x3時の合成で、LUT:93, BRAM:2というのがこれまた当サイトのFPGAプラットフォームで、Sobelフィルタなどで300MHz級で合成確認済みのものがあります(2x2はさらにBRAMが半分になります)。

　ですので、もろもろ計算に入れて机上計算するとLUT:1605 BRAM：7の超微小回路で、MNIST ~~80%~~ 85%の正解率(現在なおも上昇中)になりました。

　この実験はもともと認識率はどうでもよくて、疎行列＆バイナリの構成で、畳込みで学習が進行するかを小さな回路で見たかっただけなのですが、思いのほか認識率もでる結果になりました。
　勝手ながらこちらのサイトを参考になせて頂くと、CNV構成のLUTは数十k個のLUT消費のようですので、今のところ一桁以上小さくてもここまで動くというところです。
（なお、認識率が同じになった場合にどうかと言うのはまたこの後の話）。

　ここで一度、LUT-Networkの演算リソースについて整理しておきます（一旦 Predictionの話で、Learning 時はまた別の話です）。

　上記は、各種DNNのネットワークと演算リソースを表にしてみたものです。

　バイナリ演算について、GPUの演算器構成の情報が乏しいので、主に Intel の x64 命令(AVX2/FMA世代)と、FPGA、ASICを検討しました。
　CPUは順次演算器をあるだけ割り当てていくしかないですが、FPGA/ASICは少ない演算器を使って時間を掛けてマルチサイクルで計算することも、演算器をパイプライン上に並べてスループット１で計算することもどちらも可能なので、比較のために両方記載しています。

　なお、LUT-Network はパイプライン並列時に最大性能になることを狙ったアルゴリズムです。

　CPUでは１つの重みを計算する1コアあたりの演算サイクル数(今回はスループット1の命令しかないので、実質命令数)。それ以外では消費リソース量を考えています。

Affine(float)

　いわゆる従来のDNNです。１つの重みをFMAの積和命令１個で処理できます。AVX2で単精度実数は8並列で処理できます。なので１個当たり1/8=0.125サイクルとなります
（本当は、スーパースカラ効くのでさらに半分とかなんですけど、ややこしくなるので）。
　一方で、FPGAやASICの場合は、浮動小数点積和演算器を構成するのでその分のトランジスタ面積を消費します。FPGAの場合はハードマクロの整数乗算器(DSP)とLUTを幾つか組み合わせて計算します。

Affine(int16)

　いわゆる従来のDNNの整数版です。int8でもいいのかもしれませんが、IntelのSIMDにint8の積和命令が無いので、一旦16bitで試算しました。
　CPUだと、並列数が倍になります。FPGA/ASICだと浮動小数点積和演算器より小さく演算器が構成できます(ASICのゲート数は超適当なのでおかしいかもです)。

Binary Connect

　重みのみバイナリ化したネットです。重みがバイナリなので加減算しか発生しません。しかし、CPUだと加算と積和が同じ1サイクルなのでなんとなんの高速化も起こりません。ただしメモリ使用量が激減するのでキャッシュヒット率が上がります(これも上手にコード書かないと恩恵に与れませんが)。

BNN/XNOR-Network

　どちらも活性化と重みの両方がバイナリ化されています。ですので計算がビット演算のXNORだけで終わります。AVX2だと１命令で256個計算できるので、１個あたり 1/256cyceです。この後bit数のカウントがありますが、popcnt命令と言う64bitを一気に数える命令があるので 1/64cycle の追加ですみます。CPUでの実行効率はXNOR-Networkなどが最速ではないかと思います。

LUT-Network
　CPUでまともにやると入力数分離散アドレスでloadしてきて、table引く形になります(表の通りです)。bitシフトしてアドレス作ったりもありますが、一旦loadに隠れる前提で計算してます。テーブル引きはSIMDの苦手とするところだったりします。
　実際にはキャッシュのミスヒットや分岐予測ミスも痛いので、SIMD命令で256並列にした上で、テーブルは引かずに64個のマスク演算にアンローリングしていますが、その場合AVX命令で454命令で、256で割って１個当たり1.77cycle掛かっています(2LUTでも0.11cycle)。いずれにせよ、XNOR-NNetよりかなり遅いレベルです。
　要するに、CPU上では、既存のDNN用のライブラリ類が殆ど使えない上に、フルスクラッチで最適化しても既存のどのアルゴリズムよりやや遅いところまでが限界です。

　一方で、FPGAやASIC化した場合は、殆どロスゼロでそのまま回路にマップできるので非常に効率が良いです。
　なお、積和アルゴリズムの範疇においては、テーブル引き不要なので、浮動小数点環境で SparseAffine 扱いで学習させてしまい、さっさとFPGAにマップするのが良いかとは思います。
　（テーブル付きのLUTは、単ノードでXORも覚えられるおりこうさんなので、これをCPUでやる場合はこうなっちゃいますよ、という話で、これもまた別の話）。

　ちなみに積和の範囲でのLearning話になった場合、実数で計算するので、6LUT程度であればベクトル6本程度は今時のプロセッサならループ内に入れ込めるはずなので、ミニバッチのサイズ多少確保できれば、floatのDenseAffineと同程度か、やや遅いぐらいの性能は出てくれないかなと思っている次第です。

　あとは、Batch Normalization が各層に入るのもやや悪化要因です。Batch Normalizationは他の演算と演算方向が異なり水平方向なので、キャッシュの最適化などもやや工夫が必要かもしれません。

　さて、ここまで見えてくれば、今後やるべきことは割りと明らかで

「TensorFlowやKerasといった既存ツールでマニアックな事が難しいのであれば、代わりになるものを作る必要がある。→ ただいまBinaryBrainという名で実装中」
「既存アルゴリズムに対して、同じ条件で、FPGA移植時のパフォーマンスが高いことを示す」
「まだ机上検討なので、ちゃんとFPGAで実際に動かしてみせる」
「現実的な時間で、実用的なネットを写し取れるだけのパフォーマンスを出せる学習環境の構築。→ このアルゴリズム用のGPUライブラリの検討かな？」

　といったあたりが今後の方向になると思います。

　（その上で並行して、非積和学習もトライしていければと）。

　なお、２つめのパフォーマンスの実証については現在一本流し中です。

　これは畳込みのない単純層を6入力バイナリLUT:25,900個で構成したLUT-Networkの学習過程のスナップショットです。

　先のサイトで、91,131個のLUTで近い構成で誤答率1.6%だそうなので、比較できる正答率まで育てられればと思っています。
（ところで、バイナリ以前に畳込み無しで 98.4% ってKerasでいろいろやってるけどなかなか出ない。細かいチューニングが必要そうです。）

　まだまだ先は長いですが、いろいろと見通し明るくなってはきました。

(追記)
　その後、畳込みの方は、~~81.62%~~85.27%、非畳込みの方は97.36%まで進んだ。
　もっと伸びるかもしれないが、保存機能もないコードをこれ以上走らせてもな部分はあるので、どちらかは一旦打ち切る方向で考え中。

Ryuzのブログ

主にプログラミングやFPGAネタを書いていくブログです。
ホームページはこちら http://ryuz.my.coocan.jp/
新しい記事は Hatena Blog や Zenn にあります。

2018年9月24日 (月)