パイプラインを使ったプロセッサ設計

プロセッサ (CPU) を高速化するには、並列化が重要となります。 並列化技術のうちの1つが「パイプライン(pipeline)」です。

オーバラップとパイプライニング

複数の仕事を同時に実行する方式が「オーバラップ」です。 「パイプライン」とはオーバラップの手法の1つです。

一般に「タスク」は、連続的に実行されるいくつかの 「サブタスク」に分割することができます。 この各サブタスクを、独立して動作する複数の 論理ユニットで別々に実行してゆきます。 「パイプライン」方式においては、あるユニットは i番目のタスク(のサブタスク)を実行した次に (i+1)番目のタスク(のサブタスク)を実行します。

結果の保存....T1T2T3T4T5T6T7T8T9T10T11T12
命令の実行...T1T2T3T4T5T6T7T8T9T10T11T12.
オペランドの用意..T1T2T3T4T5T6T7T8T9T10T11T12..
命令のデコード.T1T2T3T4T5T6T7T8T9T10T11T12...
命令のフェッチT1T2T3T4T5T6T7T8T9T10T11T12....

パイプライン中のデータ転送

命令パイプラインや演算パイプラインでは論理的なタイミングの 問題や実装の問題を少なくするために同期式を通常用います。

性能とコスト

同一の複製ユニットをn台使ってn個のタスクを実行する方法 (図5.4)では、計算は早いのですがコストが非常に高くなります。 これに比べるとパイプラインの方はずっと経済的で、 計算速度もかなり向上します。

nステージのパイプラインに、s個のタスクが渡されると、パイプラインが 最初のタスクを完了するまでに nクロックが必要で、その後全てのタスクを 実行するのに s-1 クロックが必要です。 したがって、必要となるクロック数は Tn = n + (s-1) です。 同等な機能を持つ1個の非パイプラインユニットがs個のタスクを 実行するのに必要な時間は T1 = sn です。

    速度向上率 = T1 / Tn = sn / (n + s - 1)
s→∞とすると、速度向上率→nとなります。

パイプラインでは、タスクが連続的に与えられる定常状態に おいてのみ全てのユニットが動作します。 したがって、始動時と終了時には動かないユニットが存在します。

ti をユニットiの動作時間とおくと効率を次のように表わせます。

    効率 = Σni=1 ti / (n × 全動作時間)
         = sn / n (n + s - 1)
         = s / (n + s - 1)
         = 速度向上率 / n

A と B というユニットをもつ2段のパイプラインを考えます。 もしどちらの処理時間も同じならば図5.5(b)のようになります。 処理する情報によって時間が異なるとすると図5.5(c)のように 空き時間が生じます。 この場合, T(Ai), T(Bi)を それぞれ i番目のAとBの処理時間とすると、全体の 処理時間は以下のようになります。

    処理時間 = Σ(n-1)i=1 Max(T(Ai), T(B(i-1)))

ほとんどの場合は、ユニットの処理時間が固定(同じ)である 同期式パイプラインが好ましいと考えられます。 このために、あるユニットの処理時間が長くなりそうな場合は、 そのユニットの作業を分割しユニットを増やして各ユニットの 処理時間を同じになるように設計します。 これはクロック長を短くする(= 周波数を高くする) ことにも つながります。 もちろん、ユニットを増やすとユニット間で情報が渡される オーバヘッドが大きくなるので性能は上がりにくくなります。 またパイプラインを長くするとデータの依存関係も複雑に なってしまいます。 したがって、パイプラインはあまり長い物は好ましくなく、 長くても20段以下のものが多いようです。 ただ、最近のIntelのプロセッサのようにパイプラインは 長くなる傾向にあるようです。


命令のオーバラップとパイプライン

RISCプロセッサのパイプラインの例

  1. 命令のフェッチ
  2. 命令のデコードおよびレジスタからのオペランドのフェッチ
  3. 命令の実行 --- ALU演算を行うか実効アドレスの計算
  4. 結果書き込み、またはメモリにあるオペランド読み込みのためのメモリアクセス
  5. 結果のレジスタへの格納

パイプラインのハザード

