OUT A OUT B
4.1 複雑度指標
第 4 章
提案手法
本章では，DAGの複雑度指標と，パイプライン型アーキテクチャ向けのマッピング手法に ついての提案を行う．
まず，コンパイラにおけるフィードバック機構の可用性を向上させるための複雑度指標につ いて説明する．
複雑さによって，マッピング探索の困難さが変化する事を示している．DAGの複雑さと実行 時間の関係が明らかになった場合，マッピング時間が短いと予想されるクラスタリング結果か らマッピング探索を実行する事ができ，フィードバック機構を効率的に利用したコンパイラ提 案を行うことが可能となる．さらに，マッピング探索の上限時間設定を行うことでマッピング 時間そのものを短縮できる可能性がある．
以上のことから，DAGの規模や複雑さを，パイプラン型のALU数，配線数とDAGのエッ ジ数，ノード数を用いて表すComplexityという指標を導入した．Complexityの算出方法を 式(4.1)に示す．
Complexity(G) = (Vnum∗Enum)/(ALUSU M ∗EDGESU M) (4.1) Complexity(G)はDAGGのComplexityを表している．VnumはGのノード数，Enumは Gのエッジ数を表しており，図5.43のクラスタリング結果より算出できる．また，ALUSU M はアーキテクチャ全体における ALU 数，EDGESU M はエッジ数の総数を表しており，図 5.43のクラスタリングと配置配線によって算出できる，分子はDAGの規模を表しており，分 母はアーキテクチャの規模を表している．これにより，様々な規模のパイプラン型アーキテク チャのALUと配線に対して，DAG Gのノードとエッジの充填率を得ることができる．充填 率が高いほどマッピング探索領域が増えることから，これを複雑度指標とした．
データ依存解析 データ依存解析データ依存解析 データ依存解析 ソースプログラム ソースプログラム ソースプログラム ソースプログラム
データフローグラフ データフローグラフ データフローグラフ データフローグラフ
実行コード 実行コード 実行コード 実行コード クラスタリング クラスタリングクラスタリング クラスタリング
演算・ユニット対応情報 演算・ユニット対応情報 演算・ユニット対応情報 演算・ユニット対応情報
配置・配線 配置・配線配置・配線 配置・配線
構成情報構成情報構成情報 構成情報
ユニットスケジューリング ユニットスケジューリングユニットスケジューリング ユニットスケジューリング
Feedback Checker
Search Time Checker
Feedback
Feedback
図4.1 FlexSwordTMコンパイラにおけるフィードバック機構