シングルサイクル、マルチサイクルCPUと命令パイプライニングについて見ていきましょう。
本記事の内容は浦項工科大学校のCSED311の内容に基づき、
授業で扱われなかったいくつかの内容を追加して構成しました。
CPUの実装
シングルサイクルCPU
CPUが1つの命令を実行するには、通常以下の5段階を経ます。
- IF (Instruction Fetch)：PCが指すアドレスから命令を メモリ(I-cache)から取得します。同時にPCを次の命令アドレスに 更新します。
- ID (Instruction Decode)：取得した命令を解釈します。命令が加算なのか loadなのか分岐なのかを把握し、必要なレジスタ値を読み込みます。
- EX (EXecute)：実際の演算を行います。ALUで加算、減算、比較などの 算術/論理演算を行ったり、メモリアクセスが必要な命令であればアドレスを計算します。 分岐命令の場合は、分岐条件をこの段階で判断します。
- MEM (MEMory Access)：メモリにアクセスする段階です。store命令ならデータ メモリ(D-cache)に書き込み、load命令なら読み込みます。
- WB (Write Back)：結果をレジスタに書き込む段階です。ALU演算の結果や メモリから読み込んだ値を目的のレジスタに保存します。
1クロックサイクル内でこのような命令のすべての段階をすべて終わらせる構造のCPUを シングルサイクルCPUと呼びます。1サイクル内にメモリから命令を取得し、 デコードし、演算し、メモリアクセスし、レジスタに書き込むのをすべて実行します。 このように実装すると、実装が単純で理解しやすいです。
しかし致命的な欠点があり、クロックサイクルの長さを最も遅い命令に合わせなければ ならないという点です。例えばADD命令はメモリアクセスが不要なのでIF、ID、 EX、WBだけ行えばよいのですが、LOADはIF、ID、EX、MEM、WBの5段階すべてを経る必要があります。 シングルサイクルではすべての命令が同じサイクル長を使うため、addもloadと同じくらい長い サイクルを待たなければなりません。最も遅い命令に他のすべての命令が引きずられて 時間を無駄にしているわけです。
各段階の所要時間を以下のように仮定してみましょう。
| 命令の種類 | IF | ID | EX | MEM | WB | 合計 |
|---|---|---|---|---|---|---|
| Load | 200ps | 100ps | 200ps | 200ps | 100ps | 800ps |
| Store | 200ps | 100ps | 200ps | 200ps | — | 700ps |
| R-type | 200ps | 100ps | 200ps | — | 100ps | 600ps |
| Branch | 200ps | 100ps | 200ps | — | — | 500ps |
シングルサイクルCPUではクロック周期を最も遅いLoad命令に合わせて800psに 固定する必要があります。したがって500psで十分なBranch命令も、毎サイクル800psを 消費することになり、命令あたり300psが無駄になります。
シングルサイクルCPUの設計
シングルサイクルCPUは1クロック内で命令1つを最初から最後まで実行します。 そのため、すべての機能ユニットが同時に動作できなければならず、制御回路が単純です。
シングルサイクルCPUの各ユニット間のデータパスは、IFからWBまでの経路が一直線に つながった構造です。命令メモリとデータメモリが別々に存在し、ALUは1つですが、PC + 4 を計算する専用のAdderは別途必要です。ALUがEXで演算を行うと同時に、PC + 4の 次のアドレス計算も並行して進めなければならないためです。
制御ユニットは組み合わせ論理(combinational logic)で構成されます。1サイクル内にすべて
が終わるため、制御ユニットで現在の状態を記憶する必要がありません。命令を
入力として受け取り、ALU、メモリなど各ユニットに必要な制御信号、例えばRegDst、
ALUSrc、MemtoRegのような信号を一度に出力します。
クロックサイクルの長さは、IF -> WBの経路の中で最も長い経路の伝播遅延(propagation delay)によって決まります。 これをクリティカルパス(critical path) と呼び、通常はLoad命令の経路が 最も長いです。命令メモリ -> レジスタ読み出し -> ALU演算 -> データメモリ -> レジスタ書き込みまですべてのユニットを直列に経由するためです。 シングルサイクルCPUではすべての命令が同じ時間、1サイクル内で作業を終わらせなければ ならないため、すべての命令がこのクリティカルパスの長さだけの時間を使わなければなりません。
マルチサイクルCPU
これを解決するために、各命令が自分が必要とする時間だけかかるようにする 方式がマルチサイクルCPUです。1つの命令を複数のクロックに分けて、各 命令が必要とする時間だけ複数のクロックを消費させるのです。
マルチサイクルCPUでは各命令のCPI (Cycles Per Instruction)が異なり、
Programmer Visible Stateは命令のサイクルが終わる時にのみ更新されます。
命令が複数のクロックにわたって実行されるためCPIが1より大きくなります。代わりにtime/cycleが
シングルサイクルよりはるかに短くなり、全体的な性能が向上します。
先ほど見た命令をマルチサイクルCPUに載せてみましょう。クロック周期を最も短い 段階である100psに取ると、100psの段階は1クロック、200psの段階は2クロックが 必要です。
| 命令の種類 | IF | ID | EX | MEM | WB | 総クロック | 総時間 |
|---|---|---|---|---|---|---|---|
| Load | 2 | 1 | 2 | 2 | 1 | 8 | 800ps |
| Store | 2 | 1 | 2 | 2 | — | 7 | 700ps |
| R-type | 2 | 1 | 2 | — | 1 | 6 | 600ps |
| Branch | 2 | 1 | 2 | — | — | 5 | 500ps |
各命令が実際に必要な分だけクロックを消費するので、シングルサイクルで すべての命令が800psに縛られていたのとは異なり、Branchは500ps、R-typeは600psに 終わるようになります。
また、シングルサイクルCPUでは1サイクルですべての作業を処理しなければならなかったため、命令を 取得するメモリとデータを取得するメモリが別々に必要だったのに対して、マルチ サイクルCPUではIFとMEMが別々のサイクルで処理されるため、メモリを1つだけ 置いて、IFでは命令を取得し、MEMではデータを読み書きするという形で使用して ハードウェアを共有できるという利点もあります。(ただし現代のCPUでは限られたメモリ 帯域幅の中で速度向上のためにI-cacheとD-cacheが分離されているので、メモリを1つに 共有するという利点は実際には大した意味はありません。トランジスタが貴重でハードウェア リソースが限られていた初期のCPUでは、このような利点があったと覚えておけば よいでしょう。)
マルチサイクルCPUの設計
マルチサイクルCPUは1つの命令を複数のサイクルで実行しなければならないため、シングル サイクルCPUと設計上の違いがあります。
1つ目は、一時レジスタが必要です。シングルサイクルではデータが1サイクル 内で回路をそのまま流れていけばよかったのですが、マルチサイクルでは今サイクルの結果が 次のサイクルまで伝達されなければなりません。IRが命令を、レジスタファイルがレジスタから読んだ値を、 ALUが演算結果を、メモリユニットがメモリから読んだ結果をそれぞれ保存し、命令実行 周期の間保持します。
2つ目は、FSM(Finite State Machine)ベースの制御ユニットが必要です。 同じALUがあるサイクルではPC + 4を計算しなければならず、 別のサイクルではSUB演算をします。同じメモリがIFでは 命令を出力しMEMではデータを読みます。このため各モジュール間をつなぐ マルチプレクサの選択信号が、現在の命令がどの段階まで処理されたかによって 変わらなければなりません。シングルサイクルのように命令だけを見て制御信号を決定する組み合わせ論理は 不可能で、現在の状態を記憶し、それに応じて制御信号を変えるFSMが 必要になります。
マイクロコード
マイクロコードはマルチサイクルCPUでFSMを実装する方法の1つで、FSMの制御 信号をROMに保存しておく方式です。ハードワイヤード方式では、現在の状態とopcodeを 入力として受け取り、論理ゲートで直接制御信号を作り出します。高速ですが、命令を 追加したり制御ロジックを修正するには回路全体の設計を変更しなければなりません。
マイクロコード方式では、各状態でどの制御信号をオンにすべきかをROMテーブルに
あらかじめ書いておきます。1行が1つのマイクロ命令(microinstruction)で、そこに
ALUSrcA、ALUSrcB、MemReadなどの制御信号の値と次の状態情報が含まれて
います。FSMの現在の状態がROMのアドレスとなり、該当する行を読み込むと、それが今
サイクルの制御信号になります。
最大の利点は柔軟性です。新しい命令を追加したり、既存の命令の動作を 変更したい場合は、ROMの内容だけを修正すればよいのです。
一方で欠点は速度で、毎サイクルROMを読み込む必要があるため、その分遅延が 追加されます。そのため性能が重要な現代のCPUでは、よく使う単純な命令は制御 信号をハードワイヤリングで処理し、複雑な命令だけをマイクロコードで処理します。
ミリコード、ナノコード
ミリコードとナノコードはマイクロコードを階層的に分けた構造です。
マイクロコードは1つのマイクロ命令にすべての制御信号が入っています。しかし互いに 異なるマイクロ命令が同じ制御信号の組み合わせを繰り返す場合が多々あります。例えば 「メモリから読み込む」という制御信号の組み合わせはLoad命令でも使われ、IF 段階でも使われます。このように重複する制御信号を毎回すべて保存するとROM空間が 無駄になります。
ナノコード(Nanocode) はこの問題を解決するマイクロコード下位の制御階層です。実際の制御 信号の組み合わせをナノコードROMに保存しておき、マイクロコードROMには必要な制御 信号が入っているナノコードROMのアドレス(ポインタ)だけを保存しておきます。マイクロコードが 実行されるとまずマイクロコードROMからナノコードのアドレスを読み込み、そのアドレスでナノコード ROMに行って実際の制御信号を取得します。重複する制御信号をナノコードROMに1 回だけ保存できるので、全体のROMサイズが小さくなります。代わりにROMを2回読まなければならないため 速度が遅くなるという欠点があります。
ミリコード(Millicode) はナノコードとは反対に、マイクロコードの上位にある制御 階層です。複雑な命令を処理する際、マイクロコードだけでは長くなり管理が 難しくなる場合があります。ミリコードは一種のサブルーチンのように動作し、よく繰り返される マイクロコードシーケンスを1つのミリコードルーチンとしてまとめておきます。複雑な命令が 実行されるとミリコードを呼び出し、ミリコードが内部的にマイクロコードシーケンスを 実行する構造です。
現実におけるマイクロコード
現代のx86プロセッサはマイクロコードを積極的に活用します。add、movのような
単純な命令はハードワイヤードデコーダが直接制御信号を決定します。一方REP MOVSB、CPUID、WRMSRのようなCISC特有の複雑な命令はマイクロコードROMから
マイクロオプシーケンスを読み込んで実行します。前の記事でx86 CISCが内部命令を
単純化し、内部的にはRISCスタイルでCPUを動作させていると述べましたが、このようなRISC
スタイルのマイクロオプがそのような役割を果たす装置です。
ミリコードはIBMのz/Architectureメインフレームで代表的に使われます。例えば コンテキストスイッチング、割り込み処理、仮想メモリフォルト処理のような非常に複雑な動作は マイクロコードで実装するには長すぎて複雑です。これらの動作を z/Architectureではミリコードルーチンとして書いておき、ファームウェアレベルのサブルーチンのように 利用します。
ナノコードはCPUの速度が遅くなるという致命的な欠点があるため、現代のCPUではあまり 使われません。歴史的な事例としては1970年代後半に登場した モトローラ68000 (M68K)があり、マイクロコードROMにはナノコードのアドレスだけを保存し、 ナノコードROMに実際の制御信号の組み合わせを保存してROMサイズを削減しました。トランジスタが 十分な現代では、ROMサイズを削減するために別の階層を追加するよりも、ROMを2 回読む速度損失を避けることの方が重要であるため、ナノコードルーチンを使用する場合は 非常に稀です。
パイプラインCPU
パイプライニングはマルチサイクルCPUから一歩進んだ構造です。マルチ サイクルでは1つの命令が複数の段階を経て実行される間、残りの段階の ハードウェアが遊んでいました。パイプライニングはこの遊んでいるアイドルハードウェアに すぐ次の命令を投入して、複数の命令を同時に重ねて実行します。
例えば1つ目の命令がID段階にあれば、IFハードウェアは空いているので2つ目の 命令を取得します。1つ目がEXに行くと、2つ目はIDに、3つ目は新たにIFに 入ってきます。こうすると、5段パイプラインの場合、最大5つの命令がそれぞれ異なる 段階で同時に処理されます。
個々の命令のレイテンシは依然として5サイクルですが、毎サイクル命令が1つ
完了するので、スループットはサイクルあたり1個になります。前の記事で扱ったthroughput != 1/latency
の構造が適用される部分です。
構造的にマルチサイクルとの核心的な違いはパイプラインレジスタです。マルチ サイクルでは一時レジスタが毎サイクル上書きされても問題ありませんでした。どうせ一度に 処理される命令は1つだけですから。しかしパイプライニングでは複数の命令が同時に 処理されるので、各パイプライン段階の間にパイプラインレジスタを置いて、命令ごとの データを独立に保存する必要があります。パイプラインが5段であれば、IF/ID、ID/EX、EX/MEM、 MEM/WBの4つのパイプラインレジスタがあり、それぞれ該当段階の結果と制御信号を 一緒に保存して次の段階に渡します。
制御信号はID段階で一度に生成され、その信号がパイプラインレジスタに乗って 命令と共に段階ごとに流れていき、該当する段階で使われます。制御信号が自然に 次の段階に流れていくので、マルチサイクルのようにFSMが現在の状態を記憶する必要がありません。
パイプライニングの性能
理想的な場合、N段パイプラインはスループットをN倍高めることができます。毎サイクル 命令が1つずつ完了するので、パイプラインがない時よりN倍多くの命令を同じ 時間で処理できます。ただし現実ではこのように単純に性能向上が適用されるわけでは ありません。
1つ目にパイプラインレジスタ(ラッチ)のオーバーヘッドがあります。先に述べたように パイプラインの各段階の間には中間結果を保存するラッチが必要ですが、このラッチを 通過するのにも時間がかかります。パイプラインがない時の全体の演算遅延を$T$、ラッチ 遅延を$S$とすると、$K$段パイプラインの1サイクル長は以下のようになります。
$$T_{\text{clk}}(K) = \frac{T}{K} + S$$
演算部分$T$は$K$で割られて減りますが、毎段階ごとにラッチを1回ずつ通過しなければ ならないので$S$はそのまま加算されます。スループットはサイクルあたり命令1個なので $\text{Throughput}(K) = \frac{1}{T/K + S}$となり、$K \to \infty$の時サイクルは $S$に収束してスループットの上限が$\frac{1}{S}$に固定されます。つまりパイプライニングの 理論的最大速度向上は
$$\text{Speedup}_{\max} = \frac{T + S}{S} \approx \frac{T}{S}$$
となります($T \gg S$の時)。
例えば$T = 10\text{ns}$、$S = 1\text{ns}$としましょう。パイプラインがなければ1 サイクルは11nsです。$K = 5$段に分けると$10/5 + 1 = 3\text{ns}$となり、スループットが 約3.7倍速くなります。$K = 10$なら2nsで5.5倍、$K = 100$なら1.1nsで10倍まで 上がります。$K$を無限に大きくしてもサイクルは1ns($=S$)以下には下がらないので、 理論的な最大速度向上は$T/S = 10$倍あたりで止まります。
2つ目にハードウェアコストが増加します。組み合わせ論理の総量$G$はパイプラインを分けても 変わりませんが、ラッチが$K$個必要なので、段階数に比例してコストが増加します。
$$C(K) = G + L \cdot K$$
ここで$L$はラッチ1個あたりにかかるコスト(面積・電力の代用値であるゲート数)です。 $K = 1$(パイプラインなし)の時$C = G + L$で、$K$が大きくなるほど傾き$L$の 直線でコストが増加します。
例えば組み合わせ論理が$G = 1000$ゲート、ラッチ1個が$L = 50$ゲートとしましょう。 パイプラインがなければ1000ゲートですが、$K = 5$段なら$1000 + 50 \cdot 5 = 1250$ ゲートで25%増加します。$K = 10$段なら1500ゲート(50%増加)、$K = 20$段なら 2000ゲートで元の2倍になります。段階を細かく分けるほどスループットは増えますが、 その分面積と電力コストも一緒についてきます。
したがって、単にパイプラインを無限に増やすのではなく、パイプラインによる性能 向上とコストの均衡点で適切なパイプライン深さを選ぶことが重要です。 1981年にPeter M. Koggeは性能対コストを最大化する最適なパイプライン深さを 以下のような公式で提案しました。
$$K_{\text{opt}} = \sqrt{\frac{T \cdot G}{S \cdot L}}$$
この式はスループット$\frac{1}{T/K + S}$をコスト$G + L \cdot K$で割った性能/コスト比を $K$について微分して0になる地点から得られます。直感的に見ると、分子の$T \cdot G$は 「パイプライニングで得られる利益」を表し(元の演算が長く重いほど分ける 価値が大きい)、分母の$S \cdot L$は「段階を増やす時にかかるコスト」を表します(ラッチ 遅延と面積が大きいほど段階を増やすのが負担)。
先ほど挙げた例の値をそのまま入れてみると、$T = 10\text{ns}$、$S = 1\text{ns}$、 $G = 1000$、$L = 50$の時$K_{\text{opt}} = \sqrt{10 \cdot 1000 / (1 \cdot 50)} = \sqrt{200} \approx 14$です。つまりこの仮定の下では14段程度が性能対コストが 最も良い地点で、それより細かく分けるとラッチオーバーヘッドとハードウェアコストの増加が スループット向上を蝕み始めます。
もちろん実際のCPU設計ではこの公式だけで深さを決めることはありません。後述する パイプラインハザード(データ・制御・構造ハザード)によるストール、分岐予測失敗時の パイプラインフラッシュコスト、電力消費、検証難易度などがすべて深さを制約する 要因です。Kogge公式はあくまで「理想的な条件での上限」を示す 基本公式です。
パイプラインハザード
パイプライニングは複数の命令を重ねて実行するため、命令間に依存関係があると 問題が生じます。これによって発生する問題がデータハザード(Data Hazard) と コントロールハザード(Control Hazard) です。
データハザード
データハザードはパイプラインで前の命令の結果を後の命令が必要とする時、まだ 結果が準備できていないために生じる問題です。
例えば以下のようなRISC-V命令2つが連続で実行されるとしましょう。
add x1, x2, x3 # x1 = x2 + x3
sub x4, x1, x5 # x4 = x1 - x5subはaddが計算したx1を入力として使います。ところが5段パイプラインでaddが
計算を終える時点はEX段階(サイクル3)で、その結果がレジスタファイルに実際に
書き込まれる時点はWB段階(サイクル5)です。一方subは1サイクル後に入ってきてID
段階でx1を読もうとしますが、この時はサイクル3なのでまだx1には古い値が
入っています。これがまさにRAW(Read After Write)データハザードです。
| サイクル | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| add | IF | ID | EX | MEM | WB |
| sub | IF | ID | EX | MEM |
解決方法は3つあります。
1つ目はストール(stall) です。結果が準備されるまで後の命令を止めて 待ちます。パイプラインにはバブル(空のサイクル)が挿入されて、前の命令が処理される 間、組み合わせロジックの残りのロジックは遊ぶことになります。最も単純な方法ですが、性能損失が 大きいです。
2つ目はフォワーディング(forwarding) です。またはバイパシング(bypassing)とも呼ばれます。 ALU演算の結果は、EX段階が終わるとALU出力にすでに存在します。この結果値が レジスタに書き込まれるまで(WB)待つ必要なく、EX/MEMパイプラインレジスタから値を すぐ取り出して次の命令のALU入力に渡してやるのです。ハードウェア的には パイプラインレジスタの出力からALU入力へ行くバイパス経路とマルチプレクサを 追加し、フォワーディングユニットが「今読もうとしているレジスタが前の段階で書き込まれる予定か」 を検知してALUマルチプレクサを制御します。
フォワーディングでほとんどのデータハザードは解決できますが、解決できないタイプの ハザードもあります。load-useハザードです。load命令はEXの次のMEM段階が 終わってはじめて値が出ます。すぐ次の命令がその値をEXで使おうとするとサイクルが 合いません。この場合は1サイクルのストールが避けられません。
lw x1, 0(x2) # x1 = MEM[x2 + 0]
add x3, x1, x4 # x3 = x1 + x4lwの結果はMEM段階が終わるサイクル4で出ますが、addはサイクル4でEXに
入らなければならないので1サイクル早いです。フォワーディング経路を動員しても時間自体を逆向きに
動かすことはできないので、addを1サイクル止めてその場所にバブルを入れなければなりません。
その後はMEM/WBレジスタからaddのEX入力にフォワーディングが入ってきます。
| サイクル | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| lw | IF | ID | EX | MEM | WB | |
| add | IF | ID | stall | EX | MEM |
3つ目はコンパイラが命令順序を再配置(scheduling)する方法です。load の後にはその値を使う命令がすぐ来ないように、間に先に処理されても問題ない 命令を挿入します。
例えば以下のようなCコードがあるとしましょう。
int a = arr[i];
int b = a + 1;
int c = brr[j];
int d = c * 2;これをそのままコンパイルするとlw aの直後にaddi b, a, 1が来てload-useストールが
1回発生し、lw cの後にslli d, c, 1が来てまた1回ストールが発生します。
しかしaとc、bとdは互いに依存していないため、コンパイラは次のように
順序を入れ替えることができます。
lw a, 0(arr_i)
lw c, 0(brr_j) # aを待つ間にcを先にロード
addi b, a, 1 # この時点ではaがすでに準備済み
slli d, c, 1 # cもすでに準備済みlw aとaddi bの間にlw cが入っていて、load-useの間隔が広がり、2つの
ストールが両方消えます。同じ作業を2サイクル早く終えられるわけです。
代表的なコンパイラであるGCCとLLVM(Clang)の両方がこのような命令スケジューリングを行います。 まず命令間の依存関係グラフ (dependency graph)を作り、どの命令がどの 命令の結果に依存するかを把握し、依存関係のない命令の順序を自由に 再配置します。GCCは-O2以上でこの最適化が有効になり、レジスタ割り当ての前後で2 回スケジューリングを行います。LLVMも同様に中間表現(LLVM-IR)レベルとマシンコード レベルでそれぞれスケジューリングを行いますが、両方のコンパイラともターゲットCPUごとに命令 latency、実行ユニット数などのパイプライン情報をテーブルとして持っていて、そのCPUに 合った最適な順序を決定します。
データハザードは先に述べたコスト対性能効率に加えて、あまり深いパイプラインを 使えなくする要素の1つです。もし深いパイプラインを利用すると、 フォワーディングがカバーしなければならない距離がかなり遠くなります。5段パイプラインではADDの後に その結果を使うSUBが来ると、EXの結果をすぐ次のEXにフォワーディングすれば1サイクル 差で綺麗に解決されます。ところがEX段階を分割してEX1、EX2、EX3にすると、 演算結果はEX3で出るのに次の命令はEX1ですでにこの値が必要です。 データフォワーディングでもカバーできないサイクルが増えてストールがより頻繁に発生します。
load-useハザードはさらに深刻になります。5段の簡潔なパイプラインではload後1 サイクルのストールで十分でしたが、MEM段階を複数の段階に分割してより深いパイプラインを 作ると、メモリから値が出てくるまでより多くのサイクルがかかります。その分ストール サイクルが増えたり、コンパイラが間に挿入しなければならない命令数が増えたりします。
コントロールハザード
コントロールハザードは分岐命令で次に実行する命令のアドレスがまだわからない 状態で、パイプラインがすでに次の命令を取得してしまうことで生じる問題です。
例えば以下のようなコードがあるとしましょう。
beq x1, x2, L1 # x1 == x2 ならL1へ分岐
add x3, x4, x5 # 分岐が起きなかった時に実行される命令
sub x6, x7, x8
...
L1:
or x9, x10, x115段パイプラインでbeqの分岐条件はEX段階(サイクル3)になってようやく決定されます。その
間にaddとsubはすでにIF、ID段階に入ってきています。もし分岐が実際に
起きた場合、この2つの命令は誤って取得されたものなので破棄し(flush)、L1のorから
再度取得しなければなりません。
| サイクル | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| beq | IF | ID | EX | MEM | WB |
| add | IF | ID | flush | ||
| sub | IF | flush | |||
| or(L1) | IF | ID |
2サイクルがバブルとして飛んでしまい、分岐1回につき2サイクルのペナルティが生じます。IF段階は 命令を解釈する前なので分岐かどうかすら分からず、分岐の種類はIDで、条件は EXで確定されるため、その間に取得した命令をすべてflushしなければならない ということです。
解決方法は以下の通りです。
1つ目はデータハザードと同じくストールです。分岐命令に出会うと後の 命令を取得せず待ち、分岐の結果が出たら次の命令を取得する 方法です。安全で簡単ですが、分岐が出るたびにサイクルが大きく無駄になり、性能 損失が大きいです。
2つ目は分岐判定の早期化です。分岐の比較をEXではなくID段階で 処理するようにハードウェアを追加すると、ストールのペナルティが2サイクルから1サイクルに 減少します。MIPSがこのような方式を使う代表的なCPUです。
3つ目は遅延分岐(delayed branch) です。これはISAレベルでの約束事で、分岐 命令の後に来る1つ(またはそれ以上)の命令の場所をbranch delay slotとして 定義し、ハードウェアが分岐の有無に関係なくそのスロットの命令を常に実行するように します。つまり「分岐が起きようが起きまいがスロットは必ず実行する」という意味が命令 セットの一部となります。そうするとIF段階で誤って取得してしまう心配自体がなくなるので flushする必要がなく、分岐ペナルティサイクルがそのまま消えます。
代わりにそのスロットを意味のある命令で埋めるのはコンパイラの仕事です。コンパイラは 分岐の手前で分岐条件やジャンプアドレスに影響を与えない独立した命令を 1つ選んでスロットに移します。例えばMIPSコードで：
addu $t0, $t1, $t2 # 分岐と無関係な計算
beq $a0, $a1, L1adduはbeqの比較対象($a0, $a1)と無関係なので、分岐の前でも後でも結果が
同じです。コンパイラはこれを次のように再配置します。
beq $a0, $a1, L1
addu $t0, $t1, $t2 # branch delay slot — 分岐の有無に関係なく常に実行こうするとadduはどうせ実行しなければならない命令だったので、1サイクルのペナルティが無料で
埋められます。もし移せる独立した命令がなければコンパイラはスロットにnopを
入れるしかなく、この場合はただのストールと同じペナルティを負担します。
遅延分岐は1980年代初期のRISCがよく採用した方式で、MIPS、SPARC、PA-RISC、 SuperHなどがすべて1サイクルのdelay slotをISAに刻んでおきました。しかしパイプラインの 深さが増えるとスロット1つでは分岐ペナルティをすべて埋められなくなり、スーパースカラ/アウトオブオーダー 実行が一般化するにつれて分岐予測器の精度の方がはるかに良い解決策となりました。 何よりもISAに刻み込まれたセマンティクスなので、後からパイプライン構造を変えるのも困難です。 そのためARM、PowerPC、Alphaなどの後発のRISCは最初からdelay slotを導入 せず、RISC-Vも明示的に外してあり、MIPSでさえ2014年のR6改訂でdelay slotを 廃止しました。
4つ目はコンパイラレベルで分岐自体を減らしたりなくしたりする方法です。if-conversionは
短いif-then-elseを条件付き移動(x86 cmov、ARM predication、RISC-V Zicondなど)
に変えて分岐を完全に除去します。ループアンローリングは本体を複製して反復ごとに回る
バックエッジ分岐の回数を減らし、インライン化は関数呼び出しとリターン分岐を丸ごと
なくします。
例えばx = (a > b) ? a : bをそのままコンパイルすると比較の後に分岐が1回
入りますが、if-conversionを適用すると次のように分岐なしで終わります。
cmp a, b
mov x, b
cmovg x, a # a > bならx = a、そうでなければそのままb最後は分岐予測(branch prediction) です。現代のCPUで主に使用される 方法です。分岐予測には様々な方法がありますが、これは次の記事でより詳しく 見ていきたいと思います。
>> COMMENTS <<