前回は、FPGA での処理は「いつ」「なにを」「どうする」だけではなく、「だれが」と「どこで」が必要という話をしました。また、言い換えれば、CPU はデータに対して処理を変えていくのに対し、FPGA は処理の連なりを作り、それにデータを流していきます。第4回では、この「処理の連なり」を作る方法について考えていきます。
いきなり登場、データフローグラフ！
ここで現実の FPGA の世界とこれまでの回で説明してきた概念的な「小人さんの世界」との関係を対応付けしておきます。少し専門的な用語を使った説明になりますが、その辺はご容赦ください。
| やりたいことの | 現実の CPU | 現実の FPGA (小人さんの世界) |
| 記述方法 | プログラム言語 | プログラム言語またはハードウェア記述言語 (レシピ) |
| 処理方法 | 手続き的 | データフロー的 (流れ作業) |
| 変換方法 | コンパイラ | 高位合成ツール＜プログラム言語の場合＞ 論理合成ツール＜ハードウェア記述言語の場合＞ 配置配線ツール |
ハードウェア記述言語は、CPU のプログラム言語に似ていますが、「流れ作業」が書きやすくできています。また、この流れ作業をデータフローと言います。フローとは流れのことで、データが流れて処理されていくというわけです。
一方、プログラム言語で FPGA の処理を書く場合は、「なぞ変換」が一つ増えます。これを高位合成ツールと言います。このツールはプログラム言語の記述を入力して、ハードウェア記述言語の記述を出力する変換ツールです。ハードウェア記述言語の記述は論理合成ツールで FPGA が理解できる記述に変換され、配置配線ツールで FPGA の各処理要素 (これは小人さんの世界では小人さんそのものにあたります) に割り振られ、その要素間を信号線 (ベルトコンベヤー) で接続します。
論理合成ツールについては、これまで全く説明してきませんでしたが、気にしなくても問題ありません。なぜなら、FPGA の難しさはここではないからです。第一回で出てきた「なぞ変換」の一つという認識で十分です。配置配線ツールは、前回、カレー工場で小人さんへの役割の配置とベルトコンベヤーの接続 (配線) を行うツールです。これも「なぞ変換」の一つですが、これについては前回説明しました。
ここでデータフローグラフという表現方法を導入します。とは言っても驚くことはありません。すでにほぼ同じものを前回示しています。そう、カレー作成フローです。概念的には同じです。
CPU のプログラムでは、フローチャートがプログラムの流れを書くのに使われてきました。過去形で書いているのは、現在のプログラミングではあまり使われなくなってしまったからです。一方、FPGA の処理を表現するデータフローグラフは、人手で作成するというよりも「なぞ変換」の中で処理を表現するのに使われています。つまり、高位合成ではプログラム言語で書かれた処理が色々変換されて、内部的にデータフローグラフで表されているのです。したがって、論理合成で処理されるハードウェア記述言語の記述は、このデータフローを意識した記述になっています。その方が FPGA で実行しやすい回路が出来上がります。
実は、ハードウェア記述言語で FPGA の処理を書くのが難しいのは、同じプログラム言語のように見えるのに、手続き的な記述ではなくデータフロー的な記述をしなければならないからです。なので、普通のプログラマは混乱しますよね。
カレー作成フローを詳しく見てみよう
では、カレー作成フローを使って、どのように処理されていくのかをもう少し詳しく見ていきましょう。
食材を「切る」作業工程は、カレー作成フロー上では食材ごとに4並列で処理されていますが、その中身は食材ごとに異なります。例えば、じゃがいもやたまねぎは皮をむく前処理が必要です。さらに、同じ「切る」でも、切るのに必要な時間も異なります。ここでは楕円をステップ＝単位時間として処理するものとします。つまり、肉を切るの必要な時間は2ステップ、じゃがいもは、前処理に2ステップ、切るのに1ステップ、という感じです。これらの合計10ステップ分の作業を小人さんに割り振って仕事をしてもらうのですが、この「切る」作業工程全体では、何人で行うのが最も良いでしょうか？
また、この作業の条件は、1) 前処理があるものは終わるまで切れない、2) 食材は切り終わるまで変えることはできない、3) 小人さんは前処理か切るかのどちらかしかできない、となります。そして、この作業の「最も良い」解とは、なるべく少ない小人さんで、なるべく少ないステップ数で完了することです。逆の見方をすると、遊んでいる小人さんが少ない方が良いとも言えます。
さて、ここには「切る」作業は合計7ステップ分、「前処理」は合計3ステップ分あります。これを4人、3人、2人の小人さんで分担して作業してもらいます。
その結果は、下図のようになります。
(a) は4名の小人さんが「前処理」1名で「切る」3名です。(b) は2名づつ「前処理」と「切る」作業に当たります。(c) は3名で「前処理」1名で「切る」2名です。そして、(d) はそれぞれ1名の2名の小人さんで作業するケースです。
見てもわかる通り、(a) (b) (c) はどれも4ステップですが、(d) は7ステップ掛かっています。同じ時間で済むなら少ない人数の方が良いので、このケースでは (c) が最も良い解になります。点線枠の遊んでいる時間を見ても (c) が最も少ないので効率が良いですね。
このような、小人さんへの作業と人数を決める作業をアロケーションと言います。実際の FPGA の設計においては、高位合成ツールの内部で、データフローグラフを元に回路リソースを割り当てるところで行っています。
スケジュール管理が問題だ
さて、次は (c) の作業のスケジュールを考えます。このケースはほぼこのまま処理を進めていけばいいので、下図のようになります。
この図の (a) がスケジューリングされた結果です。最初のステップでたまねぎと肉が投入され、それぞれ1名の小人さんが作業を開始します。次のステップに行くところで「前処理」の小人さんは「切る」にたまねぎを渡し、じゃがいもを受け取ります。現在、肉を切っている小人さんは、作業継続です。ステップ3では、じゃがいもの前処理の小人さんとたまねぎを切っている小人さんは作業継続で、肉を切っていた小人さんは切り終えた肉を「焼く」に出力するとともに、にんじんを受け取り切り始めます。そして、最後のステップ4に行くところで、前処理の小人さんは切る小人さんにじゃがいもを渡し、たまねぎを切っていた小人さんはそれを「焼く」に出力します。そして、ステップ4ではじゃがいもを切ります。ニンジンを切っていた小人さんは継続です。ステップ4の終わりでそれぞれじゃがいもとにんじんを「焼く」に出力して終わりです。
このように日本語で書くとすごく分かりにくいですが、グラフ表現するとわかりやすいですね。これはツール内でも同じです。なので、様々な設計ツールではグラフ表現がよく使われています。
そして、それらを小人さんに割り当てる
そして、小人さん3名で「切る」作業を行うために、どのタイミングで食材が投入され、誰が何をして、どこに出力するかの接続を、このスケジューリング結果に基づいて決めます。それが図の (b) になります。このような作業をバインディングと言います。また、その時には、接続関係も作成します。
もちろん、これらも実際の FPGA 設計の高位合成ツールで行われている工程です。このように 1) データフローグラフの作成、2) アロケーション、3) スケジューリング、4) バインディング、5) データパス生成 (接続関係の作成)という5つの工程が自動化されており、手続き的なプログラミング言語で書かれた処理内容を、「流れ作業」的なハードウェア記述言語の記述へ変換されます。
まとめ
今回のまとめです。
今回はカレー工場をつくるためにカタカナがいっぱい出てきてしまいました。申し訳ありません。分かりにくかったでしょうか？
まとめると、FPGA で処理するための手順は、1) 処理されるものと処理する内容をグラフで表します、これをデータフローグラフと言います。次に、2) これを行うために人うような部品 (FPGA ではいろいろな回路資源に相当) の種類と個数を見つけ出します。この作業をアロケーションと言います。そして、3) それを時間に従って並べます。これがスケジューリングです。最後に、4) 具体的な部品に割り当てます。これをバインディングと言います。一般的にはアロケーションで求めた個数からスケジューリングによって共用できる部品が見つかりますので、バインディングでは部品数が少なくなります。また、同時に接続関係も確定します。このような一連の処理は、現代の高位合成ツールでは自動的に行われています。すごいですね。
さて、今回の真の結論は、「料理はレシピを箇条書きで書くよりも、データフローグラフで書いた方がわかりやすい」ってことかもしれません。次回最終回は、小人さんの正体について迫っていきたいと思います。お楽しみ！
熊本大学 大学院先端科学研究部 飯田全広
※ 主に Peggy und Marco Lachmann-Anke による Pixabay からの画像を使用しました。