IBM z15の分岐予測器の論文を読む

www.computer.org

ISCAの上記の論文を読む。現在は入手不可能になっているが、ISCAの時は特別に公開されていたようだ。あんまり詳細は記述できないのだがサマリだけをメモ的にアップロードしていく。

---

最新のエンタープライズクラスのIBM z15分岐予測器の設計について説明する。

• IBM z15の分岐予測器の主要な動作と機能
• パイプライン
• 予測のための構造
• 検証方法

を紹介する。

1. イントロダクション

IBM z15はメインフレーム向けのプロセッサである。これらのシステムはあらゆるワークロードに対して高性能に実行可能なように設計されており、通常はデータベース処理に対して最適化されている。

IBM z15はスーパスカラ、SMT(Simultaneous Multi Threading)、アウトオブオーダコアであり、5.2GHzで動作する。図1.に示すような深いパイプラインを持っており、6命令まで同時発行できるプロセッサである。このプロセッサは非常にパイプラインが深いため、分岐予測の精度が非常に重要となる。z15は4階層のキャッシュ改装を採用しており、240個のプロセッサコアのうち190個を使用可能となっている。CP(Central Processor)は12個のCPUコアを含んでおり、1つのL3キャッシュを共有している。4つのCPチップはSC(System Control)チップと通信することができる。このプロセッサはz/アーキテクチャ[3]に準拠している。z/アーキテクチャは分岐命令としてインダイレクト分岐と相対分岐に分類されている。

	zEC12 (32nm)	z13 (22nm)	z14 (14nm)	z15 (14nm)
CPチップ	6コア	8コア	10コア	12コア
オンチップキャッシュサイズ	L1I : 64K, L1D: 96K L1+ : 1MB Private L2 : 1MB Private L3 : 48MB Shared	L1I : 96K, L1D : 128K L2I : 2MB Private L2D : 2MB Private L3 : 63MB Shared	L1I : 128K, L1D : 128K L2I : 2MB Private L2D : 4MB L3 : 128MB Shared	L1I : 128K, L1D : 128K L2I : 4MB Private L2D : 4MB L3 : 256MB Shared
分岐予測	BTB1 : 4K (1k x 4way) BTB2 : 24K (6way) PHT : 4K CTB : 2K	BTB1 : 6K (1K x 6way) BTB2 : 96K (6way) PHT : 6K CTB : 2K	BTB1 : 8K (2K x 4way) BTB2 : 128K (4way) PHT : 8K CTB : 2K	BTB1 : 16 (2K x 8way) BTB2 : 128K (6way) PHT : 8K CTB : 2K

分岐予測は、命令フェッチ・分岐予測ユニット (IFB)によって担当される。分岐命令がデコードされると、動的に予測された分岐の情報はIDUによる命令よりも優先的に使用されて、次の命令のフェッチに使用される。

自作RISC-V OoOコアの分岐予測性能解析 (RASの論文を読む)

分岐予測は設計経験がないうえにいろいろ試行錯誤しながら作っているのだが、なかなか性能が伸びない。

時間を見つけて実装の見直しを行っているが、独自にいろいろやってもらちが明かないので論文を読んでみることにした。 参考にしたのは以下の論文「Improving Prediction for Procedure Returns with Return-Address-Stack Repair Mechanism」というもの。

ieeexplore.ieee.org

内容としては私の疑問点にかなりマッチしている。要するにCALLとRETが投機実行されてRASのインデックスが過剰に更新されてしまった場合にどうするかという話。 そこまでの経緯が図を使って詳細に説明されている。これは自分も全く同じ境遇になっているので良くわかる。

で、問題の解決方法だが、割とシンプルに「ロールバックすればよい」とだけ書いてあってそれをどうハードウェアで実現するのかを知りたかったのに、あまりそこには触れられていなかった。 途中からは性能評価の話になってしまったので途中から読むのをやめている。

やはりCALL命令を過剰にフェッチした場合にはその分だけロールバックさせなければならないということか。もう少しこれまでの実装を確認して実装方法を変更しよう。

自作RISC-V OoOコアの分岐予測性能解析 (RASの性能解析)

分岐予測は設計経験がないうえにいろいろ試行錯誤しながら作っているのだが、なかなか性能が伸びない。

とりあえず試行錯誤したバージョンは意外と性能が伸びていない。 RASのインデックスがずれてしまうのが問題のようだ。投機的にRASのインデックスが更新されてしまうので、それを上手く参照できていない。

JSONで取得している実行記録は以下のようになっており、まだまだパイプラインフラッシュが良く発生している状況だ。

"               24386" : {
  "commit" : {  "cmt" :   302,   "inst" :   999,   "dead" :   183  },
  "icache" : {  "request" :   752,   "hit" :   752,   "miss" :     0  },
  "dcache" : {
    "port[0]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[1]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[2]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[3]" : {    "req" :   139,     "hit" :   108,     "miss" :     0,     "conflict" :    31    }
    "port[4]" : {    "req" :   286,     "hit" :   217,     "miss" :     0,     "conflict" :    69    }
    "port[5]" : {    "req" :   178,     "hit" :    98,     "miss" :     0,     "conflict" :    80    }
  },
  "branch" : {    "execute" :   266,     "cmp" : { "execute" :   156, "hit" :   141 },     "uncond" : { "ret" : { "execute" :    48, "hit" :    19}, "others" : { "execute" :    62, "hit" :    62 }},   },
}
"               28386" : {
  "commit" : {  "cmt" :   310,   "inst" :  1019,   "dead" :   202  },
  "icache" : {  "request" :   773,   "hit" :   773,   "miss" :     0  },
  "dcache" : {
    "port[0]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[1]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[2]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[3]" : {    "req" :   122,     "hit" :    92,     "miss" :     0,     "conflict" :    30    }
    "port[4]" : {    "req" :   259,     "hit" :   211,     "miss" :     0,     "conflict" :    48    }
    "port[5]" : {    "req" :   164,     "hit" :   116,     "miss" :     0,     "conflict" :    48    }
  },
  "branch" : {    "execute" :   284,     "cmp" : { "execute" :   188, "hit" :   170 },     "uncond" : { "ret" : { "execute" :    44, "hit" :    12}, "others" : { "execute" :    52, "hit" :    52 }},   },
}

retの欄においてhit率が全く伸びない。BOOMの実装を読み直してもう少し確かめてみるか...

自作RISC-V OoOコアの分岐予測性能解析 (RASの設計仕様)

分岐予測は設計経験がないうえにいろいろ試行錯誤しながら作っているのだが、いくつか設計メモを残しておこう。

まずそもそもフェッチの動作だが、大きく分け3つのステージに分けている。

• s0ステージ

  • 命令キャッシュおよびTLBに対して仮想アドレスのリクエストを送出します。
  • TLBは同じサイクルで物理アドレスの探索結果を返します。
  • ヒットすれば物理アドレスまたは例外情報、ミスすればmiss信号をアサートします。
  • 命令キャッシュ内では、命令タグアドレスを用いたタグRAMの検索とデータRAMの読み出しが行われます。

• s1ステージ

  • タグRAMから読みだしたタグ情報を用いて命令キャッシュのヒット/ミスを決定します。

• s2ステージ

  • s1ステージの結果、命令キャッシュがヒットしていればヒットした命令を取得します。
  • そうでなければ命令キャッシュは読み出しをBusy状態に入り、外部に対して命令キャッシュリクエストを送出します。

で、基本的に命令フェッチハザードはS2ステージで検出してロールバックするようにしている。命令フェッチで発生するハザードは大きく分けて

• 命令キャッシュミス
• TLBミス
• 後段の命令バッファFull

これらの時にいったん命令フェッチはストップさせるようになっている。これらの検出はすべてS2ステージで、設計簡略化とハザードのシンクロのためこうしている。

で、同じように分岐予測器も動かしているのだが、

• s0ステージ : BTBとBimodalにリクエストを行う
• s1ステージ : BTBのアドレスヒット判定
• s2ステージ : フェッチした命令に分岐予測命令があり、BTBとBimodalの予測に基づいて次のフェッチアドレス変更

となっており、つまり3サイクルかけているのでs2ステージですぐさま命令フェッチアドレスを更新したとしても1サイクルバブルが空く。 BTBのためのSRAMがどれだけ早く動くか謎だが、まあs2ステージで予測を反映させてもいいのかもしれない。

RASの話に戻ると、RASも同様にs2ステージでCALL/RET命令をキャッシュライン上から抜き出してRASエントリを更新している。 いくつかやり方を試行したのだが、例えばRASのインデックスが現在Nだとすると、

1. CALL命令(A)を発見するとRASインデックスをN+1にアップデートすると同時に、そのフェッチパケット自体にN+1を渡す(つまり戻りアドレスはN+1に格納されるぞという意味)
2. そしてエントリN+1にRASの戻りアドレス(CALL命令のアドレス+4)を格納する
3. 例えば別のCALL命令(B)が投機的にフェッチされると、RASのインデックスはN+2となり同様にフェッチパケットにN+2が渡される
4. 最初のCALL命令(A)がコミットされると、その時点でRASのインデックスは命令自体が持っているRASインデックスN+1に戻る(つまり、この時点でRET命令がフェッチされるとN+1のエントリのアドレスを使ってね、となる)
5. 同様に次のCALL命令(B)がコミットされるとRASのインデックスはN+2に置き換わる
6. 万が一CALL命令(B)が投機失敗でフラッシュされる場合、RASのインデックスはN+1のままとなる。
7. RET命令をフェッチすると、N+1の値を取り出してフェッチアドレスを更新する

という仕組みだ。で、これを四苦八苦しながら実装してVerilatorで動かしているのだが、いかんせんVerilatorのコンパイルに1回30分以上かかっているので全然進まない。オープンソースEDAのみでの開発はつらいなあ。

自作RISC-V OoOコアの分岐予測性能解析 (RASのデバッグ)

ちまちまと自作RISC-Vコアを実装している。RASの検討をしたので実装を行っている。

問題となるのはBIMとの共用だ。BIMの方がキャッシュライン上の前のビット列でヒットすればそちらを採用し、RASの方がヒットすればそちらを採用する。

基本的な流れはこうだ。CALL系命令(JAL命令、JALR命令の特定の形)をキャッシュライン中で発見すると、その次のアドレスをRAS上に保存する。 さらに命令を進めて言ったうえでRET命令(JALR命令の特定の形)にを見つけると、RASのインデックスから当該アドレスを引っ張ってきて次の命令フェッチアドレスとする。

この形でとりあえず最初のCALLとRET命令は分岐予測ができるようになったが、まだDhrystoneを全部PASSさせることが出来ていない。引き続きデバッグする。

とりあえずデバッグのためにDhrystoneの中からCALLとRETのペアを引き出してみる。

12966 : 72 : PC=[0000000080002842] (26,02) f49ff0ef jal     pc - 0xb8
13186 : 79 : PC=[00000000800027b0] (31,01) 00008082 ret
13206 : 85 : PC=[0000000080002858] (33,02) f75ff0ef jal     pc - 0x8c
14262 : 417 : PC=[00000000800027ea] (26,01) 00008082 ret
14338 : 420 : PC=[0000000080002860] (30,01) e71ff0ef jal     pc - 0x190
14510 : 422 : PC=[00000000800026d4] (38,01) 00008082 ret
14558 : 425 : PC=[0000000080002868] (42,04) 12c000ef jal     pc + 0x12c
15030 : 493 : PC=[0000000080002a68] (63,04) ec8ff0ef jal     pc - 0x938
15194 : 503 : PC=[0000000080002142] (03,02) 00008082 ret

なるほど、現在問題になっているのは2番目のJALとRETのペアが正しくRASで予測できていないことだが、これは別の部分でCALL命令を正しく認識できていないらしい。デバッグする。

自作RISC-V OoOコアの分岐予測性能解析 (RASの実装検討)

ちまちまと自作RISC-Vコアを実装している。DhrystoneがPASSできるようになったが、まだまだ性能的にはひどいもんだ。

次に検討するのはRAS (Return Address Stack)の実装だ。 RASはJALRやJAL命令などのCALL系命令でスタックに戻り値を置き、RET命令がフェッチされた時点でスタックからその値を取り返す。 RET命令が戻るべきアドレスがスタックにすでに置かれているため、パイプラインフラッシュせずに関数の呼び出し元に戻ることができる。

ただし投機実行しているときはそう簡単には上手く行かなくて、投機的に関数呼び出し命令が実行されてその後廃棄された場合、スタックだけは先に進んでしまうがRET命令が呼び出すべきアドレスはずれてしまう。 これを防ぐために、BOOMがどのような技法でRASのずれを回避しているのかを調査すると、各命令がRASのインデックスを持っているらしい。

CALL命令がフェッチされると、そのCALL命令に対応するRASのインデックスが命令に渡される(そしてRASのインデックスはインクリメントされる)。 もしそのCALL命令が廃棄されると、廃棄時にRASのインデックスをその場所まで戻す。そうすることで投機的に実行したRASインデックスを元に戻すことができる。

この機構を実装してみよう。

自作RISC-V OoOコアの分岐予測性能解析 (BIMによる性能向上解析)

ちまちまと自作RISC-Vコアを実装している。DhrystoneがPASSできるようになったが、まだまだ性能的にはひどいもんだ。

BTBとBIMがDhrystoneをある程度動かせるようになってきたので、性能を見てみた。 Dead状態になるコミットはかなり減ってきた。ただしまだ全体の内1/4はパイプラインフラッシュによって殺されている。

分岐予測失敗のうち、Conditional Branchによる失敗はかなり減ってきた。次に問題となるのはReturn命令だ。 RASの実装が足りていないのがここに来てボトルネックになっている。これを実装して行こう。

"               24386" : {
  "commit" : {  "cmt" :   339,   "inst" :  1109,   "dead" :   150  },
  "icache" : {  "request" :   733,   "hit" :   733,   "miss" :     0  },
  "dcache" : {
    "port[0]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[1]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[2]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[3]" : {    "req" :   141,     "hit" :   108,     "miss" :     0,     "conflict" :    33    }
    "port[4]" : {    "req" :   279,     "hit" :   219,     "miss" :     0,     "conflict" :    60    }
    "port[5]" : {    "req" :   189,     "hit" :   116,     "miss" :     0,     "conflict" :    73    }
  },
  "branch" : {    "execute" :   317,     "cmp" : { "execute" :   193, "hit" :   177 },     "uncond" : { "ret" : { "execute" :    55, "hit" :    35}, "others" : { "execute" :    69, "hit" :    69 }},   },
}
"               28386" : {
  "commit" : {  "cmt" :   333,   "inst" :  1094,   "dead" :   143  },
  "icache" : {  "request" :   743,   "hit" :   743,   "miss" :     0  },
  "dcache" : {
    "port[0]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[1]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[2]" : {    "req" :     0,     "hit" :     0,     "miss" :     0,     "conflict" :     0    }
    "port[3]" : {    "req" :   157,     "hit" :   114,     "miss" :     0,     "conflict" :    43    }
    "port[4]" : {    "req" :   301,     "hit" :   221,     "miss" :     0,     "conflict" :    80    }
    "port[5]" : {    "req" :   203,     "hit" :   119,     "miss" :     0,     "conflict" :    84    }
  },
  "branch" : {    "execute" :   308,     "cmp" : { "execute" :   186, "hit" :   172 },     "uncond" : { "ret" : { "execute" :    56, "hit" :    35}, "others" : { "execute" :    66, "hit" :    66 }},   },
}