パイプライン処理２
現在、CSの勉強のために、コンピュータアーキテクチャ (電子情報通信レクチャーシリーズ)を読んでいる。
前回に引き続き、パイプラン処理についてまとめていく。今回は、データハザードと制御ハザードに対して、どのように対応すべきか確認する。
フォワーディング
パイプライン処理では、直前の命令の結果がレジスタに書き込まれる前に、後続の命令がレジスタの読み出しを行い、命令間にデータの依存性がある場合、更新前の意図していないデータを読み出してしまう。これを書き込む前に読み出してしまうことから、RAW（Read After Write）ハザードと呼ぶ。
RAWハザードを解消するためには、EXステージでの演算結果を、WBステージを経ることなく、次の命令のEXステージの入力としてデータの受け渡しを実現するできればいい。このように本来なら後になるデータの受け渡しを内部資源から先送りするハードウェアを追加することを、フォワーディング（forwarding）またはバイパシング（bypassing）、ショートカット（short cut）と呼ぶ。
以下の命令群を例として、RAWハザードを考える。
sub $s2, $s1, $s3 # デスティネーションレジスタrd($s2)にsubの演算結果を設定 and $t0, $s2, $s4 # 第一オペランドrs($s2)にsubの演算結果を設定 or $t1, $s5, $s2 # 第二オペランドrt($s2)にsubの演算結果を設定 add $t2, $s2, $s2 # ハザードは存在しない sw $t3, 100($s2) # ハザードは存在しない
パイプライン・レジスタのフィールド名による依存関係を明確にすると、RAWハザードが発生する条件は以下の2種類である。
- EX/MEM.RegisterRd == ID/EX.RegisterRs or ID/EX.RegisterRt
- MEM/WB.RegisterRd == ID/EX.RegisterRs or ID/EX.RegisterRt
ただし、命令の中にはレジスタに書き込みを行わないものもあり、不必要にフォワーディングを行ってしまう場合が発生する。そのため、解決策の一つとして、制御信号線のRegWrite信号（レジスタの書き込み信号）が設定されているかを確認する対策がある。
以上のことより、フォワーディング機構を追加した命令パイプラインは以下のようになる。新規に追加した部分がわかりやすいように、データ線は赤色、制御線を緑色とする。
ALUの入力にマルチプレクサ（MUX）を追加して、ID/EXパイプラインレジスタだけでなく、EX/MEMパイプラインレジスタ、MEM/WBパイプラインレジスタから取り出せるようにすることで、任意のデータをフォワーディングすることができる。
フォワーディングの制御回路はEXステージに置かれる。そして、フォワーディングを行うかの判定には、ID/EX.RegisterRsとID/EX.RegisterRtが必要なので、ID/EXレジスタに追加している。
ハザード検出ユニット
データハザードに関して、フォワーディングで解決することができない場合が1つある。それは、ロード命令が書き込むのと同じレジスタを直後の命令が読み出そうとする場合である。
ロード命令がメモリからデータを読み出している最中に、次の命令ではALUでの演算が行われしまっている。そのため、ロード命令とその結果を読み出す次命令との組み合わせに対しては、パイプラインをストールさせなければならない。そこで、「ハザード検出ユニット」を追加する。ハザード検出ユニットはIDステージで動作し、ロード命令とその結果を使用する命令との間にストールを挿入する。
ストールを挿入する条件は以下を同時に満たした場合である。
- ID/EX.MemRead == 1
- ID/EX.RegisterRt == IF/ID.RegisterRs or ID/EX.RegisterRt == IF/ID.RegisterRt
IDステージ上の命令をストールさせる場合、IFステージ上の命令もストールしないと、フェッチした命令が失われてしまう。この2つの命令の進行を止めるために、PCレジスタとIF/IDパイプライン・レジスタび両方を変更しないようにする。これらのレジスタが保持されている限り、IFステージの命令は同じPCから読み出すことができ、IDステージもIF/IDパイプライン・レジスタ中に保持されている同じ命令を使用して読み出すことができる。
EXステージ以降の部分では、何もしない命令（nop）を実行する必要がある。nop命令をパイプラインに挿入する場合、EX, MEM, WBの各ステージの制御信号を全て「0」にする必要がある。制御値が全て「0」の場合、レジスタにもメモリにも書き込みが行われない。
よって、ハザード検出ユニットを追加した命令パイプラインは以下のようになる。新規に追加した部分がわかりやすいように、データ線は赤色、制御線を緑色とする。
ハザード検出ユニットは、PCおよびIF/IDパイプライン・レジスタへの書き込みを制御するとともに、制御値のマルチプレクサ（MUX）を制御する。
命令アドレス生成 MEM→IDに変更
制御ハザードに関して、分岐の判定が完了するまでストールさせていては遅くなりすぎるため、改善策として分岐が不成立すると予測して、後続命令の実行を継続する方法がある。しかしながら、命令が成立した場合、途中まで進めた命令を破棄する必要がある。命令を破棄するには、制御値を全て「0」にすればいい。MEMステージで分岐命令先が確定した後に後続命令を破棄するためには、IF, ID, EXの各ステージ上の命令の制御値を変更する必要がある。先ほどのハザード検出ユニットでは、IDステージの制御値を「0」にして伝播させるだけでよかったが、命令を破棄する場合、パイプラインのIF, ID, EXの各ステージ上の命令を一括消去、すなわちフラッシュ（flush）する必要がある。
分岐の性能を改善する1つの方法は、成立した分岐のコストを下げることである。これまで分岐用の次の次PC値はMEMEステージで取り上げるものと想定してきた。しかしながら、分岐の実行をパイプラインの早いステージに移動することができれば、フラッシュすべき命令数を減らすことができる。
分岐判定を前倒しにするには、分岐先アドレスの計算と分岐判定の評価という2つの処理を早く開始する必要がある。MEMステージからIDステージに変更することで、分岐が成立した場合にもバブルは1つしか発生しないことになる。ただし、IDステージで2つのレジスタを読み出して比較するためにはフォワーディングやハザード検出の回路の追加が必要となる。
次の例の場合、IDステージで比較をする場合、フォワーディングを追加する必要がある。
また次の例の場合、分岐命令の直前のALU命令によって比較のオペランドが算出されるので、EX/MEMのフォワーディングを追加したとしても、ストールが必要である。
さらに、次のようにロード命令の直後に、そのロード結果に基づく条件分岐命令がある場合、2サイクルのストールが必要となる。
よって、命令アドレス生成をMEM→IDに変更し、フォワーディング機構やハザードの検出を追加した命令パイプラインは以下のようになる。
条件が成立した場合に、IFステージ上の命令をフラッシュするための制御線IF.Flashを追加している。この制御線によりIF/IDパイプライン・レジスタの命令フィールドを「0」にクリアする。レジスタをクリアすると、フェッチした命令は何も行わず何も状態を変えないnop命令に変換される。
動的分岐予測
これまで「常に分岐が成立しないと予測」する方式で説明してきた。分岐予測が外れた場合に、パイプラインのステージが増えれば増えるほど、分岐ペナルティは大きくなってしまう。
動的な分岐予測として、2ビット予測器がよく知られている。2ビット予測器の原理は、各分岐命令が2回続けて分岐するか、2回続けて分岐しなかった場合に予測を変える、というものである。
遅延分岐
条件分岐命令で、分岐をしてもしなくても直後に同じ命令を実行すると仮定する。
- 分岐の有無に関わりなく実行する命令（共通命令）を分岐命令の次のアドレス（遅延スロット、deyaled slot）に入れておく。
- 遅延分岐命令は定められた数の共通命令をパイプライン実行した後でPCをセットする。
これによって、もし共通命令が十分な数あれば、分岐によるストールをなくすことができる。
命令スケジューリング
ハザードの解消をソフトウェア的に行うことも重要な技術である。依存関係のある命令をプログラムの中でできるだけ離した位置におくようにすれば、ハザードが起こりにくい。一般に命令の位置を最適化することを命令スケジューリング（instructon scheduling）という。命令スケジューリングはコンパイラが行う。
まとめ
データハザードと制御ハザードを解消するための手法を整理することができた。また、データハザードと制御ハザードの対策を追加して、命令パイプラインを漸く最終形まで持っていくことができた。
