表題番号：1999A-214 日付：2002/02/25
研究課題制御フローを主体としたハードウェアの高位合成手法に関する研究
研究者所属（当時） 資格 氏名
（代表者） 理工学部 助手 戸川　望
研究成果概要
　一般に、画像符号化・復号化、プロトコル処理あるいは暗号処理といった、ビット処理あるいは条件分岐処理から構成されるアプリケーションプログラムが専用ハードウェアによって実現されると、ビット処理および条件分岐処理等が並列実行可能となり、マイクロプロセッサによって実現された場合と比較し、高速実行が可能となる。制御処理を主体とする専用ハードウェア設計を自動化する高位合成システムは、1.ビット処理および条件分岐処理といった制御処理を実現するハードウェアを合成可能であり、加えて2.設計者によって与えられた動作仕様に対し複数の設計候補を提供し最適設計を評価する環境を必要とする、と考える。本研究では、このような考えに基づき、制御処理ハードウェアを対象に、C言語による動作記述からハードウェア記述言語によるハードウェア記述を合成する高位合成システムを提案した。本システムは、C言語によるアプリケーションプログラムの動作記述、アプリケーションデータを入力として、アプリケーションプログラムを実現するハードウェア記述を出力する。入力されたアプリケーションプログラムに対し、時間制約および面積制約を満足するハードウェアを複数個列挙する。システムは、(i)コード最適化、(ii)面積/時間最適化、(iii)ハードウェア記述生成の各処理によって実現される。まず、コード最適化は、アプリケーションプログラムを入力とし、これを内部表現となるコールグラフならびにコントロールフローグラフにより表現する。面積/時間最適化は、コールグラフならびにコントロールフローグラフから、時間制約および面積制約を満足する複数個のハードウェア候補を得る。最後に、ハードウェア記述生成系は、面積/時間最適化によって得られたハードウェア候補に対してハードウェア記述を出力する。
　本研究ではさらに、本システムで核となる面積/時間最適化に注目し、これを実現する面積/時間最適化アルゴリズムを提案・構築した。提案アルゴリズムは、入力としてコールグラフおよびコールグラフを構成するコントロールフローグラフ集合を取り、面積制約および時間制約のもとに、コールグラフ全体を表す状態遷移グラフ集合を合成する。まず、時間制約のみを満足する状態遷移グラフを構築し、その後、時間制約を満足する間、面積制約を満足するよう状態遷移グラフを変換することによって複数個のハードウェア候補を得ることができる。提案アルゴリズムは次の特長を持つ。（1）コントロールフローグラフを直接的に操作することで、ビット処理および条件分岐処理といった制御処理を扱うことができる。（2）アプリケーションプログラム全体を表す1個のコールグラフから、面積制約および時間制約を満足する複数個のハードウェア候補を列挙することができる。
　提案した面積/時間最適化アルゴリズムをシステムの一部として組み込み、制御処理アプリケーションプログラムに適用した結果、面積と実行時間とがトレードオフの関係にある複数個のハードウェアを合成することができた。しかも、合成されたハードウェアは、人手設計によるハードウェアに比較して、より面積の小さい結果から面積の大きい結果、より実行時間の小さい結果から実行時間の大きい結果を得た。