並列処理（2）静的最適化

コンピューターの性能向上には、並列処理が必要不可欠である。前回に引き続き、静的最適化に関してまとめていく。静的最適化（static optimization）とは、プロセッサを効率良く動かすために、あらかじめ機械語プログラムを最適化することを指す。一般的にはコンパイラで行われる。

機械語プログラムと命令間依存性

ハザードを出来るだけ減らすためにコンパイラができることとして、以下が挙げられる。

依存関係を解消したり減らしたりする
- ループアンローリング
  - 複数のループを統合して1つのループにすることで、分岐命令によるハザードをなくす手法
- トレーススケジューリング
  - 分岐予測をして複数の基本ブロックを統合し、制御依存を減らす手法
依存関係のある命令どうしをプログラムの中で離れた位置に置く
- ソフトウェアパイプライニング
  - ループ間にまたがって命令を移動し、依存関係のある命令どうしの距離を離すことでハザードを起こりにくくする手法

但し、上記はプログラムの意味を変えない範囲で行わなければならない。

例として、配列aのすべての要素に5を加えるプログラムを考える。

for (i=0; i < 100; i++) {
  a[i] = a[i] + 5;
}

これをコンパイルすると、以下のアセンブリ言語を得る。

上記のプログラムにおいて、blt r1, r2, ForLoopの分岐命令で制御ハザードが発生する。分岐命令があるたびに、3クロックのストールが生じてしまう。また、並列処理を行う場合には、分岐命令をまたぐ並列化は通常行われない。

但し、今回のループにおいて、if (r1 < r2)はr1を1ずつインクリメントしているだけのため、r1=100になる最後以外は分岐予測（常に分岐しないと予測）が100%当たるため、制御ハザード解消のために分岐予測を行う。

ループ1周は、9クロックで実行される。

ループアンローリングは、複数のループを統合して1つのループにすることで、分岐命令によるハザードをなくす手法である。今回の場合、100回のループを4つのループにまとめて1つにする。アセンブリ言語は以下の通りである。

パイプラインは以下の通りである。

ループ４周分で13クロックで実行される。

先ほどの分岐予測の場合と比較して、9クロック×4周=36クロックとなるため、36 / 13 = 2.77倍の性能が出ている。

ソフトウェアパイプライニングは、ループ間にまたがって命令を移動し、依存関係のある命令どうしの距離を離すことでハザードを起こりにくくする手法である。また、ソフトウェアパイプライニングとループアンローリングは組み合わせて用いることができる。

今回においては、ループの最初で依存関係のある命令が連続している。

この部分をループをまたがって処理できるように移動させる。すなわち、ループの中ではa[i]に計算済みの値を代入し、次のループi+1番目の計算を行うようにする。以下のようなプログラムになる。

アセンブリ言語は以下の通りである。

パイプラインは以下の通りである。

ループ1周は、8クロックで実行される。

先ほどの分岐予測の場合と比較して、9 / 8 = 1.13倍の性能が出ている。

ソフトウェアパイプライニングによる効率改善の理由

トレーススケジューリングは、分岐予測をして複数の基本ブロックを統合し、制御依存を減らす手法である。

トレーススケジューリングの手順

実行履歴（プロファイル / profile）などによって、実行される確率の最も高い分岐パターンを調べる。
(1)のパターンの上にある基本ブロックを統合する。これをトレース（trace）と呼ぶ。
トレースに命令スケジューリングを施すことで、トレース内の実行効率を高める。トレース内にも分岐命令はあるが、「分岐命令を超えた命令移動」も行う。
(3)によってトレース以外に分岐する場合に生じる不都合を防ぐため、分岐先の入り口に補正用のコードを入れる。これをブックキーピング（bookkeeping）と呼ぶ。
トレースを除いた制御フローグラフにおいて、(1)～(4)を繰り返す。

今回の配列のループにおいては、条件分岐が複数あるわけではないので、トレーススケジューリングを用いることはできない。