FPGA開発日記

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

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

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

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

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

0. 参考にしている資料

  • The Berkeley Out-of-Order Machine (BOOM) Design Specification

ccelio.github.io

1. BOOMのReorder Buffer (ROB) 構造

前回のリネームステージに続いて、リオーダバッファについて読み解いていく。「Chapter.6 The Reorder Buffer(ROB) and the Dispatch Stage」の章だ。

リオーダバッファの構造は、基本的に実行中の命令を1つづつ登録していき、その命令の実行状態などを管理するための機構だ。 アウトオブオーダで発行された命令も、ROBでFIFOで順番に管理されることによってインオーダでコミットされることが保証される。

このために、ROBには複数のエントリがCyclic FIFOとして実現されているのだが、

  • 最も古い命令を指すポインタ : Commit Head
  • 最新の命令を指すポインタ : rob tail

として制御している。つまり、新しい命令がIssue Stageから出力されると、FIFOのrob tailの場所に挿入され、その命令がrob tailがインクリメントされる。また、最も古い命令のコミットが完了すると、Commit Headがインクリメントされるという構造だ。Function Unit内で命令がアウトオブオーダで実行され、命令の完了(WriteBack)の順序が命令の順番になっていないとしても、このROBで実行順序を管理することによって、コミット時に命令の順番が崩れてしまうことを防いでいる。

下記はBOOMの資料にある、2-way版BOOMのROBの構造だ。

f:id:msyksphinz:20161211234955p:plain

構造を見て分かるとおり、ROBはInstruction Bank(0), Instruction Bank(1)に分かれており、2-way Issue版の場合はway-0がBank(0), Way-1がBank(1)に格納されると思われる。これが4-way Issue版のBOOMになると、Bank(0)からBank(3)まで並列に存在することになる。

これはBOOMが1命令ずつ命令フェッチを発行するのではなく、2命令または4命令ずつ命令発行を行うための機構であり、そのため、各バンクの同一エントリに付属するPCビットは8バイト毎(4-wayの場合は16バイト毎)に増加するような機構になっている。

また、有効な命令が挿入されていることを示すvalビット、現在命令が実行注であることを示すbsyビット、例外が発生したことを示すexcビット、さらに実際に実行されるマイクロオペレーションを格納するためのuopcビット、さらに、どの分岐命令の分岐予測のもとにフェッチされた命令かを示すbrmaskビット(正直このビットの使い所はちゃんと理解できていない)などが格納されている。

Function UnitからWriteback信号(wb_valids, wb_upos)がアサートされると、ROBの当該エントリの状態を更新し、bsyで無くなると、その命令はコミット可能状態に入る。さらに、rob_headが当該エントリを指すと、その命令はコミットされる。

ストア命令の処理

上記のROBの構造では、Function Unitでの実行が完了した段階でコミットが発生するが、ストア命令のみ構造が異なる。ストア命令はメモリを書き換えるため、コミット前に投機的に実行することは出来ない。 そこで、コミット処理ユニットにて処理が完了した段階で、LSUに信号を送りストア処理を実行する。

2. BOOMのExecution Pipeline

続いて、BOOMの実行パイプライン、つまり演算ユニットについて読み解いていく。「Chapter.9 The Execution Pipeline」の章だ。

まず、Explicit Renaming機構のBOOMは集中管理型のパイプラインを持っており、下記の図に示すようなレジスタ構造を持っている。dual-issueの場合、5-read,3-writeのレジスタファイルを利用している。

下記はBOOMのDesign Specificationより抜粋。

f:id:msyksphinz:20161212004653p:plain

この5-readどのように割り当てるのかについては、8.1.1 Dynamic Read Port Schedulingに言及されている。 そもそも、Dual-issueにおいて単純な命令であれば1命令で2-readしかしないため問題ないが、複雑なFPUの命令になると3-readが同時に発行されるため問題になる。 この場合は、もし使用するオペランドに同一のものがあれば圧縮を行い参照リードポート数を減らして5-readに入るように調整し、そうでなければもう一方の命令を遅らせるなどの制御を行っている。

続いて、各Execution Pipelineはそれぞれ含まれている命令群が異なっており、これにより命令をどちらのPipelineに渡されるのかが決定される。しかしALUのみ両方のパイプラインに内蔵されており、どちらのパイプラインに流すことができる。

Execution-0のパイプラインでは最終的にALU, FPU, imul(整数乗算)のパイプラインを統合されるため、3つの演算ユニットは3サイクルに統一されている。つまり、ALUのレイテンシは常に3となるが、それぞれのステージからフォワーディングパスが通っているため、性能面でそれほど問題にはならないと考えられる。

一方で、Execution Unit #1のパイプラインは若干複雑で、それぞれの命令が別々のパイプラインで到達するため制御が複雑になっている。 ALUのみ1サイクルでライトバックポートに到達するが、divはパイプライン化されていないし、LSUもキャッシュにヒットするか否かでレイテンシが異なる。 これらを加味しながら、必要なライトバックポートの制御を行って、レジスタファイルの更新とROBの更新を行っているものと考えられる。

Functional Unitsの構造

Functional Unitsの構造ももあまり特別に言及することは無い。入出力のストール制御を行うため、ポートの部分にはFIFOが取り付けられ、前後のステージとのパイプライン制御が行われている。 パイプライン化された演算器は毎サイクルデータを入力することができるが、パイプライン化されていないような演算(除算回路など)では、入力側のReady信号がデアサートされ、新しい命令が入力されないような配慮が成されている。

下記はBOOMのDesign Specificationより抜粋。入出力部にFIFOが設置されており、各ステージからはバイパス用の信号が作られている。それ以外で特に特筆すべきことは無い。

f:id:msyksphinz:20161212090915p:plain

Branch Unitの構造

分岐ユニットだけ特別なビットを持っており、上記のFigure 6.1では分岐予測用のビットマスクが4ビットほど用意されている。これは、分岐命令がデコードされたとき、各分岐命令に個別の1ビットが割り当てられ、それ以降の後続の命令がどの分岐命令に依存しているかを示している。 従って、分岐マシクビットが4ビットならば、ROBに最大で4命令分の分岐命令を挿入することが出来る、ということになりそうだ。

各分岐命令の、分岐予測結果をブロードキャストする際、ブロードキャストされた情報を受け取ったInflightな命令は、自分がその分岐結果に依存しているかどうかをチェックする。

例えば下記のように命令が(投機的に)実行されたとする。ここから先は筆者の予測だが、おそらく以下のようにbrmaskが設定されるものと思われる。

ADD R1,R2,R3  // brmask = 0000
BNE R0,R1,100 // brmask = 0001
SUB R4,R3,R2  // brmask = 0001
BLT R4,R1,200 // brmask = 0011
DIV R5,R7,R6  // brmask = 0011

分岐命令以降の命令は、分岐命令に割り当てられたbrmaskの値を保持する。これにより、分岐命令がフラッシュした場合、フラッシュした分岐命令のbrmaskと同一のbrmaskビット位置が設定されている命令がフラッシュされるものと思われる。

ただ、この機構は実際にどうやって実現しているのかいまいち疑問が残る。例えば、上から2番目のBNE命令が分岐予測に失敗してフラッシュした場合、brmask[0]=1の命令が全てフラッシュする。

ADD R1,R2,R3  // brmask = 0000
BNE R0,R1,100 // brmask = 0001 --> 分岐予測失敗
SUB R4,R3,R2  // brmask = 0001 --> フラッシュ
BLT R4,R1,200 // brmask = 0011 --> フラッシュ
DIV R5,R7,R6  // brmask = 0011 --> フラッシュ

一方、上から4番目のBLT命令が分岐予測に失敗した(BNE命令が分岐予測に成功した)場合、brmask[0],brmask[1]=1の命令がフラッシュすると、分岐予測に成功したBNE命令の後続にあるSUB命令もフラッシュされてしまう。

ADD R1,R2,R3  // brmask = 0000
BNE R0,R1,100 // brmask = 0001 --> 分岐予測成功
SUB R4,R3,R2  // brmask = 0001 --> フラッシュ <-- BLTの失敗により、この命令もフラッシュされてしまう可能性がある。
BLT R4,R1,200 // brmask = 0011 --> 分岐予測失敗
DIV R5,R7,R6  // brmask = 0011 --> フラッシュ

では、brmaskはonehotな構造なのだろうか？これも違う気がする。何故ならば、分岐予測に失敗した後続の全ての命令をフラッシュすることが出来なくなるからだ。結局、デザインをきちんと見てみないとどのような機構になっているのかは良く分からないということか。

ADD R1,R2,R3  // brmask = 0000
BNE R0,R1,100 // brmask = 0001 --> 分岐予測失敗
SUB R4,R3,R2  // brmask = 0001 --> フラッシュ
BLT R4,R1,200 // brmask = 0010 --> フラッシュされない (onehotなので)
DIV R5,R7,R6  // brmask = 0010 --> フラッシュされない (onehotなので)

3. 終わりに

うーん、いまいちBOOMの分岐予測の機構についてはまだ納得出来ていない部分がある。

そもそも、brmaskという機構は、分岐命令すらアウトオブオーダに実行することを考えて実装された機能だと思われる。 しかし、こんな小難しいことをしなくても、分岐命令だけインオーダに発行すれば良いのでは無いかなあ？そして最後に、ROBに分岐予測失敗を通知し、当該分岐命令よりも後続のROBを全てフラッシュすれば良いような気もする。 これについては、実際にどのように実装されているのかはまだ分からない。