パイプライン処理の内容と計算問題

(1)以下の同じ命令セットアーキテクチャの三つのプロセッサ(a)~(c)において、実行命令数が1,000,000で、そのうち20%が条件分岐命令であるプログラムを実行した場合の計算時間を求めよ。条件分岐命令の30%で条件が成立するものとする。
(a)クロック・サイクル時間が2nsの単一サイクル方式のプロセッサ
(b)クロック・サイクル時間が500psの5段パイプラインプロセッサ。ただし、条件分岐命令で条件が成立した場合、1サイクルストールとする。
(c)クロック・サイクル時間が300psの10段パイプラインプロセッサ。ただし、条件分岐命令で条件が成立した場合、2サイクルストールとする。

(2)クロック周波数2GHzで動作する、ロード/ストア・アーキテクチャで5ステージ・パイプライン方式のプロセッサがある。ロード命令の結果が直後の命令で使用される場合、および分岐命令で分岐が成立する場合とジャンプ命令の場合に1サイクルストールするものとし、その他のハザードは無いものとする。実行命令数が100,000で、命令の出現頻度がALU命令：50%、ロード：20%、ストア：15%、分岐：10%、ジャンプ：5%のプログラムを実行した場合の実行時間を求めよ。ロード命令の直後にストールする割合は50%、分岐命令で分岐が成立する場合は40%とする。

京大 情報学研究科 通信情報システム専攻 計算機アーキテクチャ(A-6) より引用

パイプライン処理とは

ある命令を実行するために必要な処理を分割し、連続的に処理することを言います。

例として、A+Bを計算するときの計算機内の命令内容を考えてみましょう。

上記2つの命令に分けられます。

一つの命令に対し、実行する処理は下記の6つです。

(注意)教科書によっては、3~6の4つの処理を、実行→メモリアクセス→書込みと3つの処理で表記していることがあります。

本サイトでは、処理の内容をなるべく細分化して分かりやすくしたいため、上記6段階存在するとして説明していきます。

A+Bを計算するとき、実行すべき命令の数が2つで、命令1つにつき処理が6つありますので、順番に処理していくならば、2*6=12サイクルかかります。(逐次処理)

一方で、パイプライン処理だと下記になります。

同一サイクル(周期)で処理が被らないように1サイクルずつ後追いで命令ごとの処理を実行していきます。

下記が概要図です。

結果、全ての命令を実行するためにかかるサイクル数は7サイクルとなります。逐次処理に対し処理時間を5サイクル低減できました。

パイプライン処理の欠点

命令1の処理が最後まで終わっていないのに、命令2の処理が始まる構成上下記の欠点があります。

パイプラインにおけるハザードとは、処理をやり直す、遅れることを言います。

その結果、全ての命令を実行するためにかかる時間が遅延します。

本記事では、冒頭で紹介した問題の都合から、特に制御ハザードについて取り上げます。

下記に概要図を示します。命令1〜5まで存在し、命令3が分岐命令だったとします。

この場合、命令4、5で先に処理をしていた①〜⑤が無駄になってしまいます。

なお、制御ハザードをなるべく低減するため、分岐予測という手法が用いられることがあります。

これは、分岐条件の結果(Yes/No)のいずれかを予測し、予測した側の結果が発生した前提で後段の命令を実行していく方式です。

代表例としては、下記のような方式があります。

1.について、そのままです。Yesが多いと考えられるプログラムを実行する際に有用です。

2.について、プログラムの構成観点での予測になります。

どのようなプログラムでも、基本的にいつかは必ず処理が完了します。(END)
この思想を正とすると、分岐命令も処理が完了する側に予測することが本命であると考えられます。
処理の後半部分になるほど、参照するアドレスは後方になる考えから、後方のアドレスを参照すればプログラムの流れ通りになるとし、やり直す回数も少ない考えから予測する方式です。

3.について、一つ前の分岐がYesなら、今回の分岐はYesと予測。NoならNoと予測する方式です。
1ビットカウンタ予測と呼ばれていますが、2連続でYes/Noが成立したとき、Yes/Noの対応する予測とする2ビットカウンタ予測もあります。

解答例

(1)(a)単一サイクル方式のプロセッサの計算時間

本問では、逐次処理の場合の計算時間を求めています。

単に実行命令数にクロック・サイクル時間を掛け算すればよいです。

クロック・サイクルとは、一つの命令を実行するためにかかる時間です。

\begin{aligned}T=1000000*2.0*10^{-9}=2.0*10^{-3}[s]=2[ms]\end{aligned}

(1)(b) 5段パイプラインプロセッサの計算時間

本問から、パイプライン処理の場合の計算時間を求めていきます。

条件分岐命令が成立する確率は、0.2*0.3=0.06なので、この時は1サイクルストールします。

ストールとは、処理を遅らせるという意味です。ストールした場合、処理を完了するためには実質2サイクル必要となります。

\begin{aligned}1000000*500*10^{-12}(1+0.06)=530[μs]\end{aligned}

パイプライン方式に変更したおかげで1クロックサイクルが2ns→500psと高速化しています。

このため、ストールする確率はあれど、処理時間は(1)(a)より速くなっています。

(1)(c) 10段パイプラインプロセッサの計算時間

(2)(b)と同様に考える。

条件分岐命令が成立する確率は、0.06で、この時は処理に実質3サイクル必要。

\begin{aligned}1000000*300*10^{-12}(1+0.06*2)=336[μs]\end{aligned}

(2) パイプラインプロセッサ(2GHz)の実行時間の計算

まず、ハザードの発生確率を求める。

問題文より、ストールする要因は下記3つになる。発生確率も考慮すると

以上を合計すると、0.19(19%)の割合でハザードが発生する。

ハザードが発生したときは2クロックの処理が必要なため、

実行命令数100000に対し、100000*0.19=19000は2クロックの処理が必要(38000回)

よって、必要なクロック数は、100000*0.81+3800=119000

クロック周波数は2GHz=1秒間に2*10^9回命令を実行できるため、求める計算時間は

\begin{aligned}T=\dfrac{119000}{2000000000}=0.0000595[s]=59.5[μs]\end{aligned}

※厳密には、最後の100000番目の命令を実行するとき、処理⑥の分が最後の119000のクロックに入らない可能性があります。

そのため、11900″1″など、1の位に端数が発生するかもしれませんが、大勢に影響しないため、無視しています。

最後に

パイプラインは、多くの大学の院試で頻出の分野です。

応用情報など、企業に勤めてからの資格試験でも出題されます。

本記事が参考になれば幸いです。

参考文献

情報処理システム入門 (第3版) 浦 昭二 (編集), 市川 照久 (編集)　P52,53

コンピュータアーキテクチャ(改訂5版) 馬場敬信 (著) P242-245