パイプライン方式での処理時間の求め方

応用情報の問題で、わからない所があります。

パイプラインの深さをD 、パイプラインのピッチをP 秒とすると、I 個の命令をパイプラインで実行するのに要する時間を表す式はどれか。
ここで、パイプラインの各ステージは1ピッチで処理されるものとし、パイプラインハザードについては、考慮しなくてよい。

　ア 　(I +D )×P 　イ 　(I +D -1)×P
　ウ 　(I ×D )+P 　エ 　(I ×D -1)+P

正解は「イ」なのですが、お恥ずかしながら全く腑に落ちません。

私の理解とそれによって導き出される式は以下のようになっています。
どこでまちがっているのか、教えていただけませんでしょうか。

◆私の理解
　パイプラインの深さをD：命令の中のステージ数はD個
　パイプラインのピッチをP 秒：1ピッチP秒かかる
　パイプラインの各ステージは1ピッチで処理：各ステージの処理はP秒かかる
　I 個の命令：命令がI個ある

◆式
　所用時間＝ I　×　（D ×　P）

D×Pで命令内全ステージにかかる時間を求めたつもりです。
それに命令数をかけています。

すみません、よろしくお願いいたします。

No.4 回答者： Tacosan 回答日時： 2014/04/09 23:43

「パイプラインの各段が並列に動作しうる」ことを忘れてるだけなんだが....

パイプラインの深さと同じだけの本数を持つプロセッサが思い付かない＞#3.

No.3 回答者： chie65535 回答日時： 2014/04/09 12:02

因みに。

パイプラインの個数は、パイプラインの深さと同じ個数がある、と言うのが前提。

パイプラインの深さが７であれば、通常、パイプラインは７つあって、パイプラインの個数と同じだけの個数の命令を並行して同時に処理できる。

先ほどの例では、パイプラインは４つあれば良い。

１～４番目の命令は、順に１～４番のパイプラインに入る。

５番目の命令は、１番目の命令を処理し終わって空になった、１番のパイプラインに入る。

６番目の命令は、２番目の命令を処理し終わって空になった、２番のパイプラインに入る。

７番目の命令は、３番目の命令を処理し終わって空になった、３番のパイプラインに入る。

なので、図を正確に書くと、以下のようになる。

　深さ４
←──→
□□□□■■■■＿＿　１と５番目の命令
＿□□□□■■■■＿　２と６番目の命令
＿＿□□□□■■■■　３と７番目の命令
＿＿＿□□□□＿＿＿　４番目の命令
１ ２ ３ ４ ５ ６ ７ ８ ９ 10　←（７＋４－１）×１＝10

判りやすいように、１～４番目の命令は□で、５～７番目の命令は■で表記。

因みに、パイプラインの個数が足りないと、途中で「すべてのパイプラインが埋まってしまう」ので、無駄な空き時間が出来てしまう。

例えば、パイプラインの深さが４なのに、パイプラインが３個しか無いと、以下のようになる。

　深さ４
←──→
□□□□■■■■◇◇◇◇　１と４と７番目の命令
＿□□□□■■■■＿＿＿　２と５番目の命令
＿＿□□□□■■■■＿＿　３と６番目の命令
１ ２ ３ ４ ５ ６ ７ ８ ９ 101112

上記の場合「４ピッチ目」には、すべてのパイプが埋まっているので、パイプに空きが出来る「５ピッチ目」まで、何も出来ずに待たされてしまう。

同様に、８ピッチ目にも、すべてのパイプが埋まってしまうので、９ピッチ目まで待たされてしまう。

また逆に、パイプラインの深さよりも多い個数のパイプラインがあると、以下のように、パイプラインに無駄が出来てしまう。

　深さ４
←──→
□□□□＿■■■■＿　１と６番目の命令
＿□□□□＿■■■■　２と７番目の命令
＿＿□□□□＿＿＿＿　３番目の命令
＿＿＿□□□□＿＿＿　４番目の命令
＿＿＿＿□□□□＿＿　５番目の命令

上記の場合、１番のパイプが空いても、次の命令がすぐには入って来ないので、１番目の命令と６番目の命令の間に隙間が出来て「何もしてない無駄なサイクル」が出来てしまう。

２番のパイプも、同様に、２番目の命令と７番目の命令の間に隙間が出来てしまう。

No.2 回答者： chie65535 回答日時： 2014/04/09 11:34

図が見づらくなったので、図だけ再投稿。

　深さ４
←──→
□□□□＿＿＿＿＿＿　１番目の命令
＿□□□□＿＿＿＿＿　２番目の命令
＿＿□□□□＿＿＿＿　３番目の命令
＿＿＿□□□□＿＿＿　４番目の命令
＿＿＿＿□□□□＿＿　５番目の命令
＿＿＿＿＿□□□□＿　６番目の命令
＿＿＿＿＿＿□□□□　７番目の命令
１ ２ ３ ４ ５ ６ ７ ８ ９ 10　←（７＋４－１）×１＝10

No.1 ベストアンサー 回答者： chie65535 回答日時： 2014/04/09 11:31

命令の個数を７、パイプラインの深さを４、パイプラインのピッチを１秒とする。

この場合、１つの命令がパイプラインを通り抜けるには４秒かかる。

そして、それぞれの命令は、１秒づつズレながら順にパイプラインに入っていく。

図にすると、以下のようになる。

　深さ４
←──→
□□□□＿＿＿＿＿＿　１番目のパイプに入った命令は抜けるまで４秒かかる
＿□□□□＿＿＿＿＿　２番目の命令が入るのは１ピッチ経過後。つまり１秒後
＿＿□□□□＿＿＿＿　３番目の命令が入るのは２ピッチ経過後。つまり２秒後
＿＿＿□□□□＿＿＿　４番目の命令が入るのは３ピッチ経過後。つまり３秒後
＿＿＿＿□□□□＿＿　５番目の命令が入るのは４ピッチ経過後。つまり４秒後
＿＿＿＿＿□□□□＿　６番目の命令が入るのは５ピッチ経過後。つまり５秒後
＿＿＿＿＿＿□□□□　７番目の命令が入るのは６ピッチ経過後。つまり６秒後
１ ２ ３ ４ ５ ６７ ８９ 10　←（７＋４－１）×１＝10

最後の命令がパイプラインに入るのは「命令の個数－１ピッチ後」であり、その命令がパイプラインを通過し終わるのは、パイプラインの深さだけかかる。

つまり、最後の命令がパイプラインを通り抜け終わるのは「命令の個数－１＋パイプラインの深さ」に、１ピッチの秒数を掛けた秒数が経過した時である。

「最後の命令がパイプラインを通り抜け終わる秒数」と言うのは「全部の命令を実行するのに要する時間」そのものである。

「（命令の個数－１＋パイプラインの深さ）×１ピッチの秒数」を意味する式は「イ 　(I +D -1)×P」である。

この回答へのお礼

詳しいご解説ありがとうございます。
まだ理解できてません。。。
もう少しそしゃくのための時間が必要なのですが、取り急ぎお礼まで。
ありがとうございます！

お礼日時：2014/04/10 23:10