新しい Binary Deep Neural Network としての LUT(Look-up table) Network: Ryuzのブログ

はじめに

　引き続き新しいバイナリネットとしてのLUT-Network が着実に進歩してきたので、途中経過をブログにまとめて行きたいと思います。

　 FPGAをターゲットに、リソース効率と速度重視の学習が出来る Binary Deep Neural Network(Binary-DNN)を目指しています。
　十分なベンチマークはできていませんが、FPGAなどのハードウェアロジックにターゲットを限定し、その回路構成と等価なネットを直接学習させることで、従来のバイナリニューラルネットワークに比べて、数十倍～数千倍程度の効率が狙える可能性があることが見えてきました。

　なお、これら一連の作業はgitgubにて随時公開しております。

　動向は概ねTwitterでつぶやいております。

前回までの経過と課題

　細かい経緯は過去記事を読んでいただくとして、前回までの成果を整理すると

「FPGAの6入力LUTで作ったネットワークのテーブルを力技探索で最適化するとLUT数に対して高い認識率が得られた。しかし深い学習はNP問題となり、特に畳込みは学習困難だった」
「6入力LUTの変わりに6入力の積和に限定したSparseAffine で層を作れば、LUTに一対一にマッピングできる状態を保ったまま、Binary-DNNの手法で逆伝播でCNNなどの畳込みを含む深い学習が行えたが、リソース効率が悪かった」

　というところです。

　その内容を簡単に図にまとめて見ました。従来の密結合に対して、疎結合なLUT-Netのアプローチです。

　なお、出力はバイナリ化するためにBatchNorm と BinaryActivation を含んでおり、これは従来のBinary-Network 研究者の成果をそのまま利用させていただいています。そして出力がバイナリなら当然次の段の入力はバイナリになりますので、１段目の入力をバイナライズすればすべての層で入出力がバイナリになります。

今回の進展

　そこで、今度は課題だった効率の向上と逆伝播の活用を両立させるために、逆の発想を行いました。

　「入力が6個で出力が1個のバイナリ入出力の素子であれば、中でどんな演算をしていても1個のLUTにマッピングできる」という事実を元に、「LUTの表現可能なものは全て学習できるニューラルネットワークは何か？」を考えました。

　LUTは１個の素子でXORが表現可能です。ご承知の通り、現在のDNNではXORを学習させるには中間層が必要です。

　そこで思い切って

「LUT1個に対応するネットを、中間層を持ったネットにしてしまおう」
「中間層を持つとそこにも活性化が必要なのでここは素直に浮動小数点のまま、SigmoidやReLUなどの従来の活性化を入れよう」
「出力でバイナリにすれば、入出力はバイナリなのでLUTにマップできる」

　その思想で、ネット構成の基本単位を記述したのが以下です。

　ここで、LUTモデルの中間層の個数はどれぐらいあればLUTの表現能力を十分引き出せるのかという問題があります。

　そこで、6入力1出力の中でもっともパーセプトロンが苦手としそうな6次のXORを個別に学習させて見ました。つまり入力を i0～i5 の 6個としたときに出力が i0^i1^i2^i3^i4^i5 となるように学習を試みました。

　その結果が下記です。

　中間層をM個として、64パターンのバッチデータを作り、上限を 4,194,304 epoc として200回づつ試行しています。

　最小で中間層4で学習できていますが、99.5%が局所解に落ちて学習失敗しています。逆に中間層16ぐらいからほぼ100%に近い学習ができるようになってくる模様で、そこから先は中間層を増やすごとに少ないepoc数で学習できるようになって行くようです。

　ここで重要なのは、ここでの中間層をいくつ増やしてもFPGA化したときのリソースは、たった一個のLUTであることに変化はないと言うことです。

