こんにちは。この「Synthesijer と高位合成ツールの作り方」のシリーズでは、全5回を通じて Synthesijer をベースに FPGA 向けの簡単な高位合成処理系を作る方法を紹介していきます。例は Java ですが、お気に入りの言語向けの処理系を開発する足がかりとして利用できるように紹介できればと思ってます。
前回は、Synthesijer がプログラムをハードウェア・ロジックに変換する過程を紹介しました。今回は、内部情報の変形処理として、前回の例で登場した並列化とチェイニングがどのような変換処理で生成されたかを紹介します。
並列化
たとえば、次のようなプログラムが与えられたとします。
public class Basic1{
public int func(int a, int b, int c, int d){
return (a * c) - (b * d);
}
}与えられたプログラムからは、次のような内部情報が生成されます。この表現になってしまうと、あまり Java の面影はありません。実際、go2ir では、Java ではなく Go 言語からこの表現を生成しています。
(MODULE Basic1
(VARIABLES
)
(BOARD INT func
(VARIABLES
(VAR INT func_a_0000 :public false :global_constant false :method_param true :original a :method func :private_method false :volatile false :member false)
(VAR INT func_b_0001 :public false :global_constant false :method_param true :original b :method func :private_method false :volatile false :member false)
(VAR INT func_c_0002 :public false :global_constant false :method_param true :original c :method func :private_method false :volatile false :member false)
(VAR INT func_d_0003 :public false :global_constant false :method_param true :original d :method func :private_method false :volatile false :member false)
(VAR INT binary_expr_00004_1 :public false :global_constant false :method_param false :original binary_expr_00004 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00005_1 :public false :global_constant false :method_param false :original binary_expr_00005 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00006_1 :public false :global_constant false :method_param false :original binary_expr_00006 :method null :private_method false :volatile false :member false)
)
(SEQUENCER func
(SLOT 0
(METHOD_EXIT :next (1))
)
(SLOT 1
(METHOD_ENTRY :next (2))
)
(SLOT 2
(SET binary_expr_00004_1 (MUL32 func_a_0000 func_c_0002) :next (3))
)
(SLOT 3
(SET binary_expr_00005_1 (MUL32 func_b_0001 func_d_0003) :next (4))
)
(SLOT 4
(SET binary_expr_00006_1 (SUB binary_expr_00004_1 binary_expr_00005_1) :next (5))
)
(SLOT 5
(RETURN binary_expr_00006_1 :next (0))
)
(SLOT 6
(JP :next (0))
)
)
)
)一番外側の MODULE は Java のクラスに相当し、ハードウェア生成時のモジュールに対応します。インスタンス変数の集合 VARIABLES と、メソッドに相当する BOARD を持ちます。
この例では、func という Java のメソッドが、func という名前の BOARD です。BOARD の中はメソッドの中で定義された変数 VARIABLES とメソッドの処理に相当する SEQUENCER から構成されます。
SEQUENCER はステートマシンとして生成される処理の集まりです。ステートマシンの各ステートを構成するのが SLOT です。各 SLOT には、そのステートで処理が確定する SchedulerItem のインスタンスが格納されます。SchedulerItem は、二項演算程度の処理に相当します。たとえば、
(SET binary_expr_00004 (MUL32 func_a_0000 func_c_0002) :next (3))は、元のプログラムにあった a * c が SchedulerItem として切り出されたものです。
SEQUENCER は、メソッド呼び出しに相当するイベントが発生するまで METHOD_EXIT で待機し、メソッド呼び出しに相当するイベントが発生すると METHOD_ENTRY から順に SLOT を辿ります。METHOD_EXIT に辿りつけばメソッドの処理が終了します。
実行時間を短くしたければ辿るべきスロットの数を減らす必要があります。並列実行では、一つのスロットに複数の処理をつめこんでスロットの数を減らします。ソフトウェア実行のように処理を実行できるコアの数に決まりがあるわけではありませんので、与えられたコードからできるだけたくさん同時に実行できる処理を見つけられるといいですね。
ここでは、同時に実行しても問題ない SchedulerItem を見つけるためにデータ依存グラフを作って考えてみます。出現する変数に着目して、ある変数に書き込んでいる SchedulerItem と、その変数を利用している SchedulerItem の間に親子関係を設定します。次の図が、METHOD_ENTRY から METHOD_EXIT の間の一連のスロットのデータ依存グラフです。なお、あらかじめ上書きされる変数に別名を付ける SSA によってデータ依存解析が簡単になっています。
今回の例からは、次のようデータ依存グラフが得られます。
この図をみると、SLOT4 には、SLOT2 と SLOT3 のデータが必要ですが、SLOT2 と SLOT3 は互いにデータ依存がないことがわかります。これは、SLOT2 と SLOT3 を同時に実行しても元のプログラムの意図を壊さないということを意味します。
それを踏まえて SLOT にアイテムを詰めなおすと、次のように変換した内部表現が得られます。
(MODULE Basic1
(VARIABLES
)
(BOARD INT func
(VARIABLES
(VAR INT func_a_0000 :public false :global_constant false :method_param true :original a :method func :private_method false :volatile false :member false)
(VAR INT func_b_0001 :public false :global_constant false :method_param true :original b :method func :private_method false :volatile false :member false)
(VAR INT func_c_0002 :public false :global_constant false :method_param true :original c :method func :private_method false :volatile false :member false)
(VAR INT func_d_0003 :public false :global_constant false :method_param true :original d :method func :private_method false :volatile false :member false)
(VAR INT binary_expr_00004_1 :public false :global_constant false :method_param false :original binary_expr_00004 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00005_1 :public false :global_constant false :method_param false :original binary_expr_00005 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00006_1 :public false :global_constant false :method_param false :original binary_expr_00006 :method null :private_method false :volatile false :member false)
)
(SEQUENCER func
(SLOT 0
(METHOD_EXIT :next (1))
)
(SLOT 1
(METHOD_ENTRY :next (2))
)
(SLOT 2
(SET binary_expr_00004_1 (MUL32 func_a_0000 func_c_0002) :next (4))
(SET binary_expr_00005_1 (MUL32 func_b_0001 func_d_0003) :next (4))
)
(SLOT 4
(SET binary_expr_00006_1 (SUB binary_expr_00004_1 binary_expr_00005_1) :next (5))
)
(SLOT 5
(RETURN binary_expr_00006_1 :next (0))
)
)
)
)最初の内部表現で、SLOT2 と SLOT3 に分かれて格納されていた SchedulerItem が共に SLOT2 に格納されています。これで状態遷移のステップを1つ削減できました。
チェイニング
今度は、次のようなプログラムが与えられたとしましょう。
public class Basic2{
public int func(int a, int b, int c, int d){
return (a + c) - (b + d);
}
}並列化まで適用した段階の内部表現は次のように得られます。データ依存がない、(a + c) と (b + d) に相当する SchedulerItem が一つの SLOT にまとめられていることがわかります。
(MODULE Basic2
(VARIABLES
)
(BOARD INT func
(VARIABLES
(VAR INT func_a_0000 :public false :global_constant false :method_param true :original a :method func :private_method false :volatile false :member false)
(VAR INT func_b_0001 :public false :global_constant false :method_param true :original b :method func :private_method false :volatile false :member false)
(VAR INT func_c_0002 :public false :global_constant false :method_param true :original c :method func :private_method false :volatile false :member false)
(VAR INT func_d_0003 :public false :global_constant false :method_param true :original d :method func :private_method false :volatile false :member false)
(VAR INT binary_expr_00004 :public false :global_constant false :method_param false :original binary_expr_00004 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00005 :public false :global_constant false :method_param false :original binary_expr_00005 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00006 :public false :global_constant false :method_param false :original binary_expr_00006 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00004_1 :public false :global_constant false :method_param false :original binary_expr_00004 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00005_1 :public false :global_constant false :method_param false :original binary_expr_00005 :method null :private_method false :volatile false :member false)
(VAR INT binary_expr_00006_1 :public false :global_constant false :method_param false :original binary_expr_00006 :method null :private_method false :volatile false :member false)
)
(SEQUENCER func
(SLOT 0
(METHOD_EXIT :next (1))
)
(SLOT 1
(METHOD_ENTRY :next (2))
)
(SLOT 2
(SET binary_expr_00004_1 (ADD func_a_0000 func_c_0002) :next (4))
(SET binary_expr_00005_1 (ADD func_b_0001 func_d_0003) :next (4))
)
(SLOT 4
(SET binary_expr_00006_1 (SUB binary_expr_00004_1 binary_expr_00005_1) :next (5))
)
(SLOT 5
(RETURN binary_expr_00006_1 :next (0))
)
)
)
)さて、SLOT2 と SLOT4 に格納されているスロットにはデータ依存があります。そのため、並列に実行すると元のプログラムの意図に反した結果が生じます。ところで、この二つの処理はハードウェア化した場合に独立したステートで実行するような処理でしょうか？
ハードウェア化した場合に大きな組み合せ回路にならないのであれば、まとめて処理してしまっても問題はありません。このような場合に一つのスロットにまとめあげる最適化がチェイニングです。
プロセッサでも MAC 演算のように積と和を一命令で適用する演算がありますね。プロセッサではよく使われ実行時間の短縮の寄与する命令をあらかじめ用意しておいて、ソフトウェアがそれを利用することで実行時間を短縮します。一方で、高位合成では、プログラム中に現われる演算群から1クロックで実行する命令をチェイニングで生成できます。
ただし、いくらでも組み合わせればよいというものではありません。理想的には、実装対象の FPGA のアーキテクチャや素子の遅延、達成したい動作周波数を考慮して最適な処理を1クロックで処理するグループにまとめるべきです。
現状の Synthesijer では、手抜きして、適当なスレッショルド数以内の平易な演算(和差、論理演算など)を見つけたときにチェイニングを適用するようにしています。チェイニングを適用した結果、内部表現は次のように得られます。
今回の例では、以下のような内部情報に変換します。
(MODULE Basic2
(VARIABLES
)
(BOARD INT func
(VARIABLES
(VAR INT func_a_0000 :public false :global_constant false :method_param true :original a :method func :private_method false :volatile false :member false)
(VAR INT func_b_0001 :public false :global_constant false :method_param true :original b :method func :private_method false :volatile false :member false)
(VAR INT func_c_0002 :public false :global_constant false :method_param true :original c :method func :private_method false :volatile false :member false)
(VAR INT func_d_0003 :public false :global_constant false :method_param true :original d :method func :private_method false :volatile false :member false)
(VAR INT binary_expr_00004_1 :public false :global_constant false :method_param false :original binary_expr_00004 :method null :private_method false :volatile false :chaining ((func 2 func 2)) :member false)
(VAR INT binary_expr_00005_1 :public false :global_constant false :method_param false :original binary_expr_00005 :method null :private_method false :volatile false :chaining ((func 2 func 2)) :member false)
(VAR INT binary_expr_00006_1 :public false :global_constant false :method_param false :original binary_expr_00006 :method null :private_method false :volatile false :member false)
)
(SEQUENCER func
(SLOT 0
(METHOD_EXIT :next (1))
)
(SLOT 1
(METHOD_ENTRY :next (2))
)
(SLOT 2
(SET binary_expr_00004_1 (ADD func_a_0000 func_c_0002) :next (5))
(SET binary_expr_00005_1 (ADD func_b_0001 func_d_0003) :next (5))
(SET binary_expr_00006_1 (SUB binary_expr_00004_1 binary_expr_00005_1) :next (5))
)
(SLOT 5
(RETURN binary_expr_00006_1 :next (0))
)
)
)
)(SET binary_expr_00006_1 (SUB binary_expr_00004_1 binary_expr_00005_1) :next (5)) を、入力データを生成している (SET binary_expr_00004_1 (ADD func_a_0000 func_c_0002) :next (5)) および (SET binary_expr_00005_1 (ADD func_b_0001 func_d_0003) :next (5))と同じスロットに格納することで、スロット数を一つ削減できました。なお、元の場合と違ってチェイニングの場合、同じスロット内で変更されるデータを利用する必要があります。これは、変数の側で :chaining ((func 2 func 2)) として、スロット2で更新する値がスロット2でそのまま使われるという目印を付け、間違った値で計算しないように取り扱っています。
まとめ
Synthesijer における内部情報の変形処理として並列化とチェイニングの様子を紹介しました。次回は、もっとアグレッシブな変形処理の様子を紹介しようと思っています。
わさらぼ・みよしたけふみ