epochによるキャンセル制御

分岐が成立すると、分岐命令より後ろで既にフェッチした命令を取り消す必要があります。Pipeline processorの設計(13)では、分岐を<ID>で解決していました。分岐が成立したら、同じサイクルにPCの選択Muxで分岐先を選び、後続の命令にinvalidを流してキャンセルします。Pipeline processorの設計(19)の式 V(S+) = N(!W(S) ∪ W(S+)) ∩ !C(S+) のC(S+)が、このキャンセルにあたります。

段をパイプラインFIFOでつなぐBSVの構成では、もう少し簡単な方法があります。各命令に1bitの「epoch」を付けて流し、どの段も「古いepochの命令が来たら捨てる」という同じ規則で動きます。捨てるのは、FIFOから取り出すだけで次の段へ入れない（deqしてenqしない）ことです。validを落とすという操作そのものが要りません。

仕組み

epochのレジスタは<EX>のexEpochだけです。<PC>側のepochは、PCの箱（<PC>と<IF>の間の段間FIFO）の中に、PCと一緒に入っています。

1. <PC>は、PCの箱の中身（直前に確定したPCとepoch）を読み、PC+4に同じepochを付けて出す。
2. <EX>は、命令のPCと即値から分岐先を計算する。分岐が成立したらexEpochを反転し、<PC>へ分岐先を送る（redirect）。
3. <PC>はredirectを受けたら、分岐先に反転したepochを付けて出す。
4. <IF>、<ID>、<EX>の各段は、命令のepochがexEpochと一致しなければ、その命令を捨てる。

epochは、redirectの回数を数える世代番号の最下位ビットだと考えると分かりやすいです。

取り消しの規則は全段で同じです。どの段も、自分の処理より先にepochを比べ、古ければ捨てます。

タイミング

0100番地の分岐命令が成立し、0200番地へ飛ぶ例です。各列は、その段にいる命令のPCで、括弧内はその命令のepochです。<PC>列は、そのサイクルの終わりにPCの箱に入る値です。

分岐ペナルティは2サイクルです。この表は、下のコードをbsc 2025.07でコンパイルし、bsimとiverilogで同じ結果になることを確認したものです。

サイクル4では、<EX>の分岐判定と分岐先の計算が、同じサイクルのうちに<PC>のMuxまで組合せ回路でつながっています。つまりこのサイクルの<PC>の出力は、事実上<EX>が決めています。<PC>が<EX>の次のサイクルに動くわけではありません。同じサイクルの<IF>と<ID>も、<EX>が反転したexEpochを見て、0108と0104を捨てます。誤った命令は、すべてサイクル4のうちに消えます。

パイプラインFIFOでは、下流の段のruleが先にスケジュールされます（<EX>→<ID>→<IF>→<PC>）。そのため、<EX>が書いた値を同じサイクルの<ID>、<IF>、<PC>が読めます。exEpochはmkCRegで、ポート0を<EX>、1を<ID>、2を<IF>が使います。mkCRegはPreludeにある並行レジスタで、MITのArvindらの言うEHR（Ephemeral History Register）と同じものです。ポート0が書いた値を、同じサイクルのポート1以降が読めます。ポート数の上限は5です（BSC Libraries Reference Guide 2.4.2）。

1bitで足りる理由

exEpochが2回目に反転するのは、新epochの有効な分岐命令が<EX>に着いたときです。その命令は、<PC>がredirectを受けた後に出したものです。FIFOでは追い越しが起きないので、それより前に出た旧epochの命令は、すべて捨てられたか<EX>を通り過ぎています。

つまり、パイプライン中に同時に存在する世代は「旧」と「新」の最大2つです。世代番号の上位ビットは不要で、LSBだけで区別できます。条件は、redirectを出す段が1つであることと、段間が順序を保つFIFOであることです。

BSVの例

段間のデータは素の構造体です。分岐判定は省略して、<ID>が作ったisBrとtargetで表しています。

