パイプライン処理１
現在、CSの勉強のために、コンピュータアーキテクチャ (電子情報通信レクチャーシリーズ)を読んでいる。
これまで上記のような制御ブロック図で一つの命令がどのように実行されるかを考えてきた。今回は、複数の命令を少しずつずらして同時並行的に実行する、流れ作業のようなパイプライン処理をみていく。
パイプライン処理とは
パイプラインとは、全体の作業を多数の工程に分割し、各工程（ステージ）を並列に処理することで、単位時間あたりの処理量（スループット）を飛躍的に向上させる流れ作業のことである。パイプラインでは全体の作業の実行時間（各工程の作業時間の合計）自体を短くすることはできないが、一連の作業が複数あれば、スループットの向上により一連の作業の全体の時間を短縮することができる。
1~4工程で終わる自動車製造の作業がある、1工程の長さを1時間と仮定する。
一人で全ての工程をこなした場合、1工程ずつしか実施できないので、3台の自動車を製造するまでに要する時間は12時間となる。
次に、4人で協力して各工程を一人が担当し、流れ作業で実施した場合、3台の自動車を製造するまでに要する時間は6時間となる。
流れ作業にすることで、半分の時間で同じ作業を実施することができる。当たり前と言えば、当たり前で日常的に様々な場所で流れ作業（分業）が行われ、効率化が図られている。
命令の実行パイプライン処理
コンピュータの処理もパイプライン化することで処理の効率を飛躍的に高めることができる。コンピュータでは、様々な命令を実行することが作業となる。MIPSの命令は、下記の5ステップを要する。
- 命令フェッチ（Instruction Fetch：IF）
- メモリから命令をフェッチする
- 命令デコードとレジスタフェッチ（Instruction Decode：ID）
- 命令実行・アドレス生成（Execution：EX）
- 命令操作の実行
- 分岐の場合、PC書き換え、アドレスの生成を行う
- メモリアクセス（Memory access：MEM）
- データ・メモリ中のオペランドにアクセスする（メモリへの読み書き）
- 書き込み（Write Back：WB）
- メモリからのデータ（結果）をレジスタに書き込む
よって、MIPSのパイプラインは5ステージからなる。1クロック・サイクルの間に命令が最大5つ実行されている。
次に、単一クロックサイクルのデータパスを以下に示す。各ステージごとに分割して表示している。
命令の各ステップは左から右の順でデータが流れている。しかしながら、下記の2つだけは例外がある。
- WBステージにおいて、ALU結果・メモリから読み出されたデータがそれぞれ左側へ送られ、レジスタに書き込まれる
- PC更新時に、PC+4または、EXステージで生成された分岐アドレスのいずれかが選択される
右から左に流れるデータは、現在実行されている命令に影響を与えない。しかしながら、パイプラインを後から流れてくる命令に、この例外的なデータの動きが影響を与えてしまう可能性がある。
実際のハードウェアでは、ステージの間がただの結線だと、前のステージの処理の影響が直ちに後のステージの処理に及ぶため、正しいパイプライン動作が行われない。例えば、
- 命令1が、WB（書き込み）ステージ
- 命令2が、MEM（メモリアクセス）ステージ
- 命令3が、EX（命令実行）ステージ
- 命令4が、ID（命令デコード）ステージ
の場合を考える。データ線と制御線が直接接続されていた場合、ID（命令デコード）ステージの命令4のデータが、命令3を実行中のALUの入力線に流れ込むことになり、意図した動作をしなくなってしまう。
これを防ぐために、各ステージの間にレジスタを設け、各ステージ間のデータ・制御の受け渡しを行うようにする。全てのレジスタは、一つのクロックに同期して動作するとする。このようなレジスタをパイプラインレジスタ（pipeline register）と呼ぶ。また、IFステージとIDステージとの間のレジスタは、「IF/ID」と呼ぶ。
パイプラインの阻害要因
パイプライン処理においては、いくつかの阻害要因があり、1クロック1命令のスループットを達成するには様々な工夫が必要である。まずは、阻害要因を以下に列挙する。
オーバーヘッド
本来の処理では存在しなかった、制御上付加された余計な時間のことをオーバーヘッド（overhead）と呼ぶ。
各ステージの処理時間は、処理内容が異なるため、実際にはばらつきがある。そのため、最も時間のかかるステージの処理時間で全体のスループットが決まってしまう。対策としては、出来るだけ各ステージの処理時間の長さを合わせることである。もし長すぎるステージがあれば分割し、短すぎるステージ同士は結合する。
上記にてパイプライン処理を実現するために、パイプラインレジスタを追加した。パイプラインレジスタの読み書きによる遅延も無視することができない。パイプラインのステージ数が増えるほど、相対的にレジスタによるオーバーヘッドが大きくなってしまう。対策としては、出来るだけ高速なレジスタを使うことであるが、限度がある。
ハザード
命令をクロックごとにパイプライン動作させられない状態をパイプラインハザード（pipeline hazard）または単にハザード（hazard）と呼ぶ。そして、ハザードには、構造ハザード、データハザード、制御ハザードの3種類がある。また、ハザードによって命令の実行が止められる状態をストール（stall）と呼ぶ。
構造ハザード
構造ハザード（structual hazard）は、同時に実行される命令の組み合わせにハードウェアが対応できないために、命令を所定のクロックサイクルで実行できない事態が発生することである。
命令メモリとデータメモリを分けることができず、統合メモリを使った場合を考える。同一クロック・サイクルにおいて、最初の命令がメモリのデータにアクセセスしている時に、命令3が同じメモリから命令をフェッチしようとした場合、最初の命令がメモリを占有しているため、命令3は命令をフェッチできない。そのため、命令3を1クロック実行待ちの状態とし、1クロック遅らせる必要がある。
対策としては、資源の多重化によって解決が可能である。上記の場合、命令メモリとデータメモリを別々のものとし、それらのメモリにアクセスするための制御線やデータ線をそれぞれ独立させておく。ただし、コストが高くなってしまうので、コストと性能のトレードオフを考える必要がある。
メモリを分離するのはコストが高く現実的ではないが、キャッシュの分離は可能なので、実際には命令キャッシュとデータキャッシュを独立して設けて、メモリに関する構造ハザードの問題を解決している。
データハザード
データハザード（data hazard）は、命令の実行に必要なデータがまだ利用可能になっていないために、予定している命令を実行できない状況が発生することである。
命令間の依存関係の一つがデータ依存である。データ依存は、命令Aで生成されるデータが命令Bで使われる、というような生産者ー消費者（producer-consumer）の関係のことである。命令Aと命令Bの間に十分な時間があって、両者がパイプライン上に同時に存在しない場合は問題ない。しかしながら、データ依存のある2命令が接近している場合にストールが発生してしまう。
WBステージでレジスタに書き込みが行われるため、バブルを追加しない場合、$s1や$s2の演算結果を取得できず、演算前に格納されていたデータを読み出してしまうことになる。3つの命令の実行は本来7クロックで終了するが、上記では13クロックと約2倍になっており、スループットは約半分になってしまう。
5ステージでの命令パイプラインの場合、4命令以上離れた命令の間ではデータハザードは起こらない。
制御ハザード（分岐ハザード）
制御ハザード（control hazard）は、分岐ハザードとも呼ばれ、分岐命令が原因で次に実行する命令の確定ができないことから発生する。条件分岐で実行の流れが二つに分かれる場合、条件の評価を待たずに先行して片方の分岐の命令群をパイプラインに投入することになる。そして条件を評価した結果もう一方に分岐することが確定した場合、パイプラインの内容を破棄して正しい分岐の命令群を投入しなおさなければならない。
分岐するかの判定は、MEMステージに至るまで決定されない。分岐が完了するまでストールさせては速度が遅くなりすぎるので分岐が不成立と予測して、後続の命令の実行を継続させる。分岐が成立した場合に、フェッチおよびデコードを進めていた命令を破棄し、分岐先の命令から処理を続行する。
もし分岐先が決定するまでストールさせる場合、3クロック分ストールさせることになる。
まとめ
今回は、パイプライン処理の概要とその阻害要因を確認することができた。次回、阻害要因の詳細とどのように対策すべきか確認していく。
