Posts Tagged with "pipeline processor"

既に発行済みのブログであっても適宜修正・追加することがあります。
We may make changes and additions to blogs already published.
posted by sakurai on October 28, 2022 #541

<PC>の必要性

従来例を再掲します。作成しようとするパイプラインロジックは大略、前の図540.1のとおりです。ただし図540.1では<PC>が明示されていません。

図%-%.1
図540.1 あるRISC-Vプロセッサのパイプライン図(再掲)

次の命令ストリームの起点であるPCは、基本的に

  1. 分岐が無ければ(有っても投機的に数命令は実行)、現PC+4
  2. PC相対分岐が有ればPC+オフセット
  3. 絶対分岐の場合はその値

を次のPCにセットします。この他にも割り込み、例外処理等で新PCを演算し、次のPCにセットします。これを<PC>を意識した図に書き直すと、図541.1のように判りやすい図となります。図540.1のように、PC演算器やレジスタが窮屈に<IF>の中に折れ曲がることは無く、ストレートフォワードに描かれています。<PC>の入力が<PC>であることも図541.1を見れば明らかです。

図%%.1
図541.1 <PC>の考え方に基づき書き直したパイプライン図

図541.1では分岐の場合は<EX>の結果レジスタがPCであることから元の<EX>と分岐先<PC>が重なり、その次のステージが分岐先<IF>となることが良くわかります。クロックベースが原則のパイプラインを記号で書けば、

   <PC><IF><ID><EX><WB>
          <PC><IF><ID><EX><WB>

となります。分岐先のPC計算を分岐元のEXで代行している様子が良く分かります。

一方、図540.1では<EX>の後にPCレジスタが入り、その次に<IF>ステージとなるので、記号で書くと、

   <IF><ID><EX><WB>
          <IF><ID><EX><WB>

となり、<IF>が湧き出す意味が不明です。<IF>の入力レジスタがPCで、分岐命令の<EX>でそれを生成しているのだからという説明になると思いますが、であればPCを明示したほうが分かりやすいのは言うまでもありません。

逆にPCの生成も含めたパイプラインを理解してしまえば頭の中でできるため、取り立てて<PC>の必要性は感じなくなるので、不思議とも思わないようになりますが、教育的とは言えません。そもそも最も重要なPCの更新ステージはどこなのかが図示されていません。これでは分岐命令の高速化、例えばBTB等による<PC>の物量増加も、どのステージの話なのか理解しづらくなります。

<PC>の制御法

<PC>の必要性が理解できたところで、過去記事でパイプライン制御論理を示しました。<PC>の上流が<PC>だからといって上流に出力するwait信号を自分自身に入れると永久にストールするので、自分自身に入れてはいけません。

また、図示されていませんが、PCレジスタ自体も同じパイプライン制御論理によりパイプラインを流します。その理由は、例外の際には分岐が発生しますが、戻りアドレスをスタックに格納します。その戻りアドレスを上記PCパイプラインから適宜取得するためです。


左矢前のブログ 次のブログ右矢

posted by sakurai on October 27, 2022 #540

PCステージ

PCステージ(<PC>)を設計します。と言うとなじみがありませんね。一般には存在しないステージなので。以降ではステージ記号を次のように定義します。例:PCステージ:=<PC>

一般にはパイプライン図は<IF>から始まっています。例えば図540.1のように。PCレジスタは<IF>の入力レジスタとして描かれています。良く見ると、本来の<PC>の演算器や結果レジスタは折り曲げられて、窮屈な恰好をしています。

図%%.1
図540.1 あるRISC-Vプロセッサのパイプライン図(引用元)

図540.2の黄色のステージ記号及び点線は弊社で追加しました。FDレジスタとは<IF>と<ID>の間のステージなので、<IF>の結果レジスタです。つまりFDレジスタの左側は全て<IF>です。この図でもPCレジスタは窮屈に折り曲げられています。

図%%.1
図540.2 あるRISC-Vプロセッサのパイプライン図(引用元)

