SA によるマッピング探索手法

SAに代表されるメタヒューリスティクスアルゴリズムは，ランダムに生成したマッピング 探索解とその近似解を繰り返し探索する事で，広い探索範囲に対しても適用可能な手法であ る．DRAとして一般的に用いられているアレイ型アーキテクチャでは，マッピングの自由度 の高さを利用し，SAを用いたマッピング探索が行われている [45] [21] [30]．

しかし，本論文で対象とするパイプライン型アーキテクチャモデルでは，演算のマッピング の自由度が低いため，SAを用いた場合に探索時間が増大してしまう問題がある [43]．これは 図1.5において任意の2つの演算器間のパスが多数あることと比較して，図1.6の任意の2つ の演算器間のパスはごく少ない，もしくは存在しないことからもわかる．つまり，アレイ型 アーキテクチャは配線がマッピング探索解を発見しやすいのに対して，パイプライン型アーキ テクチャは，マッピング探索解そのものがほとんど存在していない．

SAは，ランダムな解から出発し，より良い解を目指して，その状態の局所近傍を探索するア ルゴリズムである．局所近傍解が，元の解よりも改善されれば，局所近傍解を基本解として置 き換える．基本解とは，次の局所近傍探索のベースとなる解である．局所近傍解が，元の解よ りも改善されなくても，ある確率により，基本解として置き換えられる．この確率は，探索が

進むにつれて，徐々に下がっていく．これにより，探索初期における局所最適解への収束を防 ぐことが可能となる．配置配線アルゴリズムにおいては，DAGのノードの配置探索と，DAG のエッジと配線パターンの探索を同時に行うことは，解がより離散的となり，近傍解を探索し ていくSAアルゴリズムに適さないと判断した．そこで，対象とするパイプライン型アーキテ クチャの全ての PECにおいて，予め配線パターンを固定した上で，DAGの配置探索のみを SAによって行い，解が得られれば終結する．解が得られない場合には上記固定配線パターン を変更して配置配線を繰り返す．なお，パイプライン型アーキテクチャにおける配線パターン の組み合わせは，すべての組み合わせを順に実行していく．

基本となるSAの疑似コードを次に示す．

Simulated Annealing Algorithm

s :=s 0, e :=E(s), s b:=s, e b:=b, k := 0 Begin

while k < kmax and e > emax

s n:=neighbor(s), e n:=E(s n)

if random()< M etropolis(e, e n, temp(k/kmax)) then s:=s n, e:=e n

if e < e b then

s b:=s, e b:=e k :=k+ 1

return s b End

sは基本解である配置配線状態を表し，s 0はランダムに生成されたその初期基本解とする．

配置配線アルゴリズムにおける基本解とは，対象となるパイプライン型アーキテクチャの各演 算器とDAGにおけるノードの対応状態を示している．eはSA におけるエネルギーつまり評 価値を表し，E(s)は基本解sにおける評価値を表している．配置配線アルゴリズムにおける 評価値は，配置されたノード間の配線一致率である．これは，配置配線アルゴリズムが，あら かじめ与えられた配線に対して DAGの配置探索を行い，与えられた配線とDAG における エッジとの一致率によって解の良し悪しを判断しているためである．これにより，完全に一致

した場合は，評価値0とし，一致率が下がるにつれて評価値が増大するように評価関数を作 成した．s bとe bは，それぞれ得られた最良解とその評価値を表している．k はSAの終了 条件の一つであるステップ数を表しており，kmax が最大ステップ数となる．neighbour(s) は基本解 sの近傍解を返す関数である．配置配線アルゴリズムでは，基本解 sにおいてラン ダムに選択した演算器ノードと隣接する演算器のノードを交換することで近傍解を生成する．

temp(k/kmax)は局所解の置き換えの際に重要な温度パラメータである．配置配線アルゴリ

ズムでは，解のエネルギーが改善されれば1を返し，エネルギーが改善されなければk/kmax を返す．M etoropolis(e, e n, temp(k/kmax))は局所解の置き換えの際に，新しい状態を採用 するか棄却するかの判断基準を与える関数である．配置配線アルゴリズムでは，e < e nの場

合は 1を返し，e ≥ e nの場合はe^{(e−e n)/temp} を返す．この値とランダムに生成した値を比

較することで，局所解の置き換え有無を判断する．

このようなSAによるマッピング探索手法を構築することにより，ベースとしたSAと比較 して高速にマッピング探索解を発見することが可能となる. ただし，SAを考える際に重要と なるパラメータである 総ステップ数kmaxについては，対象とする問題に応じて調整する必 要がある．なお，SAを用いた新たなマッピング探索手法が，パイプライン型アーキテクチャ に適用可能であるかどうかは，第5章実験評価における提案手法との比較によって確認する．

第 4 ^章

提案手法

本章では，DAGの複雑度指標と，パイプライン型アーキテクチャ向けのマッピング手法に ついての提案を行う．

まず，コンパイラにおけるフィードバック機構の可用性を向上させるための複雑度指標につ いて説明する．