　結局、バイナリ表現する限り、入力で取りうるパターンは2^6=64パターンしかなく、それを全部テーブル化してしまえば、そのままFPGAのLUTに収まります。中間層は学習を行う際にLUTの表現力を引き出すための便宜上の計算要素に過ぎません。
　そして、テーブル化自体はソフトウェアでもおなじみの高速化手段かと思います。計算は複雑だがパターン自体が少ないものを効果的に実装可能にしてくれます。

　ここで、XORだけの検証で十分なのか不安なども残しますが、少なくとも中間層が64種類あれば、テーブル化する64bitの各発火条件を個別のパーセプトロンに割り当て可能ですので、理屈としてはLUTが取りうる全てのパターンを学習可能と考えます。
　後は学習時のデータの数などから学習回数に適した個数に選択していくしかないですが、現実的に計算速度とXOR検証の結果から 16～64 ぐらいの間が落とし所ではないかと想像しています。

　そして、学習時はLUTに対応する「Affine - Activation - Affine - BatchNormalize - BinaryActivation」という単位を１単位として、これを多段に組み合わせて疎結合ネットワークを作って学習させるという方針でネットワークを組んでいきます。

　これは、学習時は非常に重たいのですが、ひとたびFPGAに移せば

「高効率でLUTを活用したネットワークとなる」
「１段に1LUTしかないので非常に簡単に300～400MHzの合成が通る」

　というメリットが産まれます。

　実際にこのネットワークを使ってNMISTで簡単な実験したところ

「シンプルなAffineをフラットに並べただけのネットで、力技探索と同程度(90%程度)達成」
「力技が困難だった畳込み(CNN)で90%以上の認識率を確認（LUT数:1520個）」

　まで確認できており、今後本格的に認識率を出す構成が模索できそうです。

従来ネットワークとの比較

　ここでもう一度おさらいとして過去のネットワークとの比較表を上げておきます。
　

　従来のバイナリニューラルネットワークが、CPU/GPUでのPredictionの性能改善にあったので、Weightを省メモリで表現することが重要でした。一方で今回の用にFPGAのLUTに結果だけテーブル化する前提であれば、学習(Learning)時の重みは、FP32などのReal型で問題なく、より深い学習が出来る可能性が出てきます。

　Binalized Neural Networks の論文だとMNIST 誤認識 1.40%のようですが、その際の構成は 2048ノードの隠れ層が3層の模様です。

　ここで従来のネットワークは、各層が全結線であるということがFPGA化時にはリソースインパクトの原因となります。バイナリネットワークの当初は重みのメモリ量を減らしてCPUなどでの実行時の効率UPを目指したものなので、FPGA化は特に考慮されていません。

　FPGA化する場合、2048入力から1出力を作るには単に繋ぐだけで最低412個のLUTが必要で、これが各層に2048なので最低2,531,328個のLUTが必要です。実際にはbitを数え上げないといけないので、この数倍から数十倍の規模に合成されると予想されます。これはXNOR-Netでも基本は同じで、スケーリングが入る分さらに増えると予想されます。

　現状、まだ数k個で実験しているLUT-Netはリソース量で1000倍以上少ないので、認識率が同じレベルに来てないのは当然ですし、この段階で90%が見えていること自体結構驚異的なことなのではないかとも思っています。

　市販のFPGAが数千円から数百万円まであり、LUT数も数k個～数M個までラインナップがありますが、現実的に考えると従来手法ではメモリと組み合わせて演算器の再利用が必要と思います。今回のLUT-Netなら１つのFPGA内に全部を一度に入れてワンパスで演算できる可能性があるので、リアルタイム制御のような分野での認識など、あらたな用途に使える可能性があると考えます。

　個人で買えるレベルのFPGAボードですら、Zybo-Z7-20 でLUT数:53,200個、Ultra96でLUT数:70,560個ですので、このレベルから試せる可能性があるのではと考えています。

継続課題

　一方で、LUT-Networkを使ったネットワークの構築は、接続数を6などに制約しているため、どのように接続を作れば効率的なのかがまだ見えていない部分があります。少なくとも、幅については、一度に6接続しか増えないので、例えば36x36のDenseAffine層の置き換えなどは最低でも2段重ねないと学習以前に必要なところに接続が行き渡りません。

