FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

RISC-VのOoOプロセッサ、BOOMの性能を読み解く(1)

この記事は ハードウェア開発、CPUアーキテクチャ Advent Calendar 2016 - Qiita の9日目の記事です。

Advent-Calendarを埋めてくれるかた、今からでも募集中です!是非参加してください! 僕一人では、クオリティのある記事を続けられそうにありません。。。(弱音)

今回は、UC-Berkeleyの公開しているRISC-Vのアウトオブオーダプロセッサ、BOOMを読み解いていこうと思う。

UC-Berkeleyの実装にはいくつのバリエーションが存在するが、BOOMはその中の最も性能重視のCPU実装になっている。

msyksphinz.hatenablog.com

  • CMK値

各コアについて、ベンチマークスコアは以下のようになっている。BOOMの4-way版については、4.7 CMK/MHzとかなり性能が高い部類に入っている。

このBOOMプロセッサには、性能を向上させるためにどのような仕掛けが入っているのだろう?それを読み解いていこう。

Rocket Chip BOOM 2-wide BOOM 4-wide Z-scale
CoreMark[CMK/MHz] 2.32 3.91 4.7 -

幸いにして、BOOMの実装にはかなり詳細な資料がある。

ccelio.github.io

これを読み解いていくことで、現代のCPUの高速化の技術を探っていく。

1. アウトオブオーダ実行方式の種類

現代のアウトオブオーダ実行形式については、大きく分けて2つの種類が存在する。一つが"Explicit Register Renaming(明示的なレジスタリネーミング)"、もう一つが、"Implicit Register Renaming(暗黙的なレジスタリネーミング)"と呼ばれるものだ。

BOOMはそのうち、"Explicit Register Renaming"の方式を取っている。この2種類の実行方式の違いは、

  • Explicit Register Renaming : 物理レジスタを用意し、現在の最新のレジスタの場所をリネームマップで指すようにする
  • Implicit Register Renaming : アーキテクチャレジスタのみ持っており、インフライト(コミット前)の演算結果はROB(リオーダバッファ)に格納しておく。コミット処理が完了すると、アーキテクチャレジスタにROBからデータを転送することでデータを確定させる。

ということだ。Explicit Register RenamingはMIPS R10k, Alpha 21264, Intel Sandy Bridge, ARM Cortex-A15などが採用している方式で、BOOMもその方式を取っている。 一方で、Pentium 4, ARM Cortex-A57などはImplicit Register Renamingを取っているそうだ。

これらの2つのパイプラインの違いで、特に性能向上のために有利、不利というのは無いような気がする。その構造について、最初に紹介したBOOMの資料では図を使って簡単に説明されているので、参照して欲しい。BOOMのパイプラインは、以下のようになっているらしい。下記の図はDesign Specification より抜粋。

f:id:msyksphinz:20161209233216p:plain

リネーム処理

情報科学を専攻している人なら誰しも知っているリネーム処理は、アーキテクチャレジスタを、物理レジスタのどこにマッピングさせるかを指定している。下記の例では、32本(厳密にはR0を除外するので31本)のアーキテクチャレジスタをどの物理レジスタマッピングするかを指定している。このように、アーキテクチャレジスタと物理レジスタを実際には別々に管理することによって、WAWハザードが発生しないような構造になっている。

f:id:msyksphinz:20161210000154p:plain:w300

フリーリスト

フリーリストは、物理レジスタで現在使用していらいものを管理しておくためのリストだ。

例えば、現在の命令が一つレジスタ書き込みを発生させるとすると、どの物理レジスタを実際に利用するかということを決定する必要がある。

ここで、物理レジスタが「利用されている」というのは、その物理レジスタに現在の最新の値が入っていることを示し、例えば、下記の2つの命令は同じアーキテクチャレジスタに対して書き込みを行うのだが、

ADDI R1,R2,100   // フリーリストから物理レジスタ番号を一つ取り出す(PR8であったとする)。R1をPR8にマッピングし、計算結果をPR8に書き込む。
SUB  R1,R1,R4    // フリーリストから物理レジスタ番号を一つ取り出す(PR12であったとする)。R1をPR10にマッピングし直し、PR8はもう使用しないのでフリーリストに戻す。PR10に計算結果を書き込む。