typedef struct { Addr pc; Bool epoch; }            PC2IF deriving (Bits, Eq);
typedef struct { Addr pc; Bool epoch; Inst inst; } IF2ID deriving (Bits, Eq);
typedef struct { Addr pc; Bool epoch; Bool isBr; Addr target; } ID2EX deriving (Bits, Eq);

// PCの箱。lastで中身を読み返せる1段のパイプラインFIFO
PipeQ#(PC2IF)      ifs         <- mkPipeQ(PC2IF { pc: 'h100 - 4, epoch: False });
FIFO#(IF2ID)       ids         <- mkPipelineFIFO;
FIFO#(ID2EX)       exs         <- mkPipelineFIFO;
Reg#(Bool)         exEpoch[3]  <- mkCReg(3, False);           // [0]:EX, [1]:ID, [2]:IF
Reg#(Maybe#(Addr)) redirect[2] <- mkCReg(2, tagged Invalid);  // [0]:EX, [1]:PC

// <EX>
rule ex_stage;
   let x = exs.first; exs.deq;
   if (x.epoch == exEpoch[0]) begin
      // ここで演算し、MAへenqする
      if (x.isBr) begin
         redirect[0] <= tagged Valid x.target;   // PCのMuxへ
         exEpoch[0]  <= !exEpoch[0];
      end
   end
   // epochが合わない命令はdeqするだけ（enqしない）で捨てる
endrule

// <ID>  取り消す命令は捨てる。ハザード中は発火しない（=wait）
Bool idKill = ids.first.epoch != exEpoch[1];   // EXが今反転した値を見る
Bool idHaz  = hazardCheck(ids.first);

rule id_kill (idKill);
   ids.deq;                                     // enqしない
endrule

rule id_stage (!idKill && !idHaz);
   let x = ids.first; ids.deq;
   exs.enq(ID2EX { pc: x.pc, epoch: x.epoch, isBr: x.inst == 1, target: 'h200 });
endrule

// <IF>  取り消す命令は捨てる
Bool ifKill = ifs.first.epoch != exEpoch[2];

rule if_kill (ifKill);
   ifs.deq;                                     // enqしない
endrule

rule if_stage (!ifKill);
   let x = ifs.first; ifs.deq;
   ids.enq(IF2ID { pc: x.pc, epoch: x.epoch, inst: imem(x.pc) });
endrule

// <PC>  PCの箱(ifs.last) → +4 → Mux(redirect優先) → PCの箱
rule pc_stage;
   let cur = ifs.last;
   Addr p = cur.pc + 4;
   Bool e = cur.epoch;
   if (redirect[1] matches tagged Valid .t) begin
      p = t;
      e = !cur.epoch;
      redirect[1] <= tagged Invalid;
   end
   ifs.enq(PC2IF { pc: p, epoch: e });   // ここでPCが確定
endrule

PCの箱のリセット値は「リセットベクタ−4」です。最初のサイクルに<PC>が+4して、リセットベクタを出します。<PC>専用のpcレジスタやepochレジスタはありません。RISC-V パイプラインプロセッサ 設計方針のブロック図にあるPCの箱が、ifsそのものです。確定したPCとepochは、そこに入っています。

<ID>のwaitは、id_stageの発火条件!idHazそのものです。waitの線も泡も書きません。<ID>が発火しなければidsが満杯のまま残り、<IF>と<PC>はenqできずに止まります。取り消しはハザードより先に判定します（!idKill &&）。これが「キャンセルはwaitに勝つ」という規則にあたります。

mkPipeQは、標準のmkPipelineFIFOに、中のデータレジスタを読み出すlastメソッドを足しただけのものです。

interface PipeQ#(type t);
   method Action enq(t x);
   method t      first;
   method Action deq;
   method t      last;     // 最後にenqされた値（deq後も残っている）
endinterface

module mkPipeQ#(t init)(PipeQ#(t)) provisos (Bits#(t, tSz));
   Reg#(t)    d       <- mkReg(init);
   Reg#(Bool) full[2] <- mkCReg(2, False);   // [0]:deq側, [1]:enq側
   method Action enq(t x) if (!full[1]);
      d <= x;
      full[1] <= True;
   endmethod
   method t first if (full[0]) = d;
   method Action deq if (full[0]);
      full[0] <= False;
   endmethod
   method t last = d;
endmodule

注意点

• 取り消される命令は、捨てられるまでは普通に流れます。そのため、捨てられる前の段（<IF>/<ID>）でアーキテクチャ状態を変えてはいけません。

<IF>で捨てるとき

命令メモリへの要求は<PC>で出しているので、<IF>は捨てる命令でも、メモリの応答を受け取ってから捨てます。そうしないと、要求と応答の対応がずれます。

組合せ回路の経路

<EX>の分岐判定から、<PC>のMuxを通ってIMemのアドレス（<PC>でreq）まで、同じサイクルの組合せ回路でつながります。<IF>と<ID>の取り消しも同じサイクルにつながります。これがクリティカルパスになるなら、redirectや<ID>の比較を1サイクル遅らせます。その場合、分岐ペナルティは3サイクルになります。この形はまだシミュレーションしていません。

<PC>が動けないサイクルのredirect

<IF>がwaitしてPCの箱が満杯なら、enqの暗黙条件によって<PC>のrule自体が発火しません。redirectを「そのサイクルだけ見える線」で渡すと、このサイクルのredirectは誰にも受け取られずに消えます。exEpochはもう反転しているので、以後<PC>が出す命令はすべてepochが合わず、取り消され続けます。

redirectをCReg、つまりレジスタにしているのはこのためです。<EX>が書いた値は、<PC>が実際に命令を出して消すまで残ります。サイクル4に<IF>をwaitさせた場合をbsimで確かめました。

redirectが残っている間は、新しいepochの命令がまだ<PC>から出ていません。そのため次のredirectが重なることはありません。

redirectを出す段が複数ある場合

1bitで足りるという議論は、redirectを出す段が1つであることが前提でした。<MA>での例外や、<ID>でのBTB予測の修正のように、redirectを出す段が増えると、1本のepochでは足りません。

たとえば<MA>で例外が起きたとします。その後ろの<EX>、<ID>、<IF>にいる命令は、すべて取り消す必要があります。ところが<EX>は、<MA>がredirectを出したことを自分のexEpochでは知ることができません。そのため、取り消すべき命令を<EX>がそのまま実行します。その中に分岐があれば、誤ったredirectまで出してしまいます。

そこで、redirectを出す段ごとに1bitのepochを持たせます。命令は(exEpoch, maEpoch)の2bitを運び、各段は自分より後ろの段のepochもすべて比べます。<EX>は2bitとも比べ、<MA>はmaEpochだけを比べます。それぞれのepochは自分の段のredirectでしか反転しないので、1bitで足りる理由は段ごとにそのまま成り立ちます。同じサイクルに2つのredirectが来たら、<PC>は古い命令の方、つまり後ろの段(<MA>)を優先します。この部分は、例外を実装する回で動かして確かめます。

キャンセル信号方式との比較

Pipeline processorの設計(13)では、分岐を<ID>で解決していたので、取り消すのは後ろの1命令（<IF>にいる命令）だけでした。その命令のvalidを落とし（Pipeline processorの設計(19)のC(S+)）、invalidが後段へ流れていきます。

本稿では分岐を<EX>で解決するので、取り消す命令は<IF>と<ID>の2つになります。キャンセル信号でこれを行うなら、<EX>から<IF>と<ID>の両方にキャンセル信号を配り、同じサイクルに2つのvalidを落とすことになります。epoch方式では、段に配るキャンセル信号がありません。命令に1bitを付けて一緒に流し、各段で比べるだけです。段が増えても配線は増えません。

このキャンセル信号方式では、サイクル4の時点で0104と0108が同時に無効になります。epoch方式でも、0104と0108はサイクル4に捨てられます。結果は同じで、分岐ペナルティもどちらも2サイクルです。違いは、キャンセル信号を配る代わりに、各段が自分で「古い命令か」を判定する点です。

前のブログ 次のブログ