　36x36のDenseAffine に対しては、32x6SparseAffine を6段重ねたもので規模が等価ですが、後者のほうが圧倒的にFPGAに小コストでマップできるので、このあたりは複数のSparseAffineを束ねてカプセル化したものを部品として用意すれば、従来の感覚で学習ネットが組んでいけるのではないかと考えています。

　但しまだ、CPUのみで実験環境を作っており、実用的な大きな回路の学習が出来ておらず、この点はまだまだ先が長い課題となりそうです。

------------------

[以下様々な追加アイデアなどについての備忘録]

疎結合について

　現在、SparseAffine の接続について乱数を使っています。それはそれでDropOut的ではありますが、最適とは言えないと思っています。

　最初にDenseAffineで学習しながら、重みを見て徐々に0項を作っていって必要な条件までSparse化していくなどのアイデアがあると思っています。

高位合成言語が不要な点

　この手法は、学習結果がそのままFPGAの回路構成にマップ可能なので、RTLどころか、その気になればネットリストを直接吐けるレベルの構成のままで学習しています。

　逆に言えば、高位合成言語が持つRTLに対する非効率さがあれば、それはそのまま除去されます。

　回路効率だけで言えば、高位合成言語は記述はRTLに劣りますし、RTLもゲート素子を直接記述するのに劣ります。従来のCPU/GPU向けネットワーク記述を高位合成言語に落とす段でも非効率さが入ります。

　その点で、最終回路を直接学習させると言うのは、これらの無駄を排除する試みでもあります。加えて、学習ネットワークを作るユーザーが、そのネットの構築でFPGAでの実装最適を意図に弄ることができます。電気回路というネットワークとは、深層学習というネットワークとそれほど親和性が悪くない気がしています。これはある意味で新しい事だと思います。

動的パラメータ変更について

　このアーキテクチャは重みなどの各種情報をLUTのテーブルにパッキングしています。従ってパラメータ変更にはLUTテーブルの変更が必要になります。しかしこれはFPGAによっては大きな問題にならないと考えます。
　XILINXのLUTはシフトレジスタとしても利用できる機能がありますが、これはそのままテーブルが書き換え可能なLUTとして構成されています。例えばSRLC32Eなどは、テーブル書き換え可能な5入力LUTに他ならず、２つ組み合わせて6入力にすることも容易です(もちろんはじめから5入力LUTでネットを学習してもよいです)。またパーシャルリコンフィギュレーションしてしまえば、そもそも丸ごと書き換え可能ですので、FPGAのLUTを再利用した演算も原理的には可能と考えます。　

プリミティブな計算機アーキテクチャの復権

　今回の方式は4-LUTなどの古いアーキのFPGAでも適用可能と思いますし、2入力にすれば、AND,OR,NAND,XOR, etc からゲートを選ぶ世界に落ちます。
　もしこの方法で、トランジスタの数に見合った性能を、ゲートレベルの素子の学習で引き出せたとしたら、そもそもDL用のLSIを設計するということ自体の価値が低下して、「DL用の回路はDLに設計させる」という新しいパラダイムに移行できる可能性も有しているのではないかと夢を膨らませてみます。

　今までの計算機科学の分野は、いろいろなアルゴリズムを高速に実行できる計算機アーキテクチャを追及してきました。

　一方で、回路をそのままネットワークとして表現することは、アルゴリズムと計算機を一度に設計していることに他なりません。

　この場合、マップするデバイスの演算単位が、シンプルであるほど、ネットワーク設計（アルゴリズム設計）者の自由度が増して性能が出ることになります。

　今、巷で多くの計算機屋が取り組んでいるDL専用のいエンジンを、レガシーな計算機で凌駕出来たらとても面白いことにもなりえるのではないだろうかとも思います。

Ryuzのブログ

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

2018年10月30日 (火)