FPGAに機械学習モデルを実装する –
その2：順序回路・パイプライン化
こんにちは，次世代システム研究室のS.T.です。前回に引き続きFPGAネタです。
1.概要
前回実装したランダムフォレスト回路を順序回路化・パイプライン化します。結論から言うと，性能向上には繋がりませんでしたが，クロックに同期して動作することで扱いやすくなりました。
前回の記事では入力が変化すると即座に出力が変化する組み合わせ回路としてランダムフォレストを実装しました。しかし，この方法では木の深さが深くなったり，分岐条件が他ビットになったりすると，遅延が大きくなります。こうなると，ランダムフォレスト回路を制御したり結果を使用して処理をしたりする回路との連携が，少々厄介になります。多くのシステムはクロックに同期して動作する順序回路ですから，ランダムフォレスト回路もこれに合わせたほうが都合がよさそうです。
そこで，今回はランダムフォレスト回路を順序回路として実装します。さらに，スループットを向上させるためにパイプライン化を試みます。
2.環境
今回使用した環境は以下の通りです。前回と同じ環境です。また，使用するモデルも作成したものを流用します。
- FPGAボード：Terasic社 DE0-CV / Intel Cyclone V E 5CEBA4F23C7N
- FPGA開発環境：Quartus Prime Lite 20.1
- FPGA開発言語：Verilog HDL
- シミュレータ：ModelSim Intel FPGA Starter Edition 2020.1
- PC：CPU AMD Ryzen 7 1700X / RAM 32GB / SATA SSD
- ソフトウェア・ライブラリ：Windows 10 / Python 3.6.2 / scikit-learn 0.23.2
3.順序回路化
3-1.順序回路とは
本題に入る前に，順序回路について軽く触れておきます。記事をスムーズに読み進めるための簡単な紹介に留めるので，詳細は専門書などを参照してください。
前回作った組み合わせ回路は，その瞬間の入力に応じて即座に出力が決まる回路でした。順序回路は，状態を持つ回路で，現在の入力だけでなく過去どのような順序で入力が変化したかに応じて出力が決まる回路です(1)。制御を容易にするため，クロック信号に同期して動作することが多く，状態を記憶するためのフリップフロップと，状態の遷移条件や出力を決めるための組み合わせ回路のセットで構成されます。
本記事でも，クロック同期式の順序回路としてランダムフォレストを実装します。
3-2.二分木の配列表現
二分木を表現するためのデータ構造はいくつか考えられますが，今回は配列で表現します。図1に示したように，深さが浅いノードから順に番号を振ると，n番目のノードの左につくノードは2n+1，右につくノードは2n+2となります。この表現方法を使うことで，配列の要素番号の計算のみで木を辿ることができます。各要素番号が指す配列の要素には，ノードの分岐条件や識別結果を格納しておけばよいでしょう。また，2倍する操作は「左1ビットシフト」で実現できるため，要素番号の計算を行う回路も非常にシンプルになります。
3-3.ランダムフォレストの順序回路での表現
配列で表現した二分木を使って，ランダムフォレストを順序回路で実現することを考えます。まずは，単純化のため1本の木を考えます。今回は木1段分の分岐の判定を1クロックで行い，深さ10の木を10クロックで処理する回路を考えます。
ノードで分岐の処理を行うためには，「そのノードが判定する入力ベクトルの要素」「左右に分岐するためのしきい値」の2つの情報が必要です。今回の入力ベクトルの各要素は2値ですから，0なら左，1なら右と判断することができます。そのため，「そのノードが判定する入力ベクトルの要素」を配列の要素として格納しておけば，次の式でノードの要素番号を更新していくことで，木を辿ることができます。
末端の葉まで辿り着いたら，そのノードが持つ識別結果を確認する必要がありますが，これは要素番号と識別結果のペアをMapのような形で別で保持するのがよさそうです。これらをもとに，ソフトウェアの擬似コードで木を辿る操作を記述すると，以下のようになります。
要素番号 = 0
while (葉ノードではない間) {
要素番号 = 要素番号 * 2 + 1 + 入力ベクトル[配列表現した木[要素番号]]
}
return 識別結果Map[要素番号]
今回順序回路をする際のキモは，whileループのブロック内の動作です。1クロックごとに要素番号を更新する部分を抜き出すと，Verilogのコード片は以下のようになります。クロックのネガティブエッジ（立ち下がり）に同期して要素番号を更新します。
wire [783:0] input;
reg [15:0] index;
always @(negedge clk) begin
index <= (index << 1) + 16'd1 + {15'd0, input[index]}
end
これを木の本数分並べて，最後に多数決で結果を決定します。この考え方をベースに，4-2.ランダムフォレストのパイプライン化や5-1.実装で，実際の回路を構築していきます。
4.パイプライン化
4-1.パイプラインとは
パイプライン処理は現代のCPUでおなじみの技術です。処理を複数の工程に分割し，工程ごとに順番にデータを流して処理をすることで，単位時間あたりに処理可能なデータや命令の量を増やす仕組みです(2)。
例えば，前回の作った組み合わせ回路は1回の識別に22nsかかりましたが，これを決定木1段を1工程として分割して，1工程の遅延が10nsになったとします（これはあくまでも例え）。木の深さは10なので，全部で10工程こなすと100nsになってしまい，データを入力してから推論結果を得るまでの時間は伸びてしまいます。しかし，10ns後には次の結果を得ることができます。安定して稼働すると100nsの間に10個の推論結果を得ることができます。組み合わせ回路では100nsの間に4回推論するのがいっぱいいっぱいなので，遅延が大きくなるかわりにスループットを向上することができます。
これは極端な例ですから現実の問題はそう簡単にはいかないと思いますが，とりあえず今回は1工程を木1段としてパイプライン化を試みます。
4-2.ランダムフォレストのパイプライン化
3-3.ランダムフォレストの順序回路での表現で作成した順序回路は木の1段分に相当するため，これを木の深さ分用意して数珠つなぎにすればよさそうです。図2は深さ5の場合の構成図です。
初段ではクロックに同期して外部から与えられた入力ベクトルを取り込み，根ノード（要素番号0）を見て分岐した結果（次の要素番号）をレジスタに書き込みます。2段目以降は，クロックに同期して前段で使用した入力ベクトルを取り込み，前段で計算された要素番号の要素を見て分岐します。
このような構成にすることで，外から与える入力が変化してから5クロック後にその入力に対する出力を得ることができます。
5.実装
5-1.実装
4-2.ランダムフォレストのパイプライン化のアイデアを実装していきます。といっても，構成図をそのままVerilogに落とし込み，前回同様scikit-learnのモデルから分岐条件などを持ってくるだけですが，注意点が2つあります。
- scikit-learnの木の要素番号の振り方は図1とは異なる
- 値が変化するタイミング
前者，要素番号の振り方は深さ優先で振られているようなので，これを図1のように振り直し，分岐条件とラベルを生成します。今回木の深さは10にしていますが，枝によっては10に辿り着く前に結果が定まってしまうものもあります。このままではパイプラインで扱いにくいため，深さが足りない枝にはダミーのノードを繋げて10に揃えています。つまり，全ノード数は2049個，葉ノード数は1024個となります。このうち分岐条件が必要なのは葉以外の1025ノードなので，木1本につき分岐条件が1025個，ラベルが1024個必要になります。今回は木が10本なので，この定数アサインだけで2万行を超えてしまいました；
後者，値が変化するタイミングはシンプルな問題で，「次の要素番号を計算する前に入力ベクトルが切り替わっていなければならない」ということです。今回は，図3に示すようにクロックのポジティブエッジで入力を取り込み，ネガティブエッジで要素番号を更新します。最終的な出力も要素番号の変化=ネガティブエッジに同期して変化します。
木の最終的な出力（識別結果）は最終段の要素番号とコードに埋め込んだラベルから決定します。前回同様それぞれの木の出力から多数決でモジュールの出力を決定します。
周辺の回路は前回とほぼ同様ですが，動作を確認しやすいようにクロックはFPGAボード上のスイッチから送り込むことにします。
5-2.シミュレーション
シミュレーションはクロックを変化させつつリセット，入力1，入力2の順に変化させて，パイプラインの途中のレジスタがクロックに同期して変化していくことを確認しました。図4にシミュレーション結果を示します。
シミュレーション結果から以下のことを確認しました。問題なさそうです。
- 識別結果が正しいこと（入力は7と2の画像）
- リセット解除後，1クロックずつ要素番号が更新され10クロック後に正しい出力結果となること
- 入力ベクトルはクロックのポジティブエッジで変化し，要素番号はクロックのネガティブエッジで変化すること
また，毎クロックごとに入力を変化させたシミュレーションも実施して問題ないことを確認しました。
5-3.実機での実行
実機動作の様子はこちらです。7セグに左が正解，右が推論です。ボード上のボタンからクロックを送り込んでいます。リセット後，最初の入力がパイプラインの最後に到達するまでは不定値が出力され，その後はスイッチを切り替えた数クロック後に推論結果が表示されています。シミュレーション通りの動作になっていますね。
6.遅延の評価
タイミング解析を実施し，パイプライン1段の遅延を確認したところ，Slowコーナーで1段あたり約11nsでした。深く考えず，クロックのduty比を50%とすると，クロック周期はこの倍は必要になりますから，最低でも22ns周期となります。前回の組み合わせ回路では全体で22nsの遅延でしたから，スループットの向上は実現できませんでした。。
組み合わせ回路の実装は全体のゲート数は多いですが，通過するゲートはせいぜい10個程度なので，もともとそこまで遅延が大きなものではなかったため，性能に大きな差が出なかったと考えています。
7.まとめ
今回は前回組み合わせ回路で実現したランダムフォレストを順序回路化・パイプライン化してみました。クロックに同期した順序回路を実機で動作させ推論を行うことができましたが，設計がイマイチだったのか，残念ながら性能向上には至りませんでした。
次回は高位合成などにも手を広げて色々試してみたいと思います。
