命令フェッチウエイト

次に命令フェッチ時に2ウエイトがかかった場合のタイミングを示します。

命令1の<IF>にウエイトが入ると、後続命令を直ちに止める必要があるため、前稿と同様、ウエイト信号は即時に上ステージに伝える(下向き矢印)ように制御します。

図458.2はそれを並べ替えたものです。メリットは図458.1では省略されているパイプラインバブルが見えることです。濃いグレーは初期の無効フラグであり、パイプラインバブルは薄いグレーで示しています。

パイプラインウエイトは上段に向かって即時(同一サイクル内)に流す(上向き矢印)だけでなく、下段に向かってバブルを発生します(右下斜矢印)。下段へは即時ではなくパイプラインに沿って流します。

実装は<IF>で起動するFSMにより実装します。例えば命令キャッシュをFSMで構成すると、キャッシュヒット時は1サイクルで結果が返りますが、キャッシュミス時は複数サイクルのFSMにより、命令がフェッチされます。

前のブログ 次のブログ

パイプラインウエイト

パイプラインの設計も佳境となるのがパイプラインハザードであり、それを実行するのがパイプラインウエイト制御です。本来ウエイトさせるべきタイミングでウエイトされないと、「パイプラインステージが滑る」バグとなります。

パイプラインステージ制御には原則があり、パイプラインステージは増殖してはいけません。パイプラインステージを止める場合は、その出力の更新を止めることでサイクルを繰り返す制御を行い、かつ、後段には無効信号を流す必要があります。

つまり、パイプラインステージ制御信号にはValid信号が必要です。一方パイプラインデータ信号にはValid信号は不要です。パイプラインで無効データが流れても、最後の<WB>で書き込まなければ問題ないためです。

メモリアクセスウエイト

次にロードストア命令の<MA>でのウエイトの場合を示します。

通常のパイプライン図を457.1に示します。命令の実行順に、縦に命令を1, 2, ..., 6と並べています。横軸は時間軸で、箱の中にステージ名が書かれています。命令処理を命令流すなわち、命令ストリームあるいはパイプラインストリームと呼ぶこともあります。

図457.1は例えば命令1のメモリアクセスステージ<MA>でメモリウエイトが2サイクル入った場合の例です。命令1の<MA>にウエイトが入ると、後続命令を直ちに止める必要があるため、ウエイト信号は即時に上ステージに伝える(下向き矢印)ように制御します。

図457.1をパイプラインステージ順に並べ替えたものが図457.2です。図457.1と同様に横軸は時間軸です。箱の中には命令の順番の番号が入っています。こちらのほうが有利なのは、図457.1では省略されているパイプラインバブルが見えることです。バブルは薄いグレーで示しています。初期の無効状態は濃いグレーで示しています。

パイプラインウエイトは上段に向かって即時(同一サイクル内)に流す(上向き矢印)だけでなく、下段に向かってバブルを発生します(右下斜め矢印)。下段へは即時ではなくパイプラインに沿って流します。バブルとは、具体的にはパイプラインのValid信号をインバリデート(無効, false)にすることです。

例えば1の命令が<MA>でウエイトする場合(5クロック目)、パイプラインを下段方向に止めるのではなく、下段は止めずにその代わり無効信号を流します。これは重要なパイプライン制御のテクニックであり、下段も止めてしまうと、誤ったインターロック(お互いに止めあうこと)が発生することがあります。

余談ですが、20?年前に課内でパイプライン制御を説明したとき、先輩のTさんと後輩のK君は「全部止めたらいいんじゃないか」と言いましたが、上記の理由からそれは誤っています。

実装は<MA>で起動するFSMにより実装します。例えばデータキャッシュをFSMで構成すると、キャッシュヒット時は1サイクルでデータが返りますが、キャッシュミス時は複数サイクルのFSMによりデータがフェッチされます。

前のブログ 次のブログ

レジスタフォワーディング

レジスタフォワーディングは単にフォワーディング、またはバイパスと呼ばれることがあります。これは前述のRAWハザードのペナルティ(無駄時間、バブル)を軽減もしくは無化するためのものです。

以下のような命令ストリームがあった時、

1: <PC><IF><ID><EX><MA><WB>
2:         <PC><IF><ID><EX><MA><WB>
3:                  <PC><IF><ID><EX><MA><WB>
4:                           <PC><IF><ID><EX><MA><WB>
5:                                   <PC><IF><ID><EX><MA><WB>

1:のデスティネーションレジスタは<WB>ステージで書き込まれますが、直後の2の命令ストリームの<ID>で読もうとすると、5の命令のタイミングまでウエイトしなければなりません。つまり2、3、4の命令実行時間の$3\tau$が無駄になります。

これを高速化するのがレジスタフォワーディングで、2の命令デコード時に先行命令のデスティネーションレジスタ番号と自分の命令のソースレジスタ番号の比較を行います。この時同じレジスタであれば、デスティネーションレジスタから読み出すのではなく、演算器の出力をレジスタの結果とみなします。1の命令の<EX>の出力確定は2の命令の<ID>のレジスタ読み出しと同一タイミングなので、レジスタフォワーディング制御としては<EX>の出力を<EX>の入力にフィードバックします。

このバイパス機構を設けることで、本来$3\tau$のバブルが発生するところをバブル無しとなり、RAWハザードを解消することができます。

機構的にはソースレジスタとデスティネーションレジスタの番号をパイプラインで流し、番号が前後の命令で一致するかを見る比較器を設け、一致した場合は命令コードが示すレジスタの内容ではなく、演算器の出力パスをマルチプレクサで選択します。

前のブログ 次のブログ

パイプラインステージ

プロセッサに話を戻して、一連の処理を複数のパイプラインステージに分解します。一般的にみられるのは、 ステージを<>で表示する約束として、

• <IF>: 命令フェッチステージ
• <ID>: 命令デコード, レジスタリードステージ
• <EX>: 演算ステージ
• <MA>: メモリアクセスステージ
• <WB>: ライトバックステージ

の5段に分割するものです。

このような5段のパイプラインの説明が一般的ですが、いきなり命令フェッチすることはできないので、実は<IF>の前段にはプログラムカウンタ演算の

• <PC>: PC演算ステージ

が必要になります。<PC>の前はといえば、それはその前の<PC>なので、パイプラインの開始はやはり<PC>からです。命令パイプラインなのでプログラムカウンタが原点です。

従って、<PC><IF><ID><EX><MA><WB>の6段ステージと考えるほうが考えやすいです。

1: <PC><IF><ID><EX><MA><WB>
2:         <PC><IF><ID><EX><MA><WB>
3:                  <PC><IF><ID><EX><MA><WB>
4:                           <PC><IF><ID><EX><MA><WB>

各命令の<PC>は通常PCの+4インクリメントを実行します。ここで1の命令が無条件相対分岐命令だった時、分岐命令とオフセットが判明するのが1の<ID>の最後です。従って、それからPC計算を実行すれば、分岐先は4の命令ストリームとなります。

マイクロアーキテクチャによっては、IFの中でPC計算を実施する場合もあります。その場合は<PC>は<IF>に隠蔽され5段パイプラインとなります。このあたりは、マイクロアーキテクチャの考え方で、32bitの加算に$1\tau$かかるのであれば、<PC>も$1\tau$かかるのが妥当ということになります。

投機的実行

従って1の分岐命令は3サイクル命令となります。つまり1の分岐命令のレイテンシは$3\tau$となってしまうので、裏技的な手法を使います。それは、1の命令を<IF>でフェッチしたら、次の<ID>のデコードと同時に投機的に分岐命令だと思って分岐先を計算します。こうすれば分岐先は3の命令から始めることができ、分岐命令のレイテンシは$2\tau$となります。この場合、ほとんどは分岐命令でないので、その場合は<PC>で実行した投機的な実行結果を捨てます。

<PC>では本来次の命令アドレスであるPC+4か、または分岐命令の場合はPC+オフセットのいずれかを計算すれば良いのですが、このように、常に両方計算することで高速化を図ります。

パイプラインプロセッサにはこのような投機的な(ある意味無駄な)実行は良く使われ、例えばレジスタリードも同様です。<ID>でリードするのですが、本来はレジスタ演算命令の場合だけリードすれば良く、レジスタをリードしない命令でレジスタをリードする必要はありません。

投機的実行の場合は<ID>と同時にレジスタリードを行い、<ID>の完了後に不要だった場合は実行結果を捨てます。このためにレジスタリードのための命令のビットフィールドは固定されています。

前のブログ 次のブログ

プロセッサパイプライン

本稿ではコンピュータの設計が主題なので、社内メール処理ではなく、プロセッサパイプラインについて解説します。プロセッサの命令にはRISC形式、CISC形式が存在しますが、ここではRISC形式を取り上げます。

RISCとCISC

このRISC/CISCの別は、実はパイプライン構造から発しており、パイプラインステージ中にメモリアクセスが1回のものをRISC、2回以上のものをCISCと呼びます。元々はメモリ上のデータを書き換えるのがプロセッサの役目なので、CISCが先に発明されたのですが、パイプライン化を考えた場合にパイプラインステージ中に複数のメモリアクセスステージが存在すると、パイプラインハザードが起こりやすくなるのが欠点でした。

これに対して演算をレジスタに限り、メモリアクセスをロードストアのみに限定したのがRISCです。パイプラインステージ中にメモリアクセスが1か所で固定されているため、メモリアクセスにはRAWハザードがありません。レジスタのRAWハザードのみを考慮すれば良いことになります。

RISCのメリット・デメリット

RISCのメリットは種々あり、

• 32bit固定長命令によるデコードの簡略化
• レジスタフィールドの固定により、デコードせずにソースレジスタの読み出しが可能
• 複雑な命令の排除による命令デコーダの高速化

等がありますが、その根本はメモリ演算の廃止によるものです。メモリアクセスはロードストアのみと割り切り、演算はレジスタを対象とすることでパイプライン制御を単純化し、上記の特徴も併せて高速化が可能となりました。

一方で命令長が32bit固定でかつ複雑な命令を単純な命令の組み合わせで実行することから、命令コード効率はあまり良くありません。ワークステーション等では問題なかったこの欠点は、16/32bit混合の導入により組み込み向けの応用では改善が行われています。

前のブログ 次のブログ

パイプラインハザード

それでは100段でも1,000段でも細かく切れば性能は100倍、1,000倍になるかというと、そう単純には行きません。それには複数の理由があります。

• パイプラインステージは同じレイテンシ$\tau$である必要がある。
• ステージ間の箱(パイプラインレジスタ)によるレイテンシ($\alpha$)が増加する
• パイプラインハザードの存在により、性能向上できない

ひとつの大きな処理の中を均等に細かい時間間隔の$\tau$で切るのは、ハードウエア構成上限界があります。また、パイプラインレジスタのレイテンシの追加は、性能低下原因となります。最後にパイプラインハザードの存在により、後続ステージの待ち合わせが発生し、パイプライン中に隙間(バブル)が生まれます。これも性能低下原因となります。

RAWハザード

パイプラインハザードのひとつにRAW(Read After Write)ハザードがあります。これは、パイプラインステージの前半、例えばAの処理において使用する封筒に、Cの処理において投函される封筒が必要だったとします。すると、処理としてはCが終了しないとAが開始できませんが、パイプラインステージ中ではAのほうが先になっているので、図453.1の左のようには2番目の処理が開始できず、図453.1の右のように、$2\tau$のバブル(＝無駄サイクル)が発生してしまいます。これをパイプラインハザードと呼びます。

前のブログ 次のブログ

機械の場合

人間であれば器用に3つの処理を一人で実行することができますが、コンピュータは機械なので一つのことしかできません。つまり、A専用、B専用、C専用の3つの機械を並べて処理することになります。

• 社内メール封筒を取りに行く ----- A専用機
• 宛名を書いて書類を入れて封をする ----- B専用機
• 社内メール投函箱に投函しに行く ----- C専用機

レイテンシは前稿の3人がかりと同じように$3\tau$で、スループットはその逆数である$\frac{1}{3\tau}$です。これを表452.1にまとめます。

パイプライン化

さて、ここでシステムのスループット(システム性能)は$\frac{1}{3\tau}$ですが、その向上を考えてみます。

性能向上のためレイテンシ短縮を考えると、$3\tau$以下にするのは困難です。ところが、AとB、BとCの間に箱を置いて、$3\tau$ではなく、$\tau$毎に処理を入力したらどうでしょうか。ちょうどバケツリレーのように$\tau$毎に処理が可能です。

スループットから見てみましょう。元々A, B, Cの機械単体でのスループットは$\frac{1}{\tau}$だったのですが、システムで組み合わせると$\frac{1}{3\tau}$のように33%に低下していました。

例えばA機械は、BとCが働いているときには遊んでいたわけです。これを間に箱を入れて切り離すようにした結果、レイテンシはほとんど変わらずに、スループットは3倍の100%に向上しました。つまり、A, B, Cそれぞれの機械の能力を100%出し切ることができたわけです。

このように、パイプライン化はあまりコストをかけることなく、性能を大幅に向上できる特長があります。一般的には、全体を$n$ステージのパイプラインで構成すれば、レイテンシはあまり変わらず$n\tau+\alpha$と若干増加するだけです。一方、スループット(性能)を$n$倍のように大幅に引き上げることができます。

前のブログ 次のブログ

パイプラインとは

ノイマン型計算機の進歩の中で命令パイプライン技術が考案されました。パイプライン制御はコンピュータの性能向上の手法の重要な技術のひとつです。詳細は命令パイプライン制御を見てください。

本稿ではパイプライン制御を解説していきます。このパイプライン制御を理解するには、まずスループットとレイテンシについて、正しく理解する必要があります。

スループットとレイテンシ

まずスループットとは、Wikipediaにもあるように、単位時間当たりの処理量です。コンピュータの処理能力は上げるほうが良いので、スループットを上げることを考えます。

次にレイテンシとは、端的に言えば入力から出力までの処理時間のことで、普通はその逆数がスループットになります。従って、処理能力を上げるにはレイテンシを小さくすることを考えます。

ところが、レイテンシを短くするのは非常に大変です。単純な仕事で見てみましょう。会社で社内メールを出すのに、

• 社内メール封筒を取りに行く ----- A処理と呼ぶ
• 宛名を書いて書類を入れて封をする ----- B処理と呼ぶ
• 社内メール投函箱に投函しに行く ----- C処理と呼ぶ

上記のA～C処理の3ステップがあるものとします。どれも同じ時間$\tau$だけかかるとすれば、レイテンシは$3\tau$です。一人の人間がフルに働いても$3\tau$に1通しか処理できません。処理能力であるスループットは、上記から$\frac{1}{3\tau}$となります。

3人でやってもレイテンシは$3\tau$と変わりません。Cを実行するにはBが完了していなければならない依存性があり、Bを実行するにはAが完了していなければならない依存性があるからです。これがレイテンシを短縮するのが困難な理由です。

前のブログ 次のブログ

だいぶ前の記事ですが、テストベンチのBSVと、モジュールのBSVからVerilogを生成し、Verilogシミュレーションを実施しました。BSVではテストベンチにおいてクロックとリセットが自動生成され、暗黙的にモジュールに供給されます。一方、Verilogでは明示的にテストベンチにクロックとリセットを供給する必要があります。前の記事では、テストベンチ内にその処理を行う記述をインクルードする方法を用いました。

ここでは、最上位からそれらの信号を供給する手法をとります。これにより、よりスマートにVerilogシミュレーションが実行できます。まず、原始最上位ファイルを用意します。最上位からはテストベンチを呼び出しています。

最上位ファイル:mkTop.v

module mkTop () ;
   /*AUTOREGINPUT*/
   mkTb Tb_inst(/*AUTOINST*/);
  initial begin
    RST_N = 1'b0;
    #30;
    RST_N = 1'b1;
  end
  initial begin
    CLK = 1'b0;
    forever begin
       #5 CLK = ~CLK;
    end
  end
endmodule // mkTop  

これに対して、Verilog-modeのオートコネクションコマンドであるC-c C-aを用いてポートの追加を行えば、

最上位ファイル:mkTop.v

module mkTop () ;
   /*AUTOREGINPUT*/
   // Beginning of automatic reg inputs (for undeclared instantiated-module inputs)                
   reg                  CLK;                    // To Tb_inst of mkTb.v                            
   reg                  RST_N;                  // To Tb_inst of mkTb.v                            
   // End of automatics                                                                            
   mkTb Tb_inst(/*AUTOINST*/
                // Inputs                                                                          
                .CLK                    (CLK),
                .RST_N                  (RST_N));
  initial begin
    RST_N = 1'b0;
    #30;
    RST_N = 1'b1;
  end
  initial begin
    CLK = 1'b0;
    forever begin
       #5 CLK = ~CLK;
    end
  end
endmodule // mkTop              

のように、テストベンチに対してクロックとリセットが接続されます。

最上位、テストベンチ、モジュールを結合した実行ファイルを生成します。エラーが出ることもなく実行ファイルが生成され、実行ファイルによりVerilogシミュレーションを実行すれば、

$ iverilog mkTop.v mkTb.v mkFibOne.v -o mkFibOne.exev
$ ./mkFibOne.exev
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946

このように、正しくVerilogシミュレーションが行われ、前記事と同じ結果となります。

結論としては、この記事のように自動結合を使用すれば、前記事のようにincludeを埋め込む必要はありませんでした。

追記：bscによりverilogをリンクし+bscvcd=verilog.vcdとフラグをつけることでvcdダンプができることがわかりました。これを使えばmkTop.vもiverilogも不要となります。

前のブログ 次のブログ