命令やユニット間の相互関係によってパイプラインを停止(stall)しなく てはならない状況が起こります。 これをパイプライン障害(pipeline hazard)と呼びますが、 これには3つの主な原因があります。

リソースの競合

メモリユニットや機能ユニットなどのリソースを複数の命令が同時に 要求したときにリソース競合が起きます。

(例)主記憶の競合
「メモリ・メモリ命令」とは、「ソースとデスティネーションで 共にメモリへのアクセスを必要とするような命令」のことです。 たとえば i486の命令の

    addl   (EBX), (EAX)
は「『EAXが指すメモリ番地』の内容に『EBXが指すメモリ番地』の内容を 加えて結果を『EAXが指すメモリ番地』に書き込む」という動作を行いますが、 これはメモリ・メモリ命令です。 実行時にメモリアクセスでの競合が置きる可能性がありますので RISCでは一般にこのようなメモリ・メモリ命令は用意しない ことになっています。 しかし、命令がメモリ・メモリ命令を含んでいなくてもパイプラインでは メモリアクセスの競合は起こり得ます。 図5.12 の5段パイプラインでは 3つのユニット(命令フェッチユニットが命令を取る、 オペランドフェッチユニットはオペランドを取る、 オペランドストアユニットは結果を書き込む)が競合する 可能性があります。 (i番目の命令がフェッチされ、i-2番目の命令がソースオペランドをフェッチする、 i-4番目の命令が結果を書き込む、などの場合)。

解決策の例

命令フェッチとメモリ内のデータへのアクセスの競合問題の解決例

手続き依存関係と分岐命令

分岐を行うと、パイプラインで処理中の命令を捨てる必要がでてきます。

一般にプログラムの約10〜20%が分岐命令で、分岐命令は 実行速度をかなり低下させる原因になります。

(例)10nsで動作している5段パイプラインで、10命令ごとにパイプライン中の
   全命令が捨てられると、1命令を処理する平均時間は
       (9×10ns + 1×50ns) / 10 = 14ns

改善策

データ依存

ある命令が利用するデータがそれ以前の命令によって生成された データに依存する場合は、命令は指定された順番に実行しなくては いけません。

    ADD    R2, R1, R3  ;  R3 ← R2 + R1
    SUB    1, R3, R4   ;  R4 ← R3 - 1
この例では、ADD命令でR3の値が更新される前にSUB命令がR3を読むと 結果がおかしくなります。

対処方法

スーパースカラプロセッサ

伝統的な「スカラ」プロセッサはスカラ命令(整数などのスカラデータに 対する命令)を実行します。 スーパースカラ (superscalar) プロセッサは「同時に複数のスカラ命令を 実行する」プロセッサのことです。

限定的なスーパースカラ動作としては、 「整数命令と浮動小数点数命令を同時に実行する」 例が挙げられます。

スーパースカラ動作は、一般に、同時に複数の命令を取り出して実行する ことで実現できます。すなわち、スーパースカラプロセッサは複数の パイプラインを持ち、同時に実行される命令はそれぞれのパイプラインで 処理されます。

    2本のパイプラインを持つプロセッサは最大2倍の速度で動作可能(図5.27, 5.28)
    	→命令同士の依存関係が無い場合
スーパースカラプロセッサを設計する方法

データの依存性により「ある命令は同時に実行できない」場合が 起こります。命令の乱発行 (out-of-order isshu) を許す場合は これが特に問題になります。

乱命令発行の実装

命令の乱発行と依存性の扱い方を示すために、 図5.30のプロセッサを考えましょう。 簡単のために、ここでは整数オペランドのみを扱います。 乱発行の実現には、命令ウィンドウ (instruction window) と呼ばれる 命令バッファを使います。 命令ウィンドウはフェッチステージと実行ステージの間に置かれ、 実行待ち命令を保持します。 オペランドが揃ったり、機能ユニットが空くなどで新たに命令が 実行可能になるたびに、ウィンドウから命令が発行されます。

レジスタリネーミング(register renaming)

