FWD FWD
4.2.2 P&R Search
P&R Searchでは，DAGのデータ依存関係より各ノードのALU位置と各PEC の配線パ ターンを決定する. ALU位置と配線パターンの決定は,パイプライン構造に沿って行われ, PE 内のALU位置と配線パターンを交互に決定していく. パイプライン構造に沿って探索を行う ことで，各 PE の配置問題や各PEC の配線問題の個々探索を行うことが可能となり，探索 時間が削減されると考えられる．また，配置問題と配線問題との間に発生する制約条件を明 らかにすることで，さらに探索パターンの削減が可能となる．なお，初期のALU 位置はラ ンダムに決定される．この方法について, 図4.4のDAGを用いて説明する．図4.4のDAG
は，PreProcessによって入力から出力までの全てのパスのパス長がPE数と同じに正規化さ
れた DAGである．なお，P E はパイプラインに沿って上から P E0, P E1, P E2,..., P EN−1 とする．
P&R Searchの概要アルゴリズムは次の通りである．
P&R Search Algorithm
i=N −1
while(i≥0 && i < N){
if( Determine P E(i) ==f alse
∥Determine P EC(i) ==f alse) i=i+ 1
else
i=i−1 }
Determine PE(i) では P Ei における ALU 位置を決定しており，Determine PEC(i) では P ECiのパターンを決定している．なお，Determine PE(i)はDetermine PE(i+1)と Deter-mine PEC(i)で決定されたマッピングを元に配置を決定するものであり，Determine PEC(i) についても同様に，Determine PE(i+1)で決定された配置を元に配線を決定するものである．
このアルゴリズムでは，P EN−1 からP E0へ探索を行っており，ALU位置や配線パターンが データ依存関係を満たさない場合は,バックトラック手法を用いて，直前に決定したALU位 置もしくは配線パターンを再設定して探索を行う. ただし，初期のALU位置が不適当であっ た場合は，再度Determin PE(N-1)から探索をやり直す．
以降では， 配線パターンとALU位置の決定方法について具体的に説明する. この決定方法 は, P E0 とP EN−1 のどちらからでも実現可能であるが,ここでは, P EN−1からP E0 へと探 索を行う方法について説明する.
図4.5は, P E4 のALU配置によって P EC3 を決定した結果である. ここでは，図4.4よ り(No.3, No.6)，(No.5, No.7)のノードペアが，それぞれNo.13とNo.12を親とした兄弟関 係にあることを用いて，唯一ノード間の兄弟関係を実現可能な唯一の配置配線パターンである Connection Pattern 3をP EC3 の配線パターンとして選択した．なお，本例では制約を満た すパターンが1つであったが，複数のパターンが探索対象として選択可能なケースも存在し得
２６ ２７ ２８ ２３ ２４ ２２
１８
１７ １９ ２０ １１ １３ １４
４ ６ ７
２５ ２１ １５ １６
８ ９ １０ １２
１ ２ ３ ５
図4.4 入力DAG
る．その場合，P E4のALU位置決定の次にP E3 の配線パターンを探索し，配線選択も含め たバックトラック探索を行う．
ALU位置決定では, 配線パターンの決定による配線とグラフの依存関係が一致するように 行う. P Ei+1 に配置済みのノードのALU位置とP ECiの配線より, P EiのノードのALU位 置が決定する. 図4.6は,この手法を用いてP E3におけるノードのALU位置を決定した結果 である. この例では，No.3がP E4 のALU1に配置されている事から,親子関係にあるNo.10 とNo.13はP EC3 より,P E3 のALU1とALU5に配置される. このとき, No.10とNo.13は ALU1とALU5のどちらにも配置可能なため,配置可能なパターンから任意のパターンを選択 して配置する. 他のP E3 のノードについても, ALU位置の決定を親子関係にあるノード毎に 行う. この手法により，配置パターンの大幅な削減が可能となる．
図4.7は,図4.4のDAGをP E4 からP E0へと配線パターンとALU位置を交互に決定し た結果である. PEのALU位置と配線パターンの決定により,パイプライン型アーキテクチャ モデルにおけるマッピングが可能となる. なお, 配線パターンはグラフの兄弟関係を利用し て探索パターンを削減している．このことは式 (4.3)のマッピング探索数の削減率からもわ かる．
Reduction P attern=unmatched pattern/MPm (4.3)
28 26 27 25
24 23 22 21
18 17 19 20 15 16
11 13 14 8 9 10 12
4 6 7 1 2 3 5
ALU
1 0 2
3 4 5 6 7
PE
0
1
2
3 4
図4.5 配線パターン(PE3)
mは各PEにおいて配置に必要なALU数を示している．unmatched patternは各ノードの 配置パターンを実現できない配線パターンの数を表している．MPm は枝刈りをしない場合 の各 P E におけるマッピング探索数である．これにより，マッピング探索数の削減率を算出 した．
ALU位置も，グラフの親子関係を利用して探索パターンが配線パターン数S 個から配線が 実現できるパターンのみに削減される．配線パターンが図2.2に示される４パターンのみであ ると仮定した場合，図4.5の例では，配線可能パターンが4個から1個に削減されることにな る．残りの3個の配線パターンでは，親子関係が配線によって実現できないためである．これ により，探索時間が大幅に削減される.
28 26 27 25
24 23 22 21
18 17 19 20 15 16
11 13 14 8 9 10 12
4 6 7 1 2 3 5
ALU
1 0 2
3 4 5 6 7
PE
0
1
2
3 4
図4.6 ALU位置(PE3)