Search Nodes Non-Search Nodes
5.4 枝刈り手法評価
5.4.2 Search Direction Decision 評価
以上の全ての結果より，計算時間が悪化したケースについては，枝刈りにより探索パター ンの生成順序が変更され，計算時間が長くなったものと考えられる．機能の特徴としては，
complexityの低いものは機能の有無にかかわらず，計算時間が短く，complexityの高いもの
は，機能が有効なサンプル数は少なくなるが，有効なサンプルについては時間短縮が見られる．
中間のcomplexityのものは，多くのケースで機能が有効に働き，大幅な時間短縮に繋がった．
以上の結果から，Search Nodes Selectionの手法を導入することで，マッピング探索解をよ り早く発見できることが判明した．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能 ON(PE = 2) 機能 OFF(PE = 2)
図5.18 Search Direction Decision機能検証（PE = 2，手法OFF-Bottom-）
図5.18では，P E = 2において，手法を有効にした場合と手法を無効にしBottom(下)か らのみ探索を行った場合とを比較した．機能を有効にした場合も無効にした場合もどちらも短 時間で全ての探索解を得られていることから，ほとんど差は見られない．
このことから，P E = 2においては，機能が有効であるかどうかは可視できない．
なお，機能OFFと機能ONの結果が重なっているため，図の表示がされていないことに注 意されたい．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能 ON(PE = 2) 機能 OFF(PE = 2)
図5.19 Search Direction Decision機能検証（PE = 2，手法OFF-Top-）
図5.19では，P E = 2において，手法を有効にした場合と手法を無効にしTop(上)からの み探索を行った場合とを比較した．その結果，図5.19と同様に，機能を有効にした場合も無効 にした場合もどちらも短時間で全ての探索解を得られた．つまり，P E = 2においては，Top のみBottomのみからの探索とSearch Direction Decision機能を有効にした場合の差が無い 事が分かる．これは，探索領域が小さいため，機能の有効無効に関わらず短時間で探索が完了 するためである．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能ON(PE = 4) 機能OFF(PE = 4)
図5.20 Search Direction Decision機能検証（PE = 4，手法OFF-Bottom-）
図5.20では，P E = 4において，手法を有効にした場合と手法を無効にしBottom(下)か らのみ探索を行った場合とを比較した．
この結果より，探索開始直後に発見される解発見率の差は小さいが，手法を有効にした場合 では，その後の600秒で早期に探索解が得られていることが分かる．これは，探索に時間が かかるDAGが，正しい探索方法を得たことで探索時間が短縮したものと考えられる．そのた め，十分に時間をとった場合手法OFFでも600秒以内に解が得られるケースも多く，最終的 な手法ONとOFFの差は小さくなっていることが分かる．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能 ON(PE = 4) 機能OFF(PE = 4)
図5.21 Search Direction Decision機能検証（PE = 4，手法OFF-Top-）
図5.21では，P E = 4において，手法を有効にした場合と手法を無効にしTop(上)からの み探索を行った場合とを比較した．図5.20との比較と同様に，P E = 4では，0秒から200秒 での発見率に違いがあり，Search Direction Decision機能をON にした場合に短時間で解発 見率を発見する事ができる．また，TopからのみとBottomからのみ探索する場合とではあま り差がない事が分かる．
次に，図5.23 と図5.22 は，Search Direction Decision 機能を ON にした場合と，OFF
（Topのみ，Bottomのみ）を比較した結果を示す．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能 ON(PE = 6) 機能OFF(PE = 6)
図5.22 Search Direction Decision機能検証（PE = 6，手法OFF-Bottom-）
図5.22では，P E = 6において，手法を有効にした場合と手法を無効にしBottom(下)か らのみ探索を行った場合とを比較した．
P E = 4の場合と同様に，探索開始直後に発見される解発見率の差は小さいが，手法を有効 にした場合では，その後の600秒で早期に探索解が得られていることが分かる．P E = 4との 違いは，手法OFFの場合において，探索空間が拡大するために600秒では探索解を得られな いケースが増えるためである．これらの探索解を得られないDAG が，手法ONの場合では 600秒以内に解を得られることから，600秒時点での解発見率に10%程の相模られっると考 えられる．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能ON(PE = 6) 機能OFF(PE = 6)
図5.23 Search Direction Decision機能検証（PE = 6，手法OFF-Top-）
図5.23では，P E = 6において，手法を有効にした場合と手法を無効にしTop(上)からのみ 探索を行った場合とを比較した．ここでは，図5.22とほぼ同様の結果が得られている．また，
P E = 4よりも探索開始直後の解発見率が低い傾向にあるが，機能のONとOFFとの解発見 率の違いがやや大きくなる．これは，P E = 6では探索範囲が大きくなり，一般的に探索時 間が増えるために，600秒以内という限られた時間内で評価を行った場合，Search Direction
Decisionの効果が大きくなるためだと考えられる．
図5.25と図5.24は，Search Direction Decision機能をONにした場合と，OFF（Topの
み，Bottomのみ）を比較した結果である．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能 ON(PE = 8) 機能 OFF(PE = 8)
図5.24 Search Direction Decision機能検証（PE = 8，手法OFF-Bottom-）
図5.24では，P E = 8において，手法を有効にした場合と手法を無効にしBottom(上)か らのみ探索を行った場合とを比較した．
P E = 8では，0秒直後の探索解の数にあまり差がないが，その後に得られた探索解の数に 違いがある．これは，Search Direction Decision機能によって正しい探索方向が得られ，600 秒以内に解が得られるDAGの数が増えたためだと考えられる．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能 ON(PE = 8) 機能 OFF(PE = 8)
図5.25 Search Direction Decision機能検証（PE = 8，手法OFF-Top-）
図5.25では，P E = 8において，手法を有効にした場合と手法を無効にしTop(上)からの み探索を行った場合とを比較した．
Bottom(下)からのみ探索を行った場合とTop(上)からのみ探索を行った場合では，探索開
始直後や最終的に得られる探索解発見率に差はない．これにより，DAGがBottom探索もし くはTop探索に優位な構造でないことがわかる．
次に，図5.27 と図5.26 は，Search Direction Decision 機能を ON にした場合と，OFF
（Topのみ，Bottomのみ）を比較した結果である．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能 ON(PE = 10) 機能 OFF(PE = 10)
図5.26 Search Direction Decision機能検証（PE = 10，手法OFF-Bottom-）
図5.26では，P E = 10において，手法を有効にした場合と手法を無効にしBottom(下)か らのみ探索を行った場合とを比較した．図5.24の場合と異なり，600秒時点での手法ONと 手法 OFFの解発見率の差が10%に減少している．これは，パイプライン段数が増えたこと で，パイプライン段数のTop からBottomへのパスが多様になり探索自由度が上がったため だと考えられる．つまり，パイプライン段数が増えたことで探索自由度が向上し，探索方向が 最適方向でなくとも探索解を発見できるDAGが増えるためである．
0 10 20 30 40 50 60 70 80 90 100
0 100 200 300 400 500 600
探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率 探 索 解 発 見 率
Time（秒） （秒） （秒） （秒）
機能 ON(PE = 10) 機能 OFF(PE = 10)
図5.27 Search Direction Decision機能検証（PE = 10，手法OFF-Top-）
図5.27では，P E = 10において，手法を有効にした場合と手法を無効にしTop(上)からの み探索を行った場合とを比較した．Bottom(下)からの探索結果と同様に，パイプライン段数 が増えることで配置配線の自由度が向上し，探索方向が最適方向でなくても探索解を発見でき るDAGが増えることで手法のONとOFFでの最終的な解発見率の違いが小さくなった．さ らに，Search Direction Decision では探索を開始する上下1段のパイプラインのみを比較す るため，P E数が増えると予測精度が下がるために，手法のONとOFFでの最終的な解発見 率の違いが小さくなったとも考えられる．
以上のすべてのSearch Direction Decision評価結果をまとめたものを表5.4に示す．
その結果，機能OFF-Top-と機能OFF-Bottom-の結果にはあまり差が無く，機能ON で は，探索した全てのP E で”機能 OFF”と比べて改善が見られた．また機能ONの結果は，” 最適方向”とほぼ同等の結果であるが，パイプライン数P E が増加した場合は，正しい探索方 向が選択できないDAGも発生する．
表5.4 枝刈り手法評価 : Search Direction Decision
探索方向/ PE= 2 4 6 8 10
最適方向Decision 99% 70% 49% 46% 47%
機能ON 99% 69% 49% 46% 42%
機能OFF -Top- 99% 56% 35% 30% 33%
機能OFF -Bottom- 99% 56% 39% 30% 34%
表5.4では，600秒以内に40%以下のDAGがマッピング探索解を得ている．また，この機 能を適用した探索結果は，一方向からのみの探索よりも発見率が高かった．さらに，最適方向 からの探索と比較して遜色がない結果となった．これにより，Search Direction Decisionが マッピング探索解を早期に発見するのに役立つことが分かった．
5.4.3 枝刈り手法評価のまとめ
以上2つの枝刈り手法を評価した結果，様々なパラメータのパイプライン型アーキテクチャ において，枝刈り手法がマッピング探索解の発見率向上と探索時間の短縮に有効であることが 分かった．これにより，短時間で多くのマッピング解を発見可能となった．