計算機の構造後期資料7

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

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

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

オーバラップ (overlap)
パイプライン (pipeline)

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

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

結果の保存

T₁

T₂

T₃

T₄

T₅

T₆

T₇

T₈

T₉

T₁₀

T₁₁

T₁₂

命令の実行

T₁

T₂

T₃

T₄

T₅

T₆

T₇

T₈

T₉

T₁₀

T₁₁

T₁₂

オペランドの用意

T₁

T₂

T₃

T₄

T₅

T₆

T₇

T₈

T₉

T₁₀

T₁₁

T₁₂

命令のデコード

T₁

T₂

T₃

T₄

T₅

T₆

T₇

T₈

T₉

T₁₀

T₁₁

T₁₂

命令のフェッチ

T₁

T₂

T₃

T₄

T₅

T₆

T₇

T₈

T₉

T₁₀

T₁₁

T₁₂

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

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

性能とコスト

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

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

    速度向上率 = T₁ / T_n = sn / (n + s - 1)

s→∞とすると、速度向上率→nとなります。

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

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

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

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

    処理時間 = Σ^(n-1)_i=1 Max(T(A_i), T(B_(i-1)))

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

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

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

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

パイプラインのハザード

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

リソースの競合
(特に分岐命令によって生じる)手続き依存関係
データ依存関係

リソースの競合

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

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

    addl   (EBX), (EAX)

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

解決策の例

データのメモリ読み書きを 1つのユニットだけで行うようにする(図5.15)。

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

複数のメモリモジュールやインタリーブメモリを用いて 1度に命令を複数個フェッチすることにします。図5.16の例では全てのユニットが同時に動作することはなく、 3サイクルで2命令が実行されます。
命令メモリとデータメモリをキャッシュレベルで分離します。こちらが一般的な方法です。

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

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

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

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

改善策

可能性のある命令をフェッチする命令バッファを使う方法(図5.18)。
可能性のある命令列を両方フェッチします。
分岐命令の次の命令になりやすい命令を動的に予測する方法(図5.19)。
『分岐履歴』とは「その分岐命令で今までに分岐したかどうかの記録」です。分岐履歴を用いて「分岐する可能性と分岐しない可能性のどちらが高いか」を予測して可能性の高い方の計算を始めてしまうのが『分岐予測』です。
最初の分岐命令が現れたときには初期の予測を行います。実際の分岐アドレスがわかった時点で高速の look-up table (検索テーブル) に分岐先アドレスを書き込みます。同じ命令が同じアドレスで使われるとこの look-up table に書いてある分岐先アドレスの方の計算を続行するわけです。当然、分岐予測は当然はずれることもありますが、その場合は予測に基づいて行っていた計算を捨てて、正しい方の計算をやり直します。
予測テーブルは分岐履歴テーブル(branch history table)または分岐アドレスバッファ (branch target buffer)ともよばれます。
遅延分岐命令 (delayed branch)
「分岐命令が実行されると、パイプラインの中を全部捨ててしまう」ようでは、パイプラインにおける分岐命令のペナルティは非常に大きくなります。そこで、分岐命令が実行される時にパイプラインの中身を全部捨てるのではなく、その後に続く数個の(分岐命令ではない) 命令は実行し続けよう、というのが『遅延分岐』です。
一般には、「分岐命令の後に1つの命令を入れることができる場合は約70％ですが、２個以上を入れることは難しい」そうです。そこで、たとえば SPARC では1命令の遅延分岐を採用しています。
遅延分岐で意味のある命令をおけない場合は、分岐命令の後に NOP 命令(何もしない命令)を置きます。
静的予測
プログラマやコンパイラは、ループ中でどのように条件分岐が利用されるか知っているので、どちらの命令が実行される確率が高いかわかるはずです。そこでどちらが実行されやすいかを命令に埋め込んでしまう、という方法です。このためには、命令に予測ビットの場所を設けます。たとえば intel 80960 では85％の精度で予測可能と報告されています。

データ依存

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

    ADD    R2, R1, R3  ;  R3 ← R2 + R1
    SUB    1, R3, R4   ;  R4 ← R3 - 1

この例では、ADD命令でR3の値が更新される前にSUB命令がR3を読むと結果がおかしくなります。

対処方法

パイプライン・インターロック (pipeline interlock)
依存関係がある命令の実行を止めることによって、読み出し／書き込みの順序を正しく保つ方法です。実現方法としては、各オペランドのレジスタに1ビットのタグを設けて、レジスタに正しい値が入っていることを表わします(MC88100)。
- レジスタに書き込む命令は、タグを調べて、タグが1であれば0にします。その後値を書き込むときに、タグを1に戻します。
- レジスタを読む命令はタグが 0 の間待ちます。
(例)図5.24
```
    ADD    4, R4, R3   ; R3 ← R4 + 4
    SUB    8, R3, R5   ; R5 ← R3 - 8
    SUB    12, R3, R6  ; R6 ← R3 - 12
```
内部フォワーディング(internal forwarding)
フォワーディングとは中間の記憶装置を使わずに、ある命令の結果を直接別の命令へ渡す技術のことです。これによって前のステージで更新されちたレジスタを後で読むサイクルを削除することができます。
内部フォワーディングは、プログラマには見えないプロセッサ内部レジスタやデータ経路を用いてハードウェアによって行われます(図5.25)。
```
    ADD    R0, R2, R3  ; R3 ← R2 + R0
    SUB    8, R3, R4   ; R4 ← R3 - 8
    SUB    4, R3, R5   ; R5 ← R3 - 4
```

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

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

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

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

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

スーパースカラプロセッサを設計する方法

スカラプロセッサの複製をつくってそれぞれをほぼ独立的に動作させる方法
```
    (例) Intel Pentium (u, v unit)
```
1本のパイプラインに全ての命令を処理させるのではなく、機能ごとに別のユニットを用意してこれを複数並列に動作させる方法。
1. 命令取り出しユニットが複数の命令を取り出し、オペランド取り出しユニットへわたします。
2. オペランドの準備を待っている命令は命令バッファに保持されます。
3. オペランドが揃うと、命令は異なった実行ユニットに対して発行 (issue) されます。
```
    (例) Intel P6 (= Pentium Pro)
    	予約ステーションと並べ換えバッファも持つ
```

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

命令の乱発行(out-of-order issue) --- 実行順序を変更できる、たとえば停止状態にある命令を追い越して別の命令を実行開始できること。
命令の順発行(in-order issue) --- プログラム中の順序通りに、命令がオペランド取り出しユニットから取り出されること。

乱命令発行の実装

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

集中型命令ウィンドウ
すべての保留状態の命令を保持します。
分散型命令ウィンドウ
命令バッファは予約ステーション (reservation station) と呼ばれ、各機能ユニットの入り口に置かれています。デコード済み命令は適切な予約ステーションに送られます。予約ステーションは、命令が必要なオペランドを全部受け取り、機能ユニットが空いたときにその命令を機能ユニットへと発行します。

レジスタリネーミング(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)

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

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

スーパーパイプライン

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

スーパースカラ
スーパーパイプライン

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

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

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

T(F_i) = T(E_i) = 100ns, i=1〜8
T(F_i) = 50ns, T(E_i) = 100ns, i=1〜8
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 プロセッサ

インテルは近年64bitプロセッサ Itanium (←プロセッサ名)を出荷しました。さらにインテルは、大幅に性能を向上させたItaniumプロセッサ (McKineley や Madison ←開発コード名)を開発しています。これらは VLIW プロセッサです。これからは VLIW アーキテクチャが流行ってゆく可能性があります。

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

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

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

計算機の構造 後期 資料7