有限状態機械(FSM)とシンボリック状態探索を利用したコード生成手法(<特集>システムLSIの設計技術と設計自動化)

概要

論文の詳細を見る
高速処理が必要な組み込みシステム向けLSIとして,並列命令や特殊なデータパスユニット,レジスタ構成あるいはバス構成を持つ,アプリケーションに特化したプロセッサが数多く組み込み向け市場に出現している5)〜10).しかし従来のコンパイラ技術1)だけでは,このような特殊なプロセッサの性能を十分引き出すコードを生成できない.この問題を解決する1つの方法として論文2),3)ではまず,コード生成対象のデータフローグラフ(DFG)と,対象とするアーキテクチャの命令セットから有限状態機械(FSM)を作り,そしてそのFSMの状態を1つずつ探索することによって最適コード生成を行う方法を提案している.本稿では論文2),3)と同様のアプローチをとるが,それらの論文と異なりFSMからコード生成する際にFSMをシンボリックに解析することで,はるかに多くの状態を高速に探索したうえで,より最適な並列コードを生成する方法を提案する.論文21)〜23)も本稿と同様にFSMのシンボリック状態探索によりマイクロコードを生成する手法を提案しているが,オペランドの寿命が判定できないため,必要以上に多くの状態を計算してしまう可能性がある.本稿では新たなFSM変数を導入してオペランドが保持する必要があるかどうかを決定するような条件を導き,不要な状態の削減を図る.さらに本稿ではRAMへのスピルおよびリロードも考慮し,コード生成のすべてのフェーズを同時に実行したうえでステップ数最小のコードを生成する.最後に提案手法の実験結果を示す.
一般社団法人情報処理学会の論文
2002-05-15

有限状態機械(FSM)とシンボリック状態探索を利用したコード生成手法(<特集>システムLSIの設計技術と設計自動化)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク