P&R 累計所要時間の推定手法

FlexSword^TM に代表されるパイプライン型DRAはパイプライン処理に特化したアーキテ

クチャであるため，開発対象となる処理内でパイプラン処理に適したループ処理部分の実装が 多く行われる．携帯端末機でよく用いられる無線規格802.11nの処理では，ループ内演算数 の平均は1834個となっているため [34]，パイプライン型DRAで処理が大規模なDAGで構

成されることは少ない．そこで，パイプライン型DRA 向けのコンパイラでは約2000ノード のDAGを対象として議論を進める．コンパイラでは，クラスタリングを実行することで，約 2000ノードで構成されたDAG がユニット単位のDAGに分割される．ユニット単位に分割 されたDAGは，それぞれ独立に配置配線を実行することが可能であるため，これは並列化可 能な処理であることが分かる．しかし，配置配線内部の処理は依存関係情報を必要とするた め，並列化実現には工夫が必要となる．そこで，実験で求めたアーキテクチャの構成情報と複 雑度指標complexityを用いて1つの分割DAGのP&Rに要する時間を推定することで，コ ンパイラにおけるP&R処理時間を予測する．

最初に，1つの分割処理における実行時間の期待値を母関数を用いて算出する．なお，P&R の実行時間は本来DAG毎に異なるが，簡単化のため固定値T として考えた．

1回で探索解を発見する確率はpとなり，そのP&Rの実行時間はT となる．2回で探索解 を発見する確率は(1−p)pとなり，そのP&Rの実行時間は2T となる．以下同様である．こ れをパラメータsを用いた母関数E(s)で表現すると，式(5.4)となる．式(5.6)は，式(5.5) の2項以下に内在するE(s)の再帰性を陽に表現している．E(s)に着目して式を変形すると 式(5.7)となる．本式でs = 0とするとE(0) = 1となり，全確率の総和が1となることを示 している．

E(s) =p(1−p)⁰e^{T s}+p(1−p)¹e^{2T s}+· · · (5.4)

=p(1−p)⁰e^{T s}+ (1−p)e^{T s}[p(1−p)⁰e^{T s} +p(1−p)¹e^{2T s}+· · ·] (5.5)

=pe^{T s}+ (1−p)e^{T s}(E(s)) (5.6)

E(s) = pe^{T s}

1−(1−p)e^{T s} (5.7)

次に，期待時間の推定を行う．式(5.4)をsについて偏微分すると，式(5.8)となり，所要 時間の期待値を表現する母関数となる．s = 0と置くと，所要時間の期待値となっていること が分かる．以上より，式(5.9)，式(5.10)，式(5.11)を得る．

E_t(s) =T p(1−p)⁰e^{T s}+ 2T p(1−p)¹e^{2T s}+· · · (5.8)

Et(s) = ∂E(s)

∂s = pT e^{T s}(1−(1−p)e^{T s}) +T(1−p)e^{T s}+pe^{T s}

(1−(1−p)e^{T s})² (5.9)

Et(s) = ∂E(s)

∂s |s=0 = pT(1−(1−p)) +T(1−p)p

p² (5.10)

= T

p (5.11)

以上より，実行時間T における探索解発見率がp のとき，P&R の期待実行時間は ^T_p と なる．

5.6.3 フィードバック機構

本節では，フィードバック機構とFeedback CheckerはP&R実行に先立って実行される．

コンパイラにおけるP&R実行時間を考える場合，P&Rを直列に実行するか並列に実行する かどうかを考慮する必要がある．直列実行の場合は，分割DAG全ての推定時間を加算してい くことで，コンパイルにおけるP&R処理の推定時間が割り出せる．完全並列実行できる環境 では，全ての分割DAGの中で最も推定時間の長いものが，コンパイルにおけるP&R処理の 推定時間となる．

典型作業シナリオを用いてFeedback Checkerの実現方法を以下に示す．

5.6.3.1 典型的作業シナリオ

典型的な例として，ALU 個数が8，PE 数が6，配線パターン数を4を採用したP&R 直 列実行の場合を考える．これらは，FlexSword^TM の適用環境での典型的なパラメータであ る．パイプライン型DRA向けのコンパイラでは約2000ノードのDAGを対象としているこ とから，DRA が保持する演算数(ALU 数×P E 数 = 8∗6 = 48)のうち半分の24個の演 算を使用すると仮定すると，2000/24 = 83.3個程度の分割DAGができる．そこで，シナリ オ1として，クラスタリング後の分割DAGが0.00 < complexity ≤0.25のDAGが35個，

0.25 < complexity ≤ 0.50のDAGが25個，0.50< complexity ≤0.75のDAGが15個，

0.75< complexity ≤1.00のDAGが5個の合計80個のケースを考える．前述のとおり，実 際のアプリケーションでは，complexity が低いDAGの方が compilexityが高い DAGより も数が多いという傾向を反映させている．

5.6.3.2 典型的作業シナリオに対する実行時間の推定

上記で決定した典型的作業シナリオに対して，P&Rの総累計実行時間の推定を行う．最初 に，complexityを用いて1回のP&Rで解を得るまでの実行時間を推定する．さらに，1回の P&R推定実行時間より，全てのP&R累計実行時間を推定する．

実験により得られた図5.44は，complexityと探索時間の関係を表し，横軸を実行時間，縦 軸を時間における探索解発見率としたときの各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.44 複雑度検証(PE=6)

この図より，complexity と P&R 実行時間 T から探索解発見確率 p が得られる．例え ば，complexity が 0.25−0.50 であり T = 200sec のとき，探索解発見確率 p = 0.28 が 得られる．さらに，期待実行時間が ^T_p によって得られるため，T = 200sec，p = 0.28 の とき ^T_p = _0.28²⁰⁰ = 714.2.1sec と算出される．同様に，T = 10,200,600,1200 と変動させ，

complexity を4種類に分類した場合の期待実行時間を算出した結果を表5.6に示す．表 5.6 は，行を4 種類のcomplexityに分類した分割 DAG，列をP&R 実行時間T としたときの，

探索解発見率pと，それによって得られたP&R期待実行時間である．

表5.6 フィードバックによるP&R推定実行時間

実行時間(T)

10 (sec) 200 (sec) 600 (sec) 1200 (sec) COMP0.00 0.25 12.5(p=0.8) 217.3(p=0.92) 631.5(p=0.95) 1200(p=1.0) COMP0.25 0.50 125(p=0.08) 714.2(p=0.28) 1000(p=0.6) 1764.7(p=0.68) COMP0.50 0.75 250(p=0.04) 2500(p=0.08) 1500(p=0.4) 2727.2(p=0.44) COMP0.75 1.00 -(p=0.0) 5000(p=0.04) 12000(p=0.05) 10000(p=0.12)

探索解発見確率pが一定の場合は実行時間T の値を増加させると期待実行時間も増加して いく．しかし，提案するP&Rでは探索時間が長くなるほど探索解発見確率pも上がっていく ため，確率pの上昇率が高い場合は実行時間T の増加に対して期待実行時間が下がる場合があ る．表5.6では，complexity(0.50−0.75)において実行時間T = 200secをT = 600secに変 化させた時，推定実行時間は2500secから1500secになる．つまり，complexity(0.50−0.75) においては，実行時間T = 200secよりもT = 600secを採用することで，探索解を得られ るまでの推定時間が短縮できることを示している．complexity(0.75−1.0)において実行時間 T = 1000secをT = 1200secに変化させた時も同様である．ただし，提案P&R手法は，短 時間での解探索を得られる傾向にあるため，一般的には探索時間は短い方が効率的である．ま た，complexityが0.25−0.50，T = 10secのときは，探索発見確率p= 0.0であるため，推 定実行時間は無限大となり，探索時間を200sec以上にする必要がある．

次に，表5.6を用いてP&Rを直列実行した場合の累計時間の推定を行った．結果を図5.45

に示す．横軸を 1回のP&R における実行時間，縦軸をコンパイラ全体を通してのP&R 累 計実行時間としたときの，Complexity 毎のP&R 累計実行時間を示している．シナリオよ り，complexity(0.00−0.25)のDAG が 35個，complexity(0.25−0.5)のDAG が 25個，

complexity(0.50−0.75)のDAGが15個，complexity(0.75−1.0)のDAGが5個であるた め，図5.45における各complexityはこれらのDAGに対する累計実行時間を示している．

0 40000 80000 120000 160000 200000

10 100 200 400 600 800 1000 1200 P&

R累 計実 行時 間

累計 実行 時間 累計 実行 時間 累計 実行 時間

P&R単独単独単独実行時間単独実行時間実行時間実行時間 (T)

COMP0.75_1.00 COMP0.50_0.75 COMP0.25_0.50 COMP0.00_0.25

図5.45 実行時間(T)毎のP&R累計推定時間（シナリオ1）

これにより，P&R実行時間(T)を指定した場合の，コンパイルにおけるP&R総累計推定 時間を得ることができる．例えば，実行時間 (T)を200secとした場合，コンパイルにおけ るP&R の累計時間は87,965secだと推定される．また，P&R実行時間(T)が低いほど期待 実行時間が低いことから，一般的にはP&R 単体の実行時間を少なくすることで効率的な探 索を行える事が分かる．ただし，complexity(0.75−1.0)ではT = 1000secとT = 1200sec を比較したとき，表 5.6より，T = 1200secを採用した方が単体でのP&R 期待実行時間が 下がるため，P&R総累計時間も減少している．つまり，P&R 総累計実行時間を考えた時，

T = 1000secよりもT = 1200secを採用した方がコンパイラの実行時間を減少させることが

できる．

ここで，シナリオ2として，クラスタリングにおいてユニット毎のノードの充填率を上げ て分割DAG数を減少させた場合を考える．充填率が上がることから，DRAが保持する演算 数(ALU 数×P E 数= 8∗6 = 48)で使用する演算器を24個から演算器の3/4である36個 に増やした場合，ノード数2000sec個より2000/36 = 55.5個程度の分割DAGができる．そ こで，complexity(0.00−0.25)のDAG が5個，complexity(0.25−0.5)のDAG が10個，

complexity(0.50−0.75)のDAGが15個，complexity(0.75−1.0)のDAGが25個の，合 計55個の分割DAGとするシナリオを用いたP&R累計推定時間を算出した．その結果を図 5.46に示す．横軸を1回のP&Rにおける実行時間，縦軸をコンパイラ全体を通してのP&R 累計実行時間としたときの，Complexity毎のP&R累計実行時間を示している．クラスタに

0 40000 80000 120000 160000 200000 240000 280000 320000 360000 400000

10 100 200 400 600 800 1000 1200 P&

R累 計実 行時 間

累計 実行 時間 累計 実行 時間 累計 実行 時間

P&R単独単独単独実行時間単独実行時間実行時間実行時間 (T)

COMP0.75_1.00 COMP0.50_0.75 COMP0.25_0.50 COMP0.00_0.25

図5.46 実行時間(T)毎のP&R累計推定時間（シナリオ2）

おけるノード充填率を上げることで分割DAG 数はシナリオ1の80個から55個に削減され たが，P&Rの総累計時間はいずれのP&R単体実行時間T においても，ノード充填率の低い 最初のシナリオ 1よりも高くなる．T = 800secでは，シナリオ1 のP&R総累計実行時間 129,605secに対し，シナリオ2のP&R総累計実行時間は335,657secと，約2.6倍になる．

総累計実行時間の増加は，P&R単体実行時間が長いcomplexity(0.75−1.0)のDAG数が増 えたことが原因である．これは，シナリオ2のようにノード充填率を上げた場合，分割DAG 数が減るというメリットが得られるが，それにより分割DAGのcompleityが上がりP&R総 累計実行時間の増加することを示している．

5.6.3.3 Feedback CheckerへのP&R実行時間推定グラフの活用法

シナリオ1 とシナリオ2 を用いて，Feedback Checker へのP&R 総累計時間推定グラフ (図5.45，図5.45)の活用方法を示す．

図5.47 Feedback Checker活用フロー

Feedback Checkerでは，図5.47のように，クラスタリングによる分割DAGのComplexity から得られたP&R 推定累計時間とユーザの指定した上限時間を比較し，累計推定時間が指 定された上限時間を超えた場合は，クラスタリングを再実行するフィードバック機構である．

ユーザがP&R単体の実行時間をT = 600sec，P&R累計実行時間の上限を160,000secと指 定した場合，シナリオ2では図5.46より，P&R累計実行時間が320,000sec以上と推定され る．そのため，推定累計時間がユーザの上限値を超えてしまうため，クラスタリングの再実行 を行う．その結果，シナリオ1のようなP&R総累計時間推定グラフが得られたとする．シナ リオ1を用いて，実行時間をT = 600sec，P&R累計実行時間の上限を160,000secと指定し た場合のP&R累計実行時間を図5.45より推定すると，P&R累計実行時間が130,000secで あり，ユーザの設定した上限160,000secよりも短時間で探索が終了すると推定される．この

ように，P&R実行前にユーザの求めるP&R 実行時間に合わせたクラスタリング結果を採用

することが可能になり，コンパイル実行時間の短縮につながる．

また，コンパイルにおけるP&R 全体の上限実行時間をユーザが指定した結果，そこから P&R単体の実行時間 (T)を自動的に算出可能となる．例えば上限時間を120,000secと指定 された場合，シナリオ1では図5.45より，P&R単体の実行時間をT = 400secにすればよ い．これにより，ユーザの指定したP&R累計実行時間の上限から，効果の高いP&R実行時 間を選択することが可能になる．

5.6.3.4 Search Time Checkerへの実行時間推定表の活用法

シナリオ1をベースとして，Search Time CheckerへのP&R実行時間推定表(表5.6)の活 用方法を示す．

Search Time Checkerでは，Feedback Checkerで決定したP&R 単体の実行時間(T)を用 いて，P&Rの探索打ち切り時間を決定する．例えば，Feedback Checkerにおいて実行時間 (T)が600secとなり，complexityが0.25−0.50の分割DAGを配置配線する場合，解が得ら れる推定時間は1,000secである．そこで，Search Time Checkerは，P&R探索が1,000sec を超えた場合，これ以上の探索で解を得られる可能性が低いと判断し，探索を打ち切りクラス タリングの再実行を行う．

Search Time Checkerを導入することで，P&Rの実行時間を推定することが可能となり，

一律で実行時間を設定するP&Rよりも効率的に探索を行うことができる．これにより，結果 的にP&R実行時間の短縮が実現する．

以上より，2つのフィードバック機構を導入することで，コンパイラの性能低下を抑えて，

コンパイル実行時間を短縮することが可能となる．