前回、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 は似ているけれどデータのアクセス範囲が違う」区間がいろいろ混ざってしまっている、というのが今の見立て
これをマイクロアーキテクチャのレベルで確かめるのが次の課題になる。