コンピュータ基礎の基礎～パイプライン
- 2010/07/27 19:47
- カテゴリー：備忘録
コンピュータは，これまで様々な工夫で速く動作するように作られてきました。その当時は最先端だったことでも，今は非常に基礎的なものとなっていたりするのですが，何分普段使うものではないので，ついつい忘れてしまいがちです。
そこで，この場をちょっとした復習に使おうと思います。第1回目はパイプラインです。
問題:あるCPUも命令実行におけるパイプライン処理が，以下の6段のステージをもつとする。
F:命令読みだし（instruction fetch）
D:命令解読（instruction decode）
A:番地計算（address calculation）
B:オペランド読みだし（operand fetch）
E:命令実行（instruction execution）
W:結果格納（write back）
パイプライン処理を行わない場合，命令実行Eの所要時間は15ns，Eを除く各ステージの所要時間は10nsであるとする。また，パイプライン処理を行う場合は，上記の他に各ステージにおいて2ns必要となる。2nsの打ち合わせは，クロックスキューの調整とパイプライン処理の準備のための時間である。この時，以下の問いに答えよ。
1)パイプライン処理を行わない場合の実行過程（時間を横軸）を3命令分図示せよ。
2)パイプライン処理を行う場合，ステージの所要時間（パイプラインピッチ）はいくらとなるか？
3)パイプライン処理を行う場合の命令実行過程を3命令分図示せよ。
4)パイプライン処理による定常状態における速度向上率を求めよ。
5)命令実行パイプライン処理の流れを阻害する要因（ハザード）について説明せよ。
回答:
1)
このCPUは6つのステージを持っていますが，Eステージだけは15nsかかり，それ以外は10nsで処理が出来るということです。Eステージというのは実際の命令の処理を行う部分ですから，時間が余計にかかる傾向があります。そこでここをさらに2つに分けるなどして，処理時間を短くするようなことも行われます。
パイプライン処理を行わない，つまり順番に3命令分処理するという事ですので，以下のように書くことができます。下の数字は時刻です。
Ｆ Ｄ Ａ Ｂ Ｅ Ｗ Ｆ Ｄ Ａ Ｂ Ｅ Ｗ Ｆ Ｄ Ａ Ｂ Ｅ Ｗ
0 10 20 30 40 55 65 75 85 95 105 120 130 140 150 160 170 185 195
このCPUは，3命令を実行するのに195nsかかるという事になりますね。1命令当たりの65nsかかっています。
2)
パイプライン処理というのは，各ステージを同時に実行していく方法です。パイプラインというより，ベルトコンベアという感じが正しいと思います。1つの製品を作るのに1時間かかるとしても，1つの行程が10分の流れ作業で作ると，完成品は10分に一度の割合で出てきます。ということは，見た目には1つの製品を10分で作っているように見えるわけです。
一見ウソのように思いますが，これはウソでもなんでもなく，6つの行程がひっきりなしに動いているからです。いわば，1つの製品を作るの必要な工程を順番にせず，一気に同時に行っているから時間が短くなっていると考えられるわけですね。
ややこしいのは，ステージの時間が揃っていない場合です。自分が5分で出来ても，次の人が10分かかっていたら，次の人の手前にものが溜まってしまい，結局10分に一度しかものが完成しません。つまり，一番長い時間のかかる処理に全ての処理を揃えて上げないと，パイプライン処理というのは成り立たないのです。
さて，このCPUは，6つのステージに分かれています。それぞれのステージの処理時間は，Eを除いて10ns，Eだけは15nsかかります。
このCPUでパイプライン処理を行う場合，一番遅いステージに揃えて上げる必要があります。一番遅いのはEの15nsに2nsを確か足した17nsですので，全てのステージを17nsで並べて上げるとよさそうです。この17nsという数字が，パイプラインピッチです。
3)
では，実際にパイプライン処理を図示してみましょう。
Ｆ Ｄ Ａ Ｂ Ｅ Ｗ
Ｆ Ｄ Ａ Ｂ Ｅ Ｗ
Ｆ Ｄ Ａ Ｂ Ｅ Ｗ
0 17 34 51 68 85 102 119 136
どうですか，始めと終わりに全てのステージが動いていない部分がありますが，3命令とは言わずたくさんの命令を流せば，ほとんどの時刻で全てのステージが動いてくれそうです。
実際，同じ3命令の仕事をパイプライン処理することで60ns近くも早く終わらせることに成功しています。この威力は大きいです。
4)
まず，パイプライン処理をしなかった場合の処理時間ですが，これは1)にあるように，195nsです。
これをパイプライン処理にした場合，3)のように136nsで済んでいます。速度向上率は，(195-136)/136*100=43.38%です。
一番遅いステージに揃え，なおかつ各ステージに2nsの余計な時間がかかってしまうとしても，4割も速度が上がっています。これがパイプライン処理の効能です。
5)
ところで，4)の「定常状態」なのですが，では定常状態ではない時というのはどういう時かというと，ステージが遊んでしまうような状態をさします。例えば分岐命令があった場合に起こる状態です。
分岐命令があると，その後に続く命令が確定しません。ですから確定するまで，次の命令が取り込まれることなく，各ステージはしばらく遊んでしまいます。
これをハザードといいます。
パイプライン処理というのは並列処理の一種ですから，前後の命令が時間的に相関がある，つまり前の命令の結果が後ろの命令に影響を与えるような場合，同時に処理することは出来ません。
分岐もそうですし，他にも前の命令で計算した結果を次の命令で使うような場合，前の命令の処理が完了しないと後ろの命令が実行できません。
こうしたハザードをなんの対策も行わずに放置すると，せっかくのパイプライン処理が台無しになってしまうので，いろいろな対策を盛り込むことになります。
まず，前の命令の結果を続く命令が利用する場合です。これは，前の命令の計算結果が出るステージから，結果を次に使うステージにバイパスしてやれば，前の命令の完了を待たずに済みます。これをレジスタフォワーディングといいます。
レジスタフォワーディングでも間に合わない様な場合，残念ながら結果が出るまで次の命令の実行を止めます。この待ち時間をロード遅延といい，ロード遅延を行うために必要なパイプラインを止める仕組みを，インタロックといいます。
ロード遅延を許さず，必ずパイプラインを止める方法もありますが，もしも後の命令と依存関係のない命令と順番を入れ替えることが出来るなら，パイプラインを止めずに済みます。これを遅延ロードといいます。
しかし，現実的に命令の入れ替えが可能になることは少なく，その場合は何もしない命令（NOP）を入れて，パイプラインを止めないようにします。これで，インタロックを実装しなくても待ち時間（ロード遅延）を確保出来ます。
ですが，結局なにもしない命令を入れることは，パイプラインを止めることと同じ事です。なら，インタロックを入れてパイプラインを止めてしまっても結果は同じですし，何もしない命令が入ってこない分プログラムが小さくなるということもあり，こちらの仕組みを使うCPUも多くあります。
もう1つ，分岐命令ですね。分岐命令は，実行結果によって処理する命令が違ってきますから，分岐の結果が確定するまで次の命令を取り込むことが出来ません。
当たり前のこととはいえもったいないですから，分岐命令に続く命令が置かれる場所を遅延スロットという特別な場所とし，ここに置かれた命令を，実際の分岐を遅らせて先に実行してしまいます。分岐を遅らせることから，これを遅延分岐といいます。
こうすると分岐命令があっても命令の実行が行われるようになります。そして，もしこの遅延スロットに入れる命令が，分岐の結果に依存しないような命令だったりしたら，1つ余計に命令が実行出来た事になりますね。
これを目指してコンパイラは，遅延スロットに置くことの出来る命令を探し出して，入れ替えるように動いてくれます。それでも入れ替えることの出来る命令がなかった場合には，なにもしない命令（NOP）を入れる事になります。
この仕組みは，CPUの回路規模がほとんど大きくならずに済み，分岐が行われる場合でも余計に1命令実行することが可能になるというメリットがあります。
なお，遅延スロットは1つとは限りません。2つの場合も3つの場合もありますが，それぞれ実際の分岐が行われるより先に2つもしくは3つの命令が先に実行されるように作ってあります。だから，遅延スロットの数が変わるとプログラムの互換性が損なわれますので，その数は互換性を維持する限りは変更が許されません。
もう1つ，最近は，ふんだんに使えるようになったトランジスタを利用し，こっと積極的に分岐先を予測する分岐予測と，予測された命令を実行する投機実行が使われるようになりました。予測の精度上げれば遅延分岐よりも効率が良く，遅延分岐のようなわかりにくさもないため，新しいプロセッサでは遅延分岐よりも分岐予測と投機実行が好まれる傾向にあるようです。