上記の2命令では、まずADDI命令がフリーリストから使用していない物理レジスタ番号を一つ取り出す(ここで取り出した物理レジスタ番号が8であったとする: PR8)。ADDI命令の結果はPR8に書き込まれ、リネームマップには、アーキテクチャレジスタR1-->物理レジスタPR8のマッピングが記録されている。

次に、SUB命令もR1に書き込む命令であるが、フリーリストから別の使用していない物理レジスタ番号を取り出す(ここで取り出した物理レジスタ番号が12であったとする: PR12)。SUBI命令の結果はPR12に書き込まれ、リネームマップにはアーキテクチャレジスタR1-->物理レジスタPR12のマッピングに更新される。また、この命令により一つ前のADDI命令で使用したPR8はもう参照されなくなるので、フリーリストに書き戻される。

図: 最初のADDIが実行された時のフリーリスト、リネームマップ、物理レジスタの様子

f:id:msyksphinz:20161209235843p:plain

図: 2番目のSUB命令が実行された時のフリーリスト、リネームマップ、物理レジスタの様子

f:id:msyksphinz:20161209235808p:plain

2. 投機実行を支える技術 : 分岐予測

続いて、分岐予測について見ていこう。投機実行を行う上で、分岐予測は必須の技術だ。分岐予測によりパイプラインフラッシュを如何に発生させないか、ということが、プロセッサの性能向上の重要な鍵になる。

分岐予測にはいくつかの手法があるが、BOOMで実装されているのは

  • Branch Target Buffer (BTB)
  • gshare branch histroy table (BHT)
  • Return address stack (RAS)

の3種類となる。基本的にこれらは、現在フェッチしたアドレスから次のフェッチラインを予測するという、Next Line Predictor(NLP)に実装される技術となる。

Branch Target Buffer

Branch Target Bufferは当該プログラムアドレスのエントリに対し、分岐するかしないか、およびどのアドレスに分岐するかを記憶する方式だ。分岐するかしないかは、2ビットの飽和カウンタの方式が良く用いられる。

Gshareグローバル分岐予測

また、gshare分岐予測は、プログラムカウンタの現在の場所に加えて、前後の分岐予測結果に依存して予測する。ループのようなものであれば分岐予測は簡単であるが、ストレートなコードでのif文などによる分岐予測は予測が難しいため、この方式だと前後の分岐予測結果で次の分岐を予測する。

ヘネパタ(コンピュータアーキテクチャ: 定量的アプローチ)から一つ例を引用する。

if (aa==2)
  aa=0;
if (bb==2)
  bb=0;
if (aa!=bb) {

このようなプログラムの場合、最後のaa!=bbの結果は明らかに前の2つの分岐予測の結果に依存している。このような依存関係に応じて、分岐予測を行う方式をグローバル分岐予測と呼ぶ。 BOOMには、このような分岐予測を行うための機構も搭載されている。 具体的には、Branch History Tableとそれに応じたBranch Target Bufferが搭載されている。

Return Address Stack

Return Address Stackは、予測が難しい関数コールを改善するための機構だ。関数コールにより分岐した場合、所謂「リターン命令」を実行することで、その呼出元+1のアドレスに戻ってくることが予測される。 そこで、関数コールのための命令(RISC-VだとJAL命令やJALR命令など)が呼ばれると、そのジャンプ先+4(4バイト単位で命令は配置されているため)のアドレスをスタックに格納しておく。

そして、実際に関数から戻ってくる命令が実行される(RISC-Vの場合は書き込みアドレスがR0のJALR)と、スタックからアドレスを取り出して、次の分岐先アドレスとして利用する。

3. 終わりに

以上、ここまでRISC-Vで採用されている、アウトオブオーダ実行のための機構を紹介してきた。

まずはアウトオブオーダ実行のためのリネーミング処理、そして効率的にパイプラインを流すための分岐予測の方式について見てきた。 次回は、さらに別の部分、演算器やLSUについて読み解いて行きたいと思う。