記憶場所を再利用するために発生する依存関係もあります。 このような資源競合は資源の複製を作って多重化することで 減らすことができます。
 (例)
    ADD    R4, R2, R1   ; R1 ← R2 + R4
    ADD    1, R1, R2    ; R2 ← R1 + 1
    ADD    R5, R4, R1   ; R1 ← R4 + R5
 (レジスタリネーミング)レジスタの名前を一時的に付け換えていきます。
    ADD    R4, R2a, R1a ; R1とR2に関して新しい名前が作られますが
    ADD    1, R1a, R2b  ; そこに格納される値を参照する要求が
    ADD    R5, R4, R1b  ; なくなればこわして構いません。

リオーダバッファ(reorder buffer)

レジスタリネーミングはリオーダバッファによって実現します。 リオーダバッファは先着順待ち行列で、そのエントリを 命令レジスタの結果に動的に割り付けます。

レジスタ書き込みをする命令がデコードされると、 待ち行列の先頭のエントリをその命令に割り当てます。 命令の結果の値はリオーダバッファのエントリの方に書き込まれます。 エントリが待ち行列の最後まで達していて、かつ値が書き込まれていた 場合は、レジスタファイルへ転送されます。 このエントリを解放し待ち行列を1単位分先へ移動させます。 この時点までに書き込みが行なわれていなければ、 書き込みが行なわれるまでリオーダバッファの待ち行列としての 進行は停止されます。


スーパーパイプライン

パイプラインを高速化する技術には

があります。スーパーパイプラインでは、各基本パイプラインステージを さらに分割することで、クロック周波数を上げます。 スーパースカラとスーパーパイプラインを同時に採用することも可能です。


パイプラインに関する練習問題

[5.1] 命令フェッチユニットと命令実行ユニットを持つマイクロプロセッサ を考えます。 このマイクロプロセッサは命令実行と命令フェッチをオーバラップできる ものとします。 T(Fi)を i 番目の命令をフェッチする時間、 T(Ei) を i 番目の命令を実行する時間と仮定し、 次の各場合での8つの逐次命令を処理するのに要する時間を 計算して下さい。 ただし、パイプラインのユニット間でデータの受け渡しは 非同期的に行われるものとします。

  1. T(F_i) = T(E_i) = 100ns, i=1〜8
  2. T(F_i) = 50ns, T(E_i) = 100ns, i=1〜8
  3. T(F_i) = 100ns, T(E_i) = 50,75,125,100,75,150,127,50ns, それぞれ i=1,2,3,4,5,6,7,8の場合

[5.2] 36個の命令を処理するとき、3, 9, 10, 24, 27 番目の命令が 条件分岐命令である場合の5ステージ命令パイプラインの平均命令 処理時間を求めて下さい。 ただし、分岐命令がデコードされた時には、パイプラインは完全に クリアされるものとします。


(補足)VLIW プロセッサ

インテルは90年代後半に64bitプロセッサ Itanium (←プロセッサ名)を出荷しました。 これは VLIW プロセッサです。 インテルはこれを IA-64 アーキテクチャとよび、それまでのx86をIA-32と呼ぶようになりました。

VLIW (Very Long Instruction Word)プロセッサとは、 長い命令を採用したプロセッサのことです。 1命令が長いために、1命令の中に複数のユニットの それぞれに対する動作の指定を含めることができます。

VLIWでないプロセッサでは、命令の実行時に動的に 判断してプロセッサ内の各ユニットが効率よく並行 動作できるように、命令の実行をスケジューリングしていました。 そのために、競合を判断して実行を一時止めたり、 命令の発行順序を変えたりするなど、大変な制御を 行っていたわけです。

これに対してVLIWでは、コンパイル時にプロセッサ内の 各ユニットが効率良く動作できるようにスケジューリング してしまいます。 そのスケジューリングにしたがって各ユニットの動作を 指定した命令を生成してゆくわけです。 こうすると、プロセッサにおいて命令を実行するときは、 命令に記述されている通りに各ユニットを動作させれば よいことになります。 すなわち、複雑な動的制御がいらないので、高速化が 可能になる、というわけです (コンパイラが効率の良いコードを本当に出してくれれば、 ですが)。

IA-64 は商業的には失敗しました。 インテルはAMDの後を追って2004年ごろに x86 を64bit化したアーキテクチャの CPU を出荷し、こちらが現在では主流になっています。 やはり過去との互換性は重要だ、というのが結論でしょうか。