この図のように<IF>の中にPCレジスタが書かれています。これが変であることに気づかれたでしょうか。パイプラインプロセッサは、パイプラインレジスタにより、組み合わせ回路の結果を次々に受けていくバケツリレー式であり、本来ステージの内部は組み合わせ回路で構成され、レジスタは無いはずです。

それでは<IF>の入力である命令アドレスはどこのステージで生成されるのでしょうか?それが<PC>です。つまり一般の図ではPCは<IF>の入力レジスタのように描かれていますが、実は他のステージと同様、<PC>の結果レジスタです。こう考えるとパイプラインの各ステージが統一的に理解できます。

例えば分岐命令では分岐先アドレス計算をする必要があり、それは必ず<ID>の後になります。図540.2にもPC calculationとありますが、それがパイプライン中の2個目の<PC>です。そして分岐条件が確定した後に<IF>が実行されるので、<PC>は明示したほうが判りやすいです。

一般的に<PC>が無視される理由としては、有名な教科書がIF, ID, EX, MEM, WBの5段で書かれている、からなのかもしれませんが、本来は

<PC><IF><ID><EX><MA><WB>

の6段パイプです。このことは過去記事でも指摘しています。

次の質問です。<PC>の前のステージは何でしょうか?答えは<PC>です。分岐しない限り<PC>は次の<PC>を生成し、1サイクル毎に次々にストリームを生み出します。

一方、例えば分岐命令等のようにパイプラインの途中に<PC>が出現することがあり、複数現れる場合でも命令ストリームの開始PCの計算ですから、いきなり別の命令ストリームの<IF>が現れるよりは判りやすいと思います。無から有は湧いてきません。

割り込みや例外を考える時には一層重要です。割り込みレベルやマスクや例外の種類等の情報を総合して、まずPCがどうなるかを決定します。PCさえ確定すれば、後は<IF>以降のパイプラインを普通に流せば良いだけです。つまり常に<PC>が命令ストリームの起点となります。

本稿で述べたことはエンジニアとしては意識しなくても、設計できる(かもしれない)し、見方を変えて設計が変わるわけではない(かもしれない)ので、哲学に属する話かもしれませんが、設計思想として大事な話なので強調しました。


左矢前のブログ 次のブログ右矢

posted by sakurai on October 25, 2022 #536

デコーダのソースの一部を示します。

genRules(
   switch(in_instr,
      when(pat(n(7'b0000000), v, v, n(3'b000), v, n(7'b0110011)), fadd),
      when(pat(n(7'b0100000), v, v, n(3'b000), v, n(7'b0110011)), fsub),
      when(pat(               v, v, n(3'b000), v, n(7'b0010011)), faddi),
      when(pat(n(7'b0000000), v, v, n(3'b111), v, n(7'b0110011)), fand),
      when(pat(n(7'b0000000), v, v, n(3'b110), v, n(7'b0110011)), ffor),
      when(pat(n(7'b0000000), v, v, n(3'b100), v, n(7'b0110011)), fxor),
      when(pat(               v, v, n(3'b111), v, n(7'b0010011)), fandi),
      when(pat(               v, v, n(3'b110), v, n(7'b0010011)), fori),
      when(pat(               v, v, n(3'b100), v, n(7'b0010011)), fxori),
      when(pat(               v, v, n(3'b010), v, n(7'b0000011)), flw),
      when(pat(            v, v, v, n(3'b010), v, n(7'b0100011)), fsw),
      when(pat(n(7'b0000000), v, v, n(3'b001), v, n(7'b0110011)), fsll),
      when(pat(n(7'b0000000), v, v, n(3'b101), v, n(7'b0110011)), fsrl),
      when(pat(n(7'b0100000), v, v, n(3'b101), v, n(7'b0110011)), fsra),
      when(pat(n(7'b0000000), v, v, n(3'b001), v, n(7'b0010011)), fslli),
      when(pat(n(7'b0000000), v, v, n(3'b101), v, n(7'b0010011)), fsrli),
      when(pat(n(7'b0100000), v, v, n(3'b101), v, n(7'b0010011)), fsrai),
      when(pat(n(7'b0000000), v, v, n(3'b010), v, n(7'b0110011)), fslt),
      when(pat(n(7'b0000000), v, v, n(3'b011), v, n(7'b0110011)), fsltu),
      when(pat(               v, v, n(3'b010), v, n(7'b0010011)), fslti),
      when(pat(               v, v, n(3'b011), v, n(7'b0010011)), fsltiu),
      when(pat(v, v, v, v, n(3'b000), v, v, n(7'b1100011)), fbeq),
      when(pat(v, v, v, v, n(3'b001), v, v, n(7'b1100011)), fbne),
      when(pat(v, v, v, v, n(3'b100), v, v, n(7'b1100011)), fblt),
      when(pat(v, v, v, v, n(3'b101), v, v, n(7'b1100011)), fbge),
      when(pat(v, v, v, v, n(3'b110), v, v, n(7'b1100011)), fbltu),
      when(pat(v, v, v, v, n(3'b111), v, v, n(7'b1100011)), fbgeu),
      when(pat(v, v, v, v, v, n(7'b1101111)), fjal),
      when(pat(               v, v, n(3'b000), v, n(7'b1100111)), fjalr),
      when(pat(               v, v, n(7'b0110111)), flui),
      when(pat(               v, v, n(7'b0010111)), fauipc),
      when(pat(               v, v, n(3'b001), v, n(7'b1110011)), fcsrrw),
      when(pat(               v, v, n(3'b101), v, n(7'b1110011)), fcsrrwi),
      when(pat(               v, v, n(3'b010), v, n(7'b1110011)), fcsrrs),
      when(pat(               v, v, n(3'b110), v, n(7'b1110011)), fcsrrsi),
      when(pat(               v, v, n(3'b011), v, n(7'b1110011)), fcsrrc),
      when(pat(               v, v, n(3'b111), v, n(7'b1110011)), fcsrrci),
      when(pat(n(25'b0), n(7'b1110011)), fecall)
   ) // switch
);

これは1ステップ目のデコーダステップであり、ここでビットパターン、例えばaddi命令とのマッチが取れれば、2ステップ目として個別の関数、例えばfaddiが呼び出されます。一例であるfaddiを示せば、

function Action faddi(Bit#(12) imm, Bit#(5) rs1, Bit#(5) rd) = 
   action
      Int#(32) immSext = signExtend(unpack(imm));
      if (immSext == 0)
         $display("time %4t -   mv\t%s,%s", $time, regname(rd), regname(rs1));
      else if (rs1 == 0)
         $display("time %4t -   li\t%s,%0d", $time, regname(rd), immSext);
      else
         $display("time %4t -   addi\t%s,%s,%0d", $time, regname(rd), regname(rs1), immSext);
   endaction;

RISC-Vにおいてaddi命令はイミディエイトがゼロの場合はmv命令として使用され、逆にソースレジスタにゼロレジスタを指定すれば、イミディエイトロード(li)命令として働きます。これらはプロセッサの設計的には不要な処理ですが、逆アセンブラのシンタックスシュガーとして実装しました。

2ステップ目の処理として、各種関数を命令数だけ並べる必要があります。


左矢前のブログ 次のブログ右矢

posted by sakurai on October 24, 2022 #535

BSV実行結果(ハードウェアからの出力)と逆アセンブルリストをサイドバイサイドに並べた図を535.1に示します。分岐関係を除いて一致していることが分かります。BSV実行出力にアドレスやデータを表示することは簡単ですが、逆アセンブラを作成しているわけではないので、それらの表示機能は実装していません。

図%%.1
図535.1 実行結果と逆アセンブルリスト

この後も「はじめてのCPU自作」にあるようにECALLやCSR操作命令等を実装し、ひととおりriscv-testが通るデコーダまで作成が完了しました。ところで論理合成ツールには論理圧縮機能が含まれるため、出力されたデコーダ論理を合成前に圧縮する必要はありません。


左矢前のブログ 次のブログ右矢

posted by sakurai on October 21, 2022 #534

コンパイルしたオブジェクトファイルの逆アセンブルリストは以下のとおりです。

図%%.1
図534.1 逆アセンブルリスト

これを「ハードウェアインタプリター」にかけたら以下のような実行結果となりました。

図%%.2
図534.2 インタプリター実行結果

addi命令のイミディエイトをゼロにすることでmv命令としたり、逆にレジスタをゼロレジスタとすることでli命令としたり、「インタプリター」の出力を細工し、逆アセンブルリストと合わせています。ただし、PCを実装していないので、PC相対命令のラベルは一致していません。このようにPC相対を除き、逆アセンブル結果とほぼ合わせることができました。


左矢前のブログ 次のブログ右矢

posted by sakurai on October 20, 2022 #533

「ハードウェアインタプリター」に食わせる機械語列が必要です。そこで、この記事を参考に、Fibonacciプログラムをコンパイルし機械語化しました。試みにFibonacciが通るための「インタプリター」を書いていきます。前述のとおりこの「インタプリター」は実行ステージが逆アセンブル相当の表示をするだけのものです。

入力するFibonacciのソースは以下のように短いプログラムです。

fibo.c:

int fib(int n) {
  if(n <= 1) return 1;
  return fib(n-1) + fib(n-2);
}
int main() {
  fib(10);
  for(;;) {}
  return 0;
}

これをクロスコンパイルし、BSVの入力とします。シーケンサの自動生成を利用して1サイクル毎に、命令デコーダに命令を供給します。

Stmt main = seq
    instr <= 32'h074000ef;
    instr <= 32'hfe010113;
    instr <= 32'h00112e23;
    instr <= 32'h00812c23;
    instr <= 32'h00912a23;
    instr <= 32'h02010413;
    instr <= 32'hfea42623;
    instr <= 32'hfec42703;
    instr <= 32'h00100793;
    instr <= 32'h00e7c663;
    instr <= 32'h00100793;
    instr <= 32'h0300006f;
    instr <= 32'hfec42783;
    instr <= 32'hfff78793;
    instr <= 32'h00078513;
    instr <= 32'hfc9ff0ef;
    instr <= 32'h00050493;
    instr <= 32'hfec42783;
    instr <= 32'hffe78793;
    instr <= 32'h00078513;
    instr <= 32'hfb5ff0ef;
    instr <= 32'h00050793;
    instr <= 32'h00f487b3;
    instr <= 32'h00078513;
    instr <= 32'h01c12083;
    instr <= 32'h01812403;
    instr <= 32'h01412483;
    instr <= 32'h02010113;
    instr <= 32'h00008067;
    instr <= 32'hff010113;
    instr <= 32'h00112623;
    instr <= 32'h00812423;
    instr <= 32'h01010413;
    instr <= 32'h00a00513;
    instr <= 32'hf7dff0ef;
    instr <= 32'h0000006f;
endseq;

今回はまだデコーダのテストだけなので、PCは実装していません。


左矢前のブログ 次のブログ右矢

posted by sakurai on October 18, 2022 #532

図532.1にBSV版のBitpatのREADMEに掲載されていた使用例を示します。

図%%.1
図532.1 BSVのBitpat関数

挙げられた例はちょうどRISC-Vの命令パターンに一致しており、add命令とaddi命令のデコード部分を示したものです。この要領で、次々に他の命令を実装していくことができます。

本ライブラリの動作は以下の2ステップとなっています。

  1. whenの中のパターンマッチでは可変部をvで表し、固定部をnとビットパターンで記述します。vの幅を指定しないで良いのは使いやすそうです。whenの最後に識別した機能を解釈するための関数名を記述します。
  2. マッチした後に呼ばれる関数では、可変部のみを変数で受け(固定部は捨てる)、処理を実行します。結局vの幅は意識しなければなりません。

このように最初に固定部、次に可変部という考え方に慣れる必要があります。最初は使いにくいと感じましたが、慣れれば気にならないのかもしれません。

プロセッサ設計と言ってもパイプラインでなければ、見方を変えれば、RISC-V機械語のインタプリターをHDLで作成するだけなので、それほど難しいことではありません。ひとつずつデコードし、対応する処理を実装していくだけです。この「ハードウェアインタプリター」の1段目はデコードステップで、2段目は実行ステップになります。


左矢前のブログ 次のブログ右矢

RISC-Vプロセッサの設計

posted by sakurai on October 17, 2022 #531

「はじめてのCPU自作」という本を購入したので、これを参考にRISC-Vプロセッサを設計します。ただし、この本ではChiselベースとなっていますが、本稿ではBSVベースとします。またパイプラインプロセッサの経験があるため、最初からパイプラインプロセッサを設計します。

さて、この本を読んでいたらChisel(だかScalaだか)にはBitpatという便利な機能があるようです。

図%%.1
図531.1 ChiselのBitpat関数

命令デコーダを書くのに便利そうなので、BSVにもないのか調べたら、GithubにBitpatという似たようなものがありました。これはAlexandre Joannouさんが作成されたものであり、Readmeには以下のように書いています。

BitPat BitPat is a bit-string pattern matching library for Bluespec, inspired by Morten Rhiger's "Type-Safe Pattern Combinators".

BSVにおいてのパターンマッチライブラリとのことです。便利そうなのでRISC-Vの命令デコーダに採用することにします。


左矢前のブログ 次のブログ右矢

Pipeline processorの設計(19)

posted by sakurai on March 1, 2022 #469

パイプライン制御の一般化

前項までの議論を一般化すれば、ステージSにおいての前段へのウエイト信号$\mathrm{W_{S-}}$と後段への有効信号$\mathrm{V_{S+}}$は

$$ \begin{eqnarray} \mathrm{W_{S-}}&=&\mathrm{W_S }\cup\mathrm{W_{S+}}\\ \mathrm{V_{S+}}&=&N(\mathrm{!W_S }\cup\mathrm{W_{S+}})\ \cap\ !\mathrm{C_{S+}} \end{eqnarray} \tag{469.1} $$ ただし、 $$ \mathrm{W_{S+}}: 下位ステージS+からSへのウエイト信号\\ \mathrm{C_{S+}}: 下位ステージにおけるキャンセル信号\\ N(): 時相論理、次のクロックサイクルの値 $$ とする。

何事も分かってしまえば簡単なのですが、パイプライン制御の秘密は、この論理469.1にあります。


左矢前のブログ 次のブログ右矢

posted by sakurai on February 28, 2022 #468

パイプライン制御の無効化論理

図%%.1
図468.1 CV32E40Pパイプライン図(再掲)

一方、後段にバブルを流すinvalidate信号は、EXWBレジスタのC(lear)信号ですが、やや冗長になっています。EXWB.C信号に(467.1)を代入し、ドモルガンの定理を用いて整理すれば、 $$ \require{cancel} \begin{eqnarray} \text{EXWB.C}&=&\text{wb_ready }\cap\text{!ex_valid}\\ &=&\text{wb_ready }\cap\text{(!granted }\cup\text{!wb_ready)}\\ &=&\text{(wb_ready }\cap\text{!granted) }\cup\bcancel{\text{(wb_ready }\cap\text{!wb_ready)}}\\ &=&\text{wb_ready }\cap\text{!granted} \end{eqnarray} \tag{468.1} $$ 使用ゲートは同じで、配線を繋ぎ変えるだけで1段論理になるので、2段通すのは若干無駄な論理のように見えます。論理合成を用いれば上記のように最適化されるでしょうけど。

図468.2に修正後の回路を示します。

図%%.2
図468.2 論理修正後パイプライン制御論理

前稿等で検討したように、パイプラインバブルは後段へ流すものですから、当該ステージ、この場合は<EX>にウエイト要因があり($=\text{!granted}$)、かつ後段である<WB>からウエイトが来ていない($=\text{wb_ready}$)ときに限り、後段を無効化する論理となり、(468.1)は正しいです。そして、この無効化信号は、パイプラインストリームのキャンセルにも用いられます。

パイプライン制御の有効論理

EXWB.Cの反転論理である<EX>有効信号を新たに$ex\_valid$とすれば、 $$ \require{cancel} \begin{eqnarray} ex\_valid&=&\text{!wb_ready }\cup\text{granted }\\ &=&wb\_wait\text{ }\cup\text{ }!exs\_wait \end{eqnarray} \tag{468.2} $$ となります。


左矢前のブログ 次のブログ右矢


ページ: