FPGA開発日記

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

SPEC CPU 2006 を SimPoint (100M interval) と Full-run で比較してみる (5. クラスタリングバイアスの解析)

msyksphinz.hatenablog.com

前回、cluster 9 (代表は simpoint 410) のメンバー 75 個を全部実走してみた。その結果、

  • クラスタ内のばらつき (variance) は確かにある
  • でも cluster 9 単体の bias は −5.7% しかなく、benchmark 全体の −13% gap にはほとんど効いていない

という結論になった。 今回はその続きで、gap への寄与が大きい残りの上位クラスタを順に調べていく。 結論を先に言うと、cluster 8 (代表 simpoint 359) ひとつだけで gap の 71% を説明できる という、かなりはっきりした結果が出た。順番に見ていく。

1. 検証対象の絞り込み

シリーズ 4 本目で出した「クラスタごとの寄与表」をもう一度載せる。 403.gcc subcmd 1 の SimPoint 推定値 (173.78B cycles) のうち、各クラスタが何 % を占めているか:

順位 cluster rep simpoint weight IPC cycles/100M 寄与シェア rep bias
1 7 635 0.042 0.04 2,284.7M 39.4% +1.3%
2 1 163 0.154 0.40 247.0M 15.5% §3 で測定
3 8 359 0.213 0.87 113.8M 9.9% §3 で測定
4 10 479 0.030 0.15 654.3M 7.9% —
5 4 243 0.120 0.62 158.5M 7.8% —
6 9 410 0.186 1.81 54.8M 4.2% −5.7%
7 14 707 0.028 0.29 337.9M 3.9% —
8 12 314 0.072 1.03 95.7M 2.8% —
9 0 308 0.044 0.69 144.2M 2.6% —
10 13 311 0.030 0.56 175.6M 2.1% —
11 2 336 0.021 0.49 200.6M 1.7% —
12 3 27 0.025 1.12 88.3M 0.9% —
13 11 373 0.021 1.00 99.0M 0.9% —
14 6 35 0.011 1.28 77.5M 0.4% —
15 5 211 0.003 1.01 98.1M 0.1% —

表の補足:

  • 寄与シェア = weight × cycles を全 15 クラスタで正規化した値 (合計 173.78B cycles)。
  • rep bias = 代表点の cycles が、そのクラスタ全メンバーの平均からどれだけズレているか = (代表点 − 平均) / 平均。マイナスなら代表点が平均より小さい (= SimPoint が過小評価)、プラスなら過大評価を意味する。
  • rep bias 列の — はまだ全メンバーを実走していないクラスタ。§3 で測定 の 2 つは今回この記事で測る対象。

このうち寄与の大きい cluster 7 (simpoint 635) と cluster 9 (simpoint 410) は、すでに全メンバーを測ってあった。

  • cluster 7: bias +1.3% で、代表点が平均よりわずかに重い (= 過大評価)。寄与は 40% と大きいが、これを真の平均に直すと cycles が減るので、全体の gap はむしろ広がる向きに働く。
  • cluster 9: bias −5.7% だが、寄与が小さいので gap への影響も小さい。

そこで、残った寄与の大きい 2 つ — cluster 1 (寄与 15.5%) と cluster 8 (寄与 9.9%) を調べる。

2. 実験手順

クラスタの全メンバー (100〜150 個) を Sniper で実走すると時間がかかりすぎる。かといってランダムに数個取ると、たまたま軽いメンバーばかり/重いメンバーばかりを引いて平均がブレる。そこで「層化サンプリング (stratified sampling)」を使う。これは母集団をある軸でいくつかの層に分け、各層から満遍なく取ることで、少ないサンプルでも全体を偏りなく代表させる手法。

今回その軸に使うのが「代表点 (重心) からの距離」。前回 (3 本目) で、重心から遠いメンバーほどキャッシュ動作が重い (cycles が大きい) という強い相関が見えていた。つまり距離は「そのメンバーがどれくらい重いか」の代理になっているので、距離方向に満遍なく取れば軽い〜重いまでをカバーできる。

具体的な手順は 2 段階。使うのは SimPoint が -saveLabels で吐く bbv_1.out.0.labels で、1 行 1 interval、<クラスタ ID> <重心からの距離> が並んでいる (N 行目 = interval N−1)。

# (1) 対象クラスタのメンバーだけ抜き出し、距離の昇順に並べる
awk -v c="$NEW_CID" '$1==c {print NR-1, $2}' bbv_1.out.0.labels | sort -k2 -g > sorted.txt

# (2) 並べたものから等間隔 (ここでは 4 個に 1 個) で間引く
awk 'NR == 1 || NR % 4 == 1 || NR == 122' sorted.txt

(1) では、$1==c でクラスタ ID が対象クラスタのものだけを残し、print NR-1, $2 で interval 番号 (行番号 −1) と距離を出力、sort -k2 -g で 2 列目の距離を数値昇順にソートする。結果 sorted.txt は「重心に近い順」に並んだメンバー一覧になる。

(2) では、その並びの先頭 (NR == 1、最も重心に近い点)、4 行ごと (NR % 4 == 1)、末尾 (NR == 122、最も遠い点) を拾う。これで「重心の近く〜遠くまで」を順位上で等間隔にサンプリングできる。

なぜこれで偏りのない平均が得られるのか。クラスタ内のメンバーは重心側に密集している (近い距離帯ほどメンバー数が多い) ので、順位で等間隔に間引くと、密集している距離帯からは自動的に多くのサンプルが取れる。つまりサンプルがメンバー密度に比例して配分されるため、サンプル平均がそのままクラスタ全体の平均の不偏推定になる。

サンプルサイズ:

クラスタ total members sample 数
Cluster 1 (rep 163) 109 37 (every 3rd)
Cluster 8 (rep 359) 151 32 (every 4th)

各サンプルを Sniper の詳細モード (warmup なし、cold cache、roi-icount:0:0:100M で simpoint と同じ条件) で 100M 命令ずつ走らせる。 8 並列で約 90 分かかった。

3. 結果: cluster 1 はまとまっている、cluster 8 はバラバラ

3.1 Cluster 1 (rep simpoint 163, IPC 0.40, 寄与シェア 15.5%)

値
距離レンジ 0.007 〜 0.375
サンプル数 37
rep cycles 247.0M
平均 cycles 253.5M
中央値 cycles 250.6M
range 210.8M 〜 350.1M (1.66×)
IPC range 0.28 〜 0.47
rep vs mean bias −2.6%

cluster 9 や cluster 7 と同じく「分布がまとまっていて、代表点がうまく全体を代表している」パターン。 cluster 1 単体での gap への寄与は +0.71B (= 2.7%) で、ごくわずか。

3.2 Cluster 8 (rep simpoint 359, IPC 0.87, 寄与シェア 9.9%)

値
距離レンジ 0.054 〜 0.602
サンプル数 32
rep cycles 113.8M
平均 cycles 236.1M
中央値 cycles 143.8M
range 98.1M 〜 621.5M (6.33×)
IPC range 0.16 〜 1.01 (6.3×)
rep vs mean bias −51.8%

全然まとまっていない。同じクラスタの中で IPC が 0.16 から 1.01 まで 6 倍も開いている。 代表点の simpoint 359 (113.8M cycles) はクラスタの中でも速い方に寄っていて、平均 (236.1M) は代表点の 2 倍以上もある。

特に重いメンバー (外れ値):

interval 距離 IPC cycles rep 比
153 0.24 0.16 621.5M 5.5×
129 0.16 0.17 568.3M 5.0×
218 0.26 0.19 516.7M 4.5×
8 0.45 0.31 321.6M 2.8×

平均 (236.1M) と中央値 (143.8M) が大きく離れている。これは右側に長く裾を引いた、偏った分布になっているということ。 半数のメンバーは代表点に近いのに、残り半分に「ものすごく重い」外れ値が混ざっている。

4. インパクト: gap の主因が確定

cluster 8 を代表点でなく、本当の平均で見積もり直すと:

SimPoint 推定 (rep 113.8M)   : 0.213 × 709 × 113.8M = 17.18B cycles
真値 (mean 236.1M)           : 0.213 × 709 × 236.1M = 35.65B cycles
追加分                        : +18.47B cycles
benchmark 全体の gap 26.14B   : 70.7% カバー

cluster 8 単独で gap の 71% を説明できる。

4 クラスタ全部の補正値合計:

クラスタ 補正 (B cycles) gap カバー率
Cluster 9 (rep 410) +0.25 +0.9%
Cluster 7 (rep 635) −0.85 −3.3% (gap を広げる)
Cluster 1 (rep 163) +0.71 +2.7%
Cluster 8 (rep 359) +18.47 +70.7%
合計 +18.58 +71%

残り 29% の gap は別の要因 (寄与が中くらいの他のクラスタ + FIFO/SIFT の差 + 状態の積み重なり) だと考えている。

5. なぜ cluster 8 だけこんなにバラつくのか

ここが一番知りたいところ。 cluster 9, 7, 1 はどれも bias が 6% 未満なのに、cluster 8 だけ 50% の bias を持っている。

今のところの仮説:

  • BBV ベースのクラスタリングは「実行された basic block の出現頻度ベクトル」が似ているかどうかで分類する
  • 同じ basic block を回していても、実行のたびにアクセスするデータの配置が大きく変わるループがあると、BBV は似ていてもキャッシュの動きは全然違う
  • 例えば 403.gcc には「コンパイル対象の AST を再帰的にたどる」「ハッシュテーブルのバケットを走査する」といった、通るコードは同じでもデータ次第でキャッシュの効き方が大きく変わるループがあるはず
  • cluster 8 には「BBV は似ているけれどデータのアクセス範囲が違う」区間がいろいろ混ざってしまっている、というのが今の見立て

これをマイクロアーキテクチャのレベルで確かめるのが次の課題になる。