第7章
CPUのパイプライン化
これまでの章では、同時に1つの命令を実行するCPUを実装しました。高機能なCPUを実装するのは面白いですが、プログラムの実行が遅くてはいけません。機能を増やす前に、一度性能のことを考えてみましょう。
7.1 CPUの速度
CPUの性能指標は、例えば消費電力や実行速度が考えられます。本章では、プログラムの実行速度を考えます。
7.1.1 CPUの性能を考える
性能の比較にはクロック周波数やコア数などが用いられますが、プログラムの実行速度を比較する場合、プログラムの実行にかかる時間のみが絶対的な指標になります。プログラムの実行時間は、次のような式で表せます(図7.1)
それぞれの用語の定義は次の通りです。
- CPU時間 (CPU time)
- プログラムの実行のためにCPUが費やした時間
- 実行命令数
- プログラムの実行で実行される命令数
- CPI (Clock cycles Per Instruction)
- プログラム全体またはプログラムの一部分の命令を実行した時の1命令当たりの平均クロック・サイクル数
- クロック周波数 (clock rate)
-
クロック・サイクル時間(clock cycle time)の逆数
クロック・サイクル時間は、クロックが0
→1
→1
になる周期のこと
今のところ、CPUは命令をスキップしたり無駄に実行することはありません。そのため、実行命令数は、プログラムを1命令ずつ順に実行していった時の実行命令数になります。
CPIを計測するためには、何の命令にどれだけのクロック・サイクル数がかかるかと、それぞれの命令の割合が必要です。今のところ、メモリにアクセスする命令は3 ~ 4クロック、それ以外の命令は1クロックで実行されます。命令の割合は考えないでおきます。
クロック周波数は、CPUの回路のクリティカルパスの長さによって決まります。クリティカルパスとは、組み合わせ回路の中で最も大きな遅延を持つ経路のことです。
7.1.2 実行速度を上げる方法を考える
CPU性能方程式の各項に注目すると、CPU時間を減らすためには、実行命令数を減らすか、CPIを減らすか、クロック周波数を増大させる必要があります。
実行命令数に注目する
実行命令数を減らすためには、コンパイラによる最適化でプログラムの命令数を減らすソフトウェア的な方法と、命令セットアーキテクチャ(ISA)を変更することで必要な命令数を減らす方法が存在します。どちらも本書の目的とするところではないので、検討しません*1。
[*1] 他の方法として、関数呼び出しやループをCPU側で検知して結果を保存して利用することで実行命令数を減らす手法があります。この手法はずっと後の章で検討します。
CPIに注目する
CPIを減らすためには、例えばどの命令も1クロックで実行してしまうという方法が考えられます。しかし、そのために論理回路を大きくすると、その分クリティカルパスが長くなってしまう場合があります。また、1クロックに1命令しか実行しない場合、どう頑張ってもCPIは1より小さくなりません。
CPIをより効果的に減らすためには、1クロックで1つ以上の命令を実行開始し、1つ以上の命令を実行完了すればいいです。これを実現する手法として、スーパースカラやアウトオブオーダー実行が存在します。これらの手法はずっと後の章で解説、実装します。
クロック周波数に注目する
クロック周波数を増大させるには、クリティカルパスの長さを短くする必要があります。
今のところ、CPUは計算命令を1クロック(シングルサイクル)で実行します。例えばADD命令を実行するとき、FIFOに保存されたADD命令をデコードし、命令のビット列をもとにレジスタの値を選択し、ALUで足し算を実行し、その結果をレジスタにライトバックします。これらを1クロックで実行するということは、命令が保存されている32ビットのレジスタと32*64ビットのレジスタファイルを入力に、64ビットのADD演算の結果を出力する組み合わせ回路が存在するということです。この回路は大変に段数の深い組み合わせ回路を必要とし、長いクリティカルパスを生成する原因になります。
クロック周波数を増大させるもっとも単純な方法は、命令の処理をいくつかのステージ(段)に分割し、複数クロックで1つの命令を実行することです。複数のクロック・サイクルで命令を実行することから、この形式のCPUはマルチサイクルCPUと呼びます。
命令の処理をいくつかのステージに分割すると、それに合わせて回路の深さが軽減され、クロック周波数を増大させられます。
図7.2では、1つの命令を3クロック(ステージ)で実行しています。3クロックもかかるのであれば、CPIが3倍になり、CPU時間が増えてしまいそうです。しかし、処理を均等な3ステージに分割できた場合、クロック周波数は3分の1になる*2ため、それほどCPU時間は増えません。
[*2] 実際のところは均等に分割することはできないため、Nステージに分割してもクロック周波数はN分の1になりません
しかし、CPIがステージ分だけ増大してしまうのは問題です。この問題は、命令の処理を、まるで車の組立のように流れ作業で行うことで緩和できます(図7.3)。このような処理のことを、パイプライン処理と呼びます。
本章では、CPUをパイプライン化することで性能の向上を図ります。
7.1.3 パイプライン処理のステージを考える
具体的に処理をどのようなステージに分割してパイプライン処理を実現すればいいでしょうか?これを考えるために、第3章の最初で検討したCPUの動作を振り返ります。第3章では、CPUの動作を次のように順序付けしました。
- PCに格納されたアドレスにある命令をフェッチする
- 命令を取得したらデコードする
- 計算で使用するデータを取得する (レジスタの値を取得したり、即値を生成する)
- 計算する命令の場合、計算を行う
- メモリにアクセスする命令の場合、メモリ操作を行う
- 計算やメモリアクセスの結果をレジスタに格納する
- PCの値を次に実行する命令のアドレスに設定する
もう少し大きな処理単位に分割しなおすと、次の5つの処理(ステージ)を構成できます。ステージ名の後ろに、それぞれ対応する上のリストの処理の番号を記載しています。
- IF (Instruction Fetch) ステージ (1)
-
メモリから命令をフェッチします。
フェッチした命令をIDステージに受け渡します。 - ID (Instruction Decode) ステージ (2、3)
-
命令をデコードし、制御フラグと即値を生成します。
生成したデータをEXステージに渡します。 - EX (EXecute) ステージ (3、4)
-
制御フラグ、即値、レジスタの値を利用し、ALUで計算します。
分岐判定やジャンプ先の計算も行い、生成したデータをMEMステージに渡します。 - MEM (MEMory) ステージ (5、7)
-
メモリにアクセスする命令とCSR命令を処理します。
分岐命令かつ分岐が成立する、ジャンプ命令である、またはトラップが発生するとき、 IF、ID、EXステージにある命令を無効化して、ジャンプ先をIFステージに伝えます。 メモリのロード、CSRの読み込み結果をWBステージに渡します。 - WB (WriteBack) ステージ (6)
- ALUの演算結果、メモリやCSRの読み込み結果など、命令の処理結果をレジスタに書き込みます。
MEMステージではジャンプするときにIF、ID、EXステージにある命令を無効化します。これは、IF、ID、EXステージにある命令は、ジャンプによって実行されない命令になるためです。パイプラインのステージにある命令を無効化することを、パイプラインをフラッシュ(flush)すると呼びます。
IF、ID、EX、MEM、WBの5段の構成を、5段パイプライン(Five Stage Pipeline)と呼ぶことがあります。
CSRをMEMステージで処理する
上記の5段のパイプライン処理では、CSRの処理をMEMステージで行っています。これはいったいなぜでしょうか?
CPUにはECALL命令による例外しか実装してしないため、EXステージでCSRの処理を行ってしまっても問題ありません。しかし、他の例外、例えばメモリアクセスに伴う例外を実装するとき、問題が生じます。
メモリアクセスに起因する例外が発生するのはMEMステージです。このとき、EXステージでCSRの処理を行っていて、EXステージに存在する命令がmtvecレジスタに書き込むCSRRW命令だった場合、本来はMEMステージで発生した例外によって実行されないはずであるCSRRW命令によって、既にmtvecレジスタが書き換えられているかもしれません。これを復元する処理を書くことはできますが、MEMステージ以降でCSRを処理することでもこの事態を回避できるため、MEMステージでCSRを処理しています。
7.2 パイプライン処理の実装
7.2.1 ステージに分割する準備をする
それでは、CPUをパイプライン化します。
パイプライン処理では、複数のステージがそれぞれ違う命令を処理します。そのため、それぞれのステージのために、現在処理している命令を保持するためのレジスタ(パイプラインレジスタ)を用意します。
まず、処理を複数ステージに分割する前に、既存の変数の名前を変更します。
coreモジュールでは、命令をフェッチする処理に使う変数の名前の先頭にif_
、FIFOから取り出した命令の情報を表す変数の名前の先頭にinst_
をつけています。
命令をフェッチする処理はIFステージに該当するため、if_
から始まる変数はこのままで問題ありません。しかし、inst_
から始まる変数は、CPUの処理を複数ステージに分けたとき、どのステージの変数か分からなくなります。IFステージの次はIDステージであるため、変数がIDステージのものであることを示す名前に変えてしまいます。
inst_valid
、inst_is_new
、inst_pc
、inst_bits
、inst_ctrl
、inst_imm
の名前をリスト7.1のように変更します。定義だけではなく、変数を使用しているところもすべて変更してください。
7.2.2 FIFOを作成する
命令フェッチ処理とそれ以降の処理は、それぞれ独立して動作しています。実は既にCPUは、IFとIDステージ(命令フェッチ以外の処理を行うステージ)の2ステージのパイプライン処理を行っています。
IFステージとIDステージはFIFOで区切られており、FIFOのレジスタを経由して命令の受け渡しを行います。これと同様に、5ステージのパイプライン処理の実装では、それぞれのステージをFIFOで接続します(図7.5)。ただし、FIFOのサイズは1とします。この場合、FIFOはただの1つのレジスタです。
IFからIDへのFIFOは存在するため、IDからEX、EXからMEM、MEMからWBへのFIFOを作成します。
構造体の定義
まず、FIFOに格納するデータの型を定義します。それぞれのフィールドが存在する区間は図7.6の通りです。
IDステージは、IFステージから命令のアドレスと命令のビット列を受け取ります。命令のビット列をデコードして、制御フラグと即値を生成し、EXステージに渡します(リスト7.2)。
EXステージは、IDステージで生成された制御フラグと即値と受け取ります。整数演算命令のとき、レジスタの値を使って計算します。分岐命令のとき、分岐判定を行います。CSRやメモリアクセスでrs1とrs2を利用するため、演算の結果とともにMEMステージに渡します(リスト7.3)。
MEMステージは、メモリのロード結果とCSRの読み込みデータを生成し、WBステージに渡します(リスト7.4)。
WBステージでは、命令がライトバックする命令のとき、即値、ALUの計算結果、メモリのロード結果、CSRの読み込みデータから1つを選択し、レジスタに値を書き込みます。
構造体のフィールドの生存区間が図7.6のようになっている理由が分かったでしょうか?
FIFOのインスタンス化
FIFOと接続するための変数を定義し、FIFOをインスタンス化します(リスト7.5、リスト7.6)。DATA_TYPE
パラメータには先ほど作成した構造体を設定します。FIFOのデータ個数は1であるため、WIDTH
パラメータには1
を設定します*3。mem_wb_fifo
のflush
は0
にしています。
[*3] FIFOのデータ個数は2 ** WIDTH - 1
です
7.2.3 IFステージを実装する
まず、IFステージを実装します。...といっても、既にIFステージ(=命令フェッチ処理)は独立に動くものとして実装されているため、手を加える必要はありません。
リスト7.7のようなコメントを挿入すると、ステージの処理を書いている区間が分かりやすくなります。ID、EX、MEM、WBステージを実装するときにも同様のコメントを挿入し、ステージの処理のコードをまとまった場所に配置しましょう。
7.2.4 IDステージを実装する
IDステージでは、命令をデコードします。既にids_ctrl
とids_imm
には、デコード結果の制御フラグと即値が割り当てられているため、既存のコードの変更は必要ありません。
デコード結果はEXステージに渡します。EXステージにデータを渡すには、exq_wdata
にデータを割り当てます(リスト7.8)。
IDステージにある命令は、EXステージが命令を受け入れられるとき(exq_wready
)、IDステージを完了してEXステージに処理を進められます。この仕組みは、if_fifo_rready
にexq_wready
を割り当てることで実現できます。
最後に、命令が現在のクロックで供給されたかどうかを示す変数id_is_new
は必要ないため削除します(リスト7.9)。
7.2.5 EXステージを実装する
EXステージでは、整数演算命令のときはALUで計算し、分岐命令のときは分岐判定を行います。
まず、EXステージに存在する命令の情報をexq_rdata
から取り出します(リスト7.10)。
次に、EXステージで扱う変数の名前を変更します。変数の名前にexs_
をつけます(リスト7.11)。
最後に、MEMステージに命令とデータを渡します。MEMステージにデータを渡すために、memq_wdata
にデータを割り当てます(リスト7.12)。
br_taken
には、ジャンプ命令かどうか、または分岐命令かつ分岐が成立するか、という条件を割り当てます。jump_addr
には、分岐命令、またはジャンプ命令のジャンプ先を割り当てます。MEMステージではこれを利用してジャンプと分岐を処理します。
EXステージにある命令は、MEMステージが命令を受け入れられるとき(memq_wready
)、EXステージを完了してMEMステージに処理を進められます。この仕組みは、exq_rready
にmemq_wready
を割り当てることで実現できます。
7.2.6 MEMステージを実装する
MEMステージでは、メモリにアクセスする命令とCSR命令を処理します。また、ジャンプ命令、分岐命令かつ分岐が成立、またはトラップが発生するとき、次に実行する命令のアドレスを変更します。
ロードストア命令でメモリにアクセスしているとき、EXステージからMEMステージに別の命令の処理を進めることはできず、パイプライン処理は止まってしまいます。パイプライン処理を進められない状態のことをパイプラインハザード(pipeline hazard)と呼びます。
まず、MEMステージに存在する命令の情報をmemq_rdata
から取り出します(リスト7.13)。MEMステージでは、csrunitモジュールに、命令が現在のクロックでMEMステージに供給されたかどうかの情報を渡します。そのため、変数mem_is_new
を定義しています。
mem_is_new
には、id_is_new
の更新に利用していたコードを利用します(リスト7.14)。
次に、MEMモジュールで使う変数に合わせて、memunitモジュールとcsrunitモジュールのポートに割り当てている変数名を変更します(リスト7.15)。
フェッチ先が変わったことを表す変数control_hazard
と、新しいフェッチ先を示す信号control_hazard_pc_next
では、EXステージで計算したデータとCSRステージのトラップ情報を利用します(リスト7.16)。
ジャンプ命令の後ろの余計な命令を実行しないために、control_hazard
が1
になったとき、ID、EX、MEMステージに命令を供給するFIFOをフラッシュします。control_hazard
が1
になるとき、MEMステージの処理は完了しています。後述しますが、WBステージの処理は必ず1クロックで終了します。そのため、フラッシュするとき、MEMステージにある命令は必ずWBステージに移動します。
最後に、WBステージに命令とデータを渡します(リスト7.17)。WBステージにデータを渡すために、wbq_wdata
にデータを割り当てます
MEMステージにある命令は、memunitモジュールが処理中ではなく(!memy_stall
)、WBステージが命令を受け入れられるとき(wbq_wready
)、MEMステージを完了してWBステージに処理を進められます。この仕組みは、memq_rready
とwbq_wvalid
を確認してください。
7.2.7 WBステージを実装する
WBステージでは、命令の結果をレジスタにライトバックします。WBステージが完了したら命令の処理は終わりなので、命令を破棄します。
まず、WBステージに存在する命令の情報をwbq_rdata
から取り出します(リスト7.18)。
次に、WBステージで扱う変数名を変更します。変数名にwbs_
をつけます(リスト7.19)。
最後に、命令をFIFOから取り出します。WBステージでは命令を複数クロックで処理することはなく、WBステージの次のステージを待つ必要もありません。wbq_rready
に1
を割り当てることで、常にFIFOから命令を取り出します(リスト7.20)。
これで、IF、ID、EX、MEM、WBステージを作成できました。
7.2.8 デバッグのために情報を表示する
今までは同時に1つの命令しか処理していませんでしたが、これからは全てのステージで別の命令を処理することになります。デバッグ表示を変更しておきましょう。
リスト7.21のように、デバッグ表示のalways_ffブロックを変更します。
7.2.9 パイプライン処理をテストする
それでは、riscv-testsを実行してみましょう。試しに、RV64IのADDのテストを実行します。
$ make build $ make sim VERILATOR_FLAGS="-DTEST_MODE" $ python3 test/test.py -r obj_dir/sim test/share rv64ui-p-add.bin.hex FAIL : ~/core/test/share/riscv-tests/isa/rv64ui-p-add.bin.hex Test Result : 0 / 1
おや? テストに失敗してしまいました。一体何が起きているのでしょうか?
7.3 データ依存の対処
7.3.1 正しく動かないプログラムを確認する
実は、ただIF、ID、EX、MEM、WBステージに処理を分割するだけでは、正しく命令を実行できません。例えば、リスト7.23のようなプログラムは正しく動きません。
test/sample_datahazard.hex
を作成し、次のように記述します(リスト7.23)。
このプログラムでは、x1にx0 + 1を代入した後、x2にx1 + 1を代入します。シミュレータを実行し、どのように実行されるかを確かめます(リスト7.24)。
$ make build $ make sim $ ./obj_dir/sim test/sample_datahazard.hex 7 ... # 5 ID ------ 0000000000000004 : 00108113 itype : 000010 imm : 0000000000000001 EX ----- 0000000000000000 : 00100093 op1 : 0000000000000000 ← x0 op2 : 0000000000000001 ← 即値 alu : 0000000000000001 ← ゼロレジスタ + 1 = 1 # 6 ID ------ 0000000000000008 : 00000000 itype : 000000 imm : 0000000000000000 EX ----- 0000000000000004 : 00108113 op1 : 0000000000000000 ← x1 op2 : 0000000000000001 ← 即値 alu : 0000000000000001 ← x1 + 1 = 2のはずだが1になっている MEM ----- 0000000000000000 : 00100093 ...
ログを確認すると、アドレス0の命令でx1が1になっているはずですが、アドレス4の命令でx1を読み込むときにx1は0になっています。
この問題は、まだアドレス0の命令の結果がレジスタファイルに書き込まれていないのに、アドレス4の命令でレジスタファイルで結果を読み出しているために発生しています。
7.3.2 データ依存とは何か?
ある命令Aの実行結果の値を利用する命令Bが存在するとき、命令Aと命令Bの間にはデータ依存(data dependence)があると呼びます。データ依存に対処するためには、命令Aの結果がレジスタに書き込まれるのを待つ必要があります。データ依存があることにより発生するパイプラインハザードのことをデータハザード(data hazard)と呼びます。
7.3.3 データ依存に対処する
レジスタの値を読み出すのはEXステージです。データ依存に対処するために、データ依存関係があるときにEXステージをストールさせます。
まず、MEMとEXか、WBとEXステージにある命令の間にデータ依存があることを検知します(リスト7.25)。例えばMEMステージとデータ依存の関係にあるとき、MEMステージの命令はライトバックする命令で、rdがEXステージのrs1、またはrs2と一致しています。
次に、データ依存があるときに、データハザードを発生させます(リスト7.26)。データハザードを起こすためには、EXステージのFIFOのrready
とMEMステージのwvalid
に、データハザードが発生していないという条件を加えます。
最後に、データハザードが発生しているかどうかをデバッグ表示します(リスト7.27)。
7.3.4 パイプライン処理をテストする
test/sample_datahazard.hex
が正しく動くことを確認します。
$ make build $ make sim $ ./obj_dir/sim test/sample_datahazard.hex 7 ... # 5 ... ID ------ 0000000000000004 : 00108113 itype : 000010 imm : 0000000000000001 EX ----- 0000000000000000 : 00100093 op1 : 0000000000000000 op2 : 0000000000000001 alu : 0000000000000001 dhazard : 0 ... # 6 ... EX ----- 0000000000000004 : 00108113 op1 : 0000000000000000 op2 : 0000000000000001 alu : 0000000000000001 dhazard : 1 ← データハザードが発生している MEM ----- 0000000000000000 : 00100093 mem stall : 0 mem rdata : 0000000000000000 WB ---- # 7 ... EX ----- 0000000000000004 : 00108113 op1 : 0000000000000000 op2 : 0000000000000001 alu : 0000000000000001 dhazard : 1 MEM ----- WB ---- 0000000000000000 : 00100093 reg[ 1] <= 0000000000000001 ← 1が書き込まれる # 8 ... EX ----- 0000000000000004 : 00108113 op1 : 0000000000000001 ← x1=1が読み込まれた op2 : 0000000000000001 alu : 0000000000000002 ← 正しい計算が行われている dhazard : 0 ← データハザードが解消された MEM ----- WB ----
アドレス4の命令が、6クロック目と7クロック目にEXステージでデータハザードが発生し、アドレス0の命令が実行終了するのを待っているのを確認できます。
RV64Iのriscv-testsも実行します。
$ make build $ make sim VERILATOR_FLAGS="-DTEST_MODE" $ python3 test/test.py -r obj_dir/sim test/share rv64ui-p- ... FAIL : ~/core/test/share/riscv-tests/isa/rv64ui-p-ma_data.bin.hex ... Test Result : 51 / 52
正しくパイプライン処理が動いていることを確認できました。