Crusoeの未来について考える(部分最適化編)





さて、では前回の予告通りCMSのアルゴリズムを変更して、 繰り返し頻度の高い部分のみを最適化する方法としてみよう。 これは、前回のプログラムを下記の2つに分解する事で行う。

1.ループ部分は前回同様、VLIWによる並列処理を目指す。
2.非ループ部分は、あえて逐次実行とする。


では、前回同様に処理時間を計算してみよう。


○第一ステップ:命令の翻訳   
x86-atom変換は今回も前回と同じなので割愛する。 ループ部分だろうが、非ループであろうが、置換を行わないと、 VLIWは処理を行えないからだ。と言うわけで、変換は全体を一括で行ってしまおう。

1.命令翻訳の処理時間=プログラム長/単位時間当たりの変換能力 =10Xサイクル


○第二ステップ:ループ部分の並列実行命令抽出   
まず並列性の抽出部分は下記の通りになる。 ループ部分の長さは、全コードの10%であることに注目して欲しい。

2.同時実行命令のパック処理時間=χ×(n(nー1)/2)×(2X/n)

並列性の抽出作業はループ回数に関わらず1回で済むのがミソである。


○第三ステップ:パックしたVLIW命令の実行   
VLIW命令にパックされた部分の処理を行う。この部分は、並列性の抽出と異なり、 ループ回数分だけ繰り返し実行されなければならない。つまり処理時間は 下記の通りとなる。

3.VLIW命令処理時間=逐次処理時間/平均並列実行命令数 =162X/(1+(n−1)η)


○第四ステップ:残された逐次命令の実行   
非ループ部分の処理である。この場合はatom1個を1パックのVLIW命令と見立てて、 残りの3atomにはNOP(何も処理しないで次へ行けという命令)を入れる。 つまり、まったく高速化に寄与しない逐次処理を行う事となる。

4.VLIW命令処理時間=逐次処理時間=18X


●総処理時間   
では、この部分最適化アルゴリズムで処理を行う場合の処理時間は いかほどであろうか?

総処理時間=1.+2.+3.+4. =10X+χ×(n(nー1)/2)×(2X/n) +162X/(1+(n−1)η) +18X

ここで、前回同様、抽出作業の比較検証コスト倍率を実行効率と同じと考えて χ=1と仮定し、また、並列実行命令の出現頻度を50%と仮定して、 η=0.5と仮定してみよう。 すると、最短となる総処理時間は上記の式から下記の通り計算される。

総処理時間=62.25X (n=15 このとき平均並列実行命令数は8atom)

ただし、現状のCrusoeはatomを4つしかパックできない。従って、 最適解は8命令同時実行だが、ここでは涙をのんでn=7つまり4命令同時実行まで デチューンしなければならない。 これはハードウエア・リソースの制約なので、CMSではどうにもできないのである。 そのときの処理時間は下記の通りである。

総処理時間=74.5X (n=7 このとき平均並列実行命令数は4atom)

すべてのコードを最適化するアルゴリズムでの総処理時間は110Xサイクル だったことを思い出して欲しい。 部分的に最適化するというのは、一見すると 手抜きアルゴリズムのように見える。 しかし、それが奏功し、 なんと処理時間が約32%も短縮されたのである。

これは、コードの10%しか最適化しなかったために、 並列性抽出処理に時間を取られなかったと言うことと、 命令ウインドウのエントリ数nが5から7に引き上げられた結果、 平均並列実行命令数が3から4に増えたこととの 相乗効果による。

nとχを振ってグラフにしてみた。ηは50%固定である。 大ざっぱなタコ解析編で示した、全コード最適化の場合と比較して、その威力を確認して欲しい。



このグラフ、相対値は当てになるが、PentiumIII比の絶対値は あまり当てにはならない。 であるが、とりあえずこれを信用すると、Crusoeのコア性能は 大雑把に言ってPentiumIIIの約67%となった。

公称値はPentiumIII比で80%の処理能力である。この差は、(誤差の他に)まだまだ、 たるさんには解明できない多くのワザがCMSに秘められているということだろう。

次回は、この式から次世代Crusoeの将来像について予想してみたい。(続く)

(補足)
今回計算したこの近似だけど、平均並列実行命令数が実際のVLIW命令の パック数に近くなればなるほど誤差が大きくなる。 それは、計算された並列命令数はあくまで平均であって、 実際にはある一瞬だけ見ると増えたり減ったり、ゆらいでいるからだ。 申し訳ないのだが、この点だけは注意して読んでいただきたい。

「平均並列実行命令数<パック数」ならば、ゆらぎが発生しても近似誤差は少ない。 プラスとマイナスがうち消すからだ。

しかし、「平均並列実行命令数=パック数」となると誤差が大きくなる。 平均からのズレの内、プラス分はパックしきれずに 次のVLIW命令に繰り越される事になるからだ。

この場合、命令の相互依存関係から次のVLIW中のatomがパック数上限 よりも少なくても、そこに余った命令を組み込むわけにはゆかなくなる。 つまり、近似値よりも遅くなってしまうのである。

命令数のゆらぎを正しく評価する事はアマチュアには難しい。 従って、今回のこの値は理論限界として扱った方が良いかもしれない。