PEC = 2 PEC = 4
5.5.2 PE 値変動における複雑度評価
次に，P E = 2,4,6,8,10に関するComplexity の検証を行ったものを，それぞれ図5.34， 図5.35，図5.36，図5.37，図5.38に示す．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time （秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.34 複雑度検証(PE=2)
図5.34では，ALU = 8，P E = 2，P EC = 4におけるcomplexity毎の探索解発見率を結 果を示した．
P E = 2では，complexityの値に関わらず，ごく短時間に解を得ることができるという結果
が得られた．これにより，ALU = 8，P E = 2，P EC = 4のパイプライン型アーキテクチャ
では，complexityを考慮せずに探索を行える事が分かった．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time （秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.35 複雑度検証(PE=4)
図5.35では，ALU = 8，P E = 4，P EC = 4におけるcomplexity毎の探索解発見率を結 果を示した．
complexity= 0.00−0.25では，探索開始後のごく短時間でほぼ全ての解探索発見率を得る ことができているが，complexity = 0.25−1.00では，最初の短時間での解発見率が約30%
で共通していたが，その後の1200秒ではcomplexity が低いDAGほど多くの探索解を発見 することができていることがわかる．
これにより，complexity が低いDAGほど短時間で多くの探索解を発見することができる ことがわかった．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time （秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.36 複雑度検証(PE=6)
図5.36では，ALU = 8，P E = 6，P EC = 4におけるcomplexity毎の探索解発見率を結 果を示した．
この結果より，complexity が低い DAG ほど多くの探索解を発見することができてい ることがわかる．complexity = 0.00 − 0.5 では，70% 以上の解発見率が得られている が，complexity = 0.5 以上では探索解発見率の低下が大きくなる．特に，complexity = 0.75−1.00では10%程度しか探索解発見率を得ることができないことができる．
これにより，complexity が高い DAG は 1200 秒でほとんど探索解を得られない事が分 かった．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time （秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.37 複雑度検証(PE=8)
図5.37では，ALU = 8，P E = 8，P EC = 4におけるcomplexity毎の探索解発見率を結 果を示した．
この結果より，complexity が低い DAG ほど多くの探索解を発見することができている ことがわかる．complexity = 0.00− 0.5 では，80% 以上の解発見率が得られているが，
complexity = 0.5以上では探索解発見率が著しく低下し，30%以下となる．
これにより，complexityが50%以上のDAGは1200秒でほとんど探索解を得られない事 が分かった．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time （秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.38 複雑度検証(PE=10)
図5.38では，ALU = 8，P E = 10，P EC = 4におけるcomplexity毎の探索解発見率を 結果を示した．
P E = 6,8の場合と同様に，complexity が低いDAGほど多くの探索解を発見することが できていることがわかる．しかし，complexity = 0.50−0.75において，P E = 8ほどの解 発見率の差は見られない．これは，パイプライン段数が増えることで配置配線の自由度が向上 し，complexityの影響が緩和されたためだと考えられる．
最後に，P EC = 2,4,8,16に関するComplexityの検証を行ったものを，それぞれ図5.39， 図5.40，図5.41，図5.42に示す．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time （秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.39 複雑度検証(PEC=2)
図5.39では，ALU = 8，P E = 4，P EC = 2におけるcomplexity毎の探索解発見率を結 果を示した．
P EC = 2では，complexityの値に関わらず，ごく短時間に解を得ることができるという
結果が得られた．これにより，ALU = 8，P E = 4，P EC = 2のパイプライン型アーキテク チャでは，complexityを考慮せずに探索を行える事が分かった．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.40 複雑度検証(PEC=4)
図5.40では，ALU = 8，P E = 4，P EC = 4におけるcomplexity毎の探索解発見率を結 果を示した．
P EC = 4では，complexityが低いDAGほど多くの探索解を発見することができ，いずれ の場合も40%以上の探索解発見率を得ることができた．これは，配線パターン数の増加によ り配置配線の自由度が上がり，DAGのcomplexity増加の影響が緩和されたためだと考えら れる．
これにより，ALU = 8，P E = 4，P EC = 4 のパイプライン型アーキテクチャでは，
complexityが高くなっても探索解の発見率の低下が抑えられる事が分かった．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time （秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.41 複雑度検証(PEC=8)
図5.41では，ALU = 8，P E = 4，P EC = 8におけるcomplexity毎の探索解発見率を結 果を示した．
P EC = 8 では，complexity が低い DAGほど多くの探索解を発見することができるが，
complexity = 0.75−1.00では解発見率が20%程度に低下してしまう．これは，配線パター ン数の増加により探索範囲が増大し，配置配線自由度の向上が打ち消されてしまうためだと考 えられる．
これにより，ALU = 8，P E = 4，P EC = 8 のパイプライン型アーキテクチャでは，
complexityが高いDAGは探索解が発見出来なくなるケースが増える事が分かった．
0 10 20 30 40 50 60 70 80 90 100
0 200 400 600 800 1000 1200
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time （秒） （秒） （秒） （秒）
COMP0.00_0.25 COMP0.25_0.50 COMP0.50_0.75 COMP0.75_1.00
図5.42 複雑度検証(PEC=16)
図5.42では，ALU = 8，P E = 4，P EC = 16におけるcomplexity毎の探索解発見率を 結果を示した．
P EC = 16では，complexity が低いDAGほど多くの探索解を発見することができるが，
P EC = 8と比較してcomplexity = 0.00−0.25においても探索解の発見が遅くなる傾向が みられる．これは，P EC = 8以上に探索領域が増大し，探索時間1200秒以内に探索解を得 られないためである．
以上のALU，P E，P ECのパラメータを変動させた全てグラフ結果より，Complexityが低 いものほどマッピング探索解の発見率が高いことがわかる．特に，0.00< Complexity ≤0.25 は1200秒内にすべてのDAGに対してマッピング探索解を得ることができている．一方で，
0.75 < Complexity≤ 1.00では，ほとんどのDAGに対して，マッピング探索解を得られて いない．このことから，ALU, P E, P EC の値に関わらず，Complexity が低いDAGにおい ては，マッピング探索解が得やすいために一定以上の発見率を保っていることが判明した．つ まり，図5.29や図5.30においてDAGのマッピング探索解の発見数がP E, P EC 値の増大に
表5.5 Search Node SelectionによるPE削減数
Complexity 0-0.25 0.25-0.5 0.5-0.75 0.75-1 Reduced PEs 3.52 0.24 0.04 0
比例しないのは，テストセットにComplexityが低いDAGが含まれているためである．
さらに，Complexityが低いものについては最初の数秒で多数のDAGのマッピング探索解
を得られていることもわかる．これは，4.2.で説明したSearch Node Selectionによる効果だ と考えられる．そこで，Complexity毎のDAG集合で，Search Node Selectionによって削減 されたP E の平均を表5.5に示す．先ほどの評価と同様に，ALU = 8，P E = 10，P EC = 4 として評価を行った．
0−0.25は，0.00< complexity ≤0.25となる25個のDAG集合を示す．その他について も同様である．Complexityの集合の下には，集合におけるPE 数の平均削減数が示されてい る．これにより，Complexityが低いものほど，多くのDAGノードを探索領域から枝刈りし ていることがわかる．つまり，Complexityの低いDAGは探索の必要のないノードが多いた
め，Search Node Selectionによって探索領域が削減され，その結果探索時間が大幅に削減さ
れた．
5.5.3 スケーラビリティ評価のまとめ
以上の結果より，提案手法はP E，P EC のパラメータに対して、性能の変動が少ないこと が分かった．ALU については値を増加させた結果，性能低下が発生したが，ALU = 2,4,8 については高い解発見率が得られることが示された．さらに，マッピング探索解を得られた DAG の大半が最初のわずかな時間で，マッピング探索解を得られていることもグラフから 読み取れる．Complexityによる評価により，パイプライン型アーキテクチャのパラメータ値 (ALU, P E, P EC)が増えたとしても，Complexityの低いDAGに対してはマッピング探索 解を得やすいことも判明した．
Complexityについては，実際のアプリケーションを用いた調査も行った．調査したアプリ
ケーションは，2G規格のGSM，動画圧縮規格H.264と無線LAN規格802.11nの3つあり，
それぞれパイプライン処理が有効な処理部分を抽出し，適切なDAG分割をした上で各DAG
のComplexityを調べた．GSMでは，全てのDAGのcomplexityが0.25以下と，非常に低 いComplexityとなった．H.264では，89%のDAGがcomplexity 0.25以下であり，残りの 11%もcomplexity 0.25以上0.5以下の範囲にあり，これもComplexityが低い傾向にあるこ とがわかった．802.11nについては，complexity0.25 以下が88%，complexity0.25以上0.5 以下が6%，complexity0.5以上0.75以下が6%となり，95%のDAGが低いcomplexityを 示していることがわかった．ただし，この複雑度の範囲においても，表5.1, 表5.2, 表5.3に 示したように，SAではほとんど解が得られない．
また，Complexityが高いDAGにおいて解が得られない場合にも，クラスタリングにおい
てパイプライン段数を削減する等，Complexityが低くなる処理分割をすることで，マッピン グ探索解を得やすくなることが分かった．これは，処理分割によってDAGのノード数とエッ ジ数が削減され，結果としてComplexityが下がり，Complexity毎の解発見率を評価した図 5.38のように，マッピング探索解の発見率が向上するためである．