はじめに
CGRA(Coarse-Grained Reconfigurable Array)は、ソフトウェアによって再構成可能なアーキテクチャであり、AI学習や汎用計算において 柔軟性と高効率化を両立する技術 として注目を集めています。
本記事ではCGRAに対する命令マッピングを考えるうえで欠かせない、 DFG(Data Flow Graph) と MRRG(Modular Routing Resource Graph) の関係について調査した内容の備忘録です。
CGRAとは
CGRAは、複数の演算部やメモリ、レジスタなどから構成され、それらの接続や動作をコンフィギュレーションによって再構成可能なアーキテクチャです。
一般的には、 PE(Processing Element) と呼ばれる処理要素を格子状に配置したアレイ構造を持ち、各PEにはALU(Arithmetic Logic Unit: 算術論理演算装置)、レジスタ、マルチプレクサなどが組み込まれています。
これらのPE群は、内部に配置されたマルチプレクサをコンフィギュレーションによって制御することで、PE間の接続方法を柔軟に変更できます。また、ALUに特定の演算命令を割り当てることで、アプリケーションに特化した演算パイプラインを構成することが可能です。ハードウェアの再構成性を活かして、用途に応じた効率的な計算を実現できる点が大きな特徴となっています。
DFGとMRRGの役割と関係
DFG (Data Flow Graph)
DFG (Data Flow Graph)は、プログラム内の演算処理とそのデータ依存関係を有向グラフとして表現したものです。ノードは加算や乗算などの演算を、エッジは演算間のデータの流れ、依存関係を表します。
CGRAにおける命令マッピングでは、DFGはどの演算をどの順序・依存関係で実行する必要があるのかを明確にする役割があります。
図2にDFGの例を示します。これは以下の演算を表現したものです。
z = (a + b) * (c - d)
MRRG (Modular Routing Resource Graph)
MRRG (Modular Routing Resource Graph)は、 CGRAが持つ計算資源および通信資源をグラフ構造で表現したモデル です。
ノードにはPE内のALU、レジスタ、スイッチ（マルチプレクサ）などが含まれ、エッジはPE間や内部でのデータ転送可能な経路を表します。
MRRGはどこで計算ができ、どの経路でデータを流せるか、というCGRAのハードウェア的な制約を表現するために用いられます。
DFGとMRRGの関係
CGRAの命令マッピング問題は、DFGをMRRG上に割り当てる問題として定式化できます。
具体的には、DFGの各演算ノードをMRRG上の計算資源（ALUなど）に、DFGのエッジをMRRG上の通信経路に対応付けることで、DFGで表現された計算をCGRA上で実行可能な構成へと変換します。
このとき、計算資源の競合を避ける配置と通信経路の制約を満たす配線の必要があり、これが命令マッピングの難しさの一因になります。
ここで、先程の演算（図2）をMRRG（図3）に当てはめると図4のような例ができます。
- 加算(+) -> PE0.ALU
- 減算(-) -> PE1.ALU
- 乗算(*) -> PE3.ALU
このとき、
- DFGの演算ノードはMRRG上のALUノードに対応させる
- DFGのエッジはMRRG上の通信経路に割り当てられる
PE2.ALUはこのとき何もせず、スイッチ（マルチプレクサ）によってスキップされています。
もし、通信経路が存在しない、あるいは他の演算と競合する場合、この割り当ては成立せず、CGRAへの命令マッピングはできません。この制約付き割り当ての問題が、CGRAの命令マッピング問題です。
おわりに
本記事では、CGRAのマッピング問題におけるDFGとMRRGの役割について基本的な内容を整理しました。
DFGは演算の命令と依存関係をグラフに表現したもので、ハードウェアリソースを抽象化したMRRGに割り当てることで、実際のハードウェア上の命令配置・配線を表すことができます。
命令マッピング問題はCGRAの効率化には不可欠ですが、制約が複雑化したり、資源が競合する問題や、時間方向への展開、複数のコンテキストを含む問題、など奥が深いので、また調べてみたいと思います。