perf statでL1,L2(,L3)キャッシュミス測定

はじめに

この記事は,前回のエントリの続きものです.
まだご覧になっていない方は,前回分をお読みになってからこちらの記事を見てください.

対象プロセッサ

このエントリは,AMDの次のプロセッサを対象に書かれています.

  • AMD Athlon 64
  • AMD Opteron
  • AMD Phenom

ただし, これらのプロセッサでは本エントリの記述がそのまま当てはまる という意味であって,
他のプロセッサでも,記憶域の構成を知った上で本エントリのような考え方を適用すればキャッシュミス測定ができます.

上に挙げたプロセッサをお使いの場合でも,L3キャッシュがあるモデルかどうかで読み替えてください.
本エントリではL3キャッシュがあるとして記述している箇所があります.

参考文献

前回のエントリでも紹介した
Basic Performance Measurements for AMD Athlon 64, AMD Opteron and AMD Phenom Processors
の “4.3 Memory Accesses” を参考に本エントリを書きました.

perf stat でキャッシュミスを正確に測定するのは難しい

perf list 一覧できるイベント名は直感的ですが,実際には何のハードウェアイベントを測定しているのかが分かりにくいというのは前回のエントリでも触れました.

試しに,イベント名を使ってキャッシュミスを計測します.
その値と, Basic Performance Measurements for AMD Athlon 64, AMD Opteron and AMD Phenom Processors に書かれた計算式から求めた値と比較してみて,「イベント名はアテできない・・・」ということを実感してみましょう.

測定に使ったCPUは,Quad-Core AMD Opteron. Model. 8354 です.L1データキャッシュ,L1命令キャッシュ,L2キャッシュがコアごとに1つずつ,L3キャッシュが4コアに1つあります.

測定用アプリケーション(a.out)は単純なもので,1次元の領域に対して書き込みをした後読み出すだけです(下の擬似コード参照).

1
2
3
4
5
6
7
8
9
10
11
size = atoi(コマンドライン引数);
int *a = malloc(size * sizeof(int));

for (i = 0; i < size; ++size)
size[i] = 1;

sum = 0;
for (i = 0; i < size; ++size)
sum += a[i];

printf("%d\n", sum);

では,イベント名を使ってキャッシュミスらしきものを計測してみましょう.

1
2
3
4
5
6
7
8
9
10
11
$ perf stat -e L1-dcache-load-misses -e L1-dcache-store-misses -e cache-misses -e LLC-load-misses -e LLC-store-misses ./a.out 1000000000

Performance counter stats for './a.out 1000000000':

77557463 L1-dcache-load-misses # 0.000 M/sec
<not counted> L1-dcache-store-misses
190127 cache-misses # 0.000 M/sec
86401250 LLC-load-misses # 0.000 M/sec
<not counted> LLC-store-misses

7.447300257 seconds time elapsed

*-store-misses が計測出来ていない時点で,イベント名が疑わしい臭いがします.

(※ ‘dcache’ はデータキャッシュ, ‘LLC’ は ‘Last Level Cache’ の略です)

次に, Basic Performance Measurements for AMD Athlon 64, AMD Opteron and AMD Phenom Processors の計算式を使った測定の結果を見てみます.
測定用のスクリプト, “perf-stat-with-events.py” はこのエントリ中に掲載します.

1
2
3
4
5
6
7
8
9
10
$ perf-stat-with-events.py ./a.out 1000000000

(出力抜粋)

186936122 Data Cache Misses
146084145 L2 Misses
16306069 L3 Misses

=== Elapsed Time ===
7.371837186 seconds time elapsed

先程のイベント名を使った測定の値と比較すると,どのように対応しているのかが全く分かりません.

やはり,真面目に各階層のキャッシュミスを計測しようと思うと,イベント名に頼ってもいられないというのが現状のようです.

perf のソースを覗いて実際に測っているものを調べる

今回のエントリの本筋とは外れますので,読み飛ばして結構です.

perf のソースを見て perf stat では何を測っているのかを確認してみたいと思います.

perfのソースは,Linuxのソースツリーの中にあります.
Linuxのソースがあるディレクトリの中で,

1
find -name "perf_"

とすると,perfのソースのありかが分かります(ただし,これで列挙されるファイルで全てなのかは知りません).

実際にハードウェアカウンタの値をとるソースは,当然プロセッサの種類に依存します.
先の測定に用いた, AMD Opteron. Model. 8354 では,
“arch/x86/kernel/cpu/perf_event_amd.c”
に, perf stat ではどのハードウェアカウンタの値をとっているのかが書いてあります.

コードについてあまり深くは触れませんが,これを見ると,

  • 「AMDのプロセッサ」という風に汎用的な枠組みで定義しているので,L3キャッシュを持つプロセッサについても,L3キャッシュミスを計測するためのイベント名を提供していない
  • 例えばデータキャッシュミスなどは, Basic Performance Measurements for AMD Athlon 64, AMD Opteron and AMD Phenom Processors で「この測り方は正確な測定としてはお勧めできません」と書いてあるやり方で計測しようとしている

といった問題点が見えてきます.

Oprofileみたいに,プロセッサの種類をもっと細かく分類しなければ,「直感的なイベント名で正しく計測」というのは難しいのでしょう.
(余談の余談ですが,そういうpatchは投げられてないんですかね?)

キャッシュ・メインメモリの構成を正しく把握する

お使いのプロセッサで,キャッシュとメインメモリがどのような構成になっているのかを正しく知らなければ,正しいキャッシュミス測定はできません.
これはそれぞれのプロセッサのマニュアルに載っている情報のはずです.

先程の計測に使った AMD Opteron. Model. 8354 については,同様のキャッシュ・メインメモリ構成を持つプロセッサの日本語解説記事がありました:
後藤弘茂のWeekly海外ニュース - 大幅に強化されたAMDのクアッドコア「Barcelona」

キャッシュミスを計算する

それでは,キャッシュミスを計算します.計算するのは,

  • L1データキャッシュミス
  • L1命令キャッシュミス
  • L2キャッシュミス
  • L3キャッシュミス

です.

そのために,次のハードウェアイベントを計測しておきます.
括弧内は,

1
$ perf stat -e rNNN

の NNN に当たる, <UnitMask(16進数)><EventSelect(16進数)> を表します.

  • Data Cache Accesses (40)
  • Data Cache Refills from L2 (1e42)
  • Data Cache Refills from System (1e43)
  • Instruction Cache Fetches (c80)
  • Instruction Cache Refills from L2 (c82)
  • Instruction Cache Refills from System (c83)
  • Requests to L2 Cache [TLB fill] (c47d)
  • L2 Cache Misses [TLB fill] (c47e)
  • Read Requests to L3 Cache (cf74e0)
  • L3 Cache Misses (cf74e1)

L1データキャッシュミスの計算を例に,考え方を知る

L1データキャッシュミスを直接測定するためのハードウェアイベントはありません.間接的な手法を採ります.

これはL1データキャッシュにも以外の全てのキャッシュにも言えることですが,
キャッシュミスが起きると,自分より下のレベルのキャッシュかメインメモリからキャッシュライン分のデータを取ってきて,自分のキャッシュに載せる
ということが起きます(この動作を refill と言います).
つまり,
自分より下のレベルのキャッシュ・メインメモリからデータを取ってきて,自分のキャッシュに載せるという一連の動作(Refill)の回数が,キャッシュミス回数
となります.

従って,

1
"L1データキャッシュミス回数" = "L2からL1データキャッシュへのrefill回数" + "L3からL1データキャッシュへのrefill回数" + "メインメモリからL1データキャッシュへのrefill回数"

という関係が成立します.

右辺の項とハードウェアイベントの対応は,

1
2
"L2からL1データキャッシュへのrefill回数" = "Data Cache Refills from L2"
("L3からL1データキャッシュへのrefill回数" + "メインメモリからL1データキャッシュへのrefill回数") = "Data Cache Refills from System"

となっています.

以上より,

1
"L1データキャッシュミス回数" = "Data Cache Refills from L2" + "Data Cache Refills from System"

として計算ができます.

その他のレベルのキャシュミスについて

L2キャッシュミスが起こる状況を考えてみます.

  • L1データキャッシュミスが起きて,L2キャッシュにアクセスしたところ,L2キャッシュもミスしたので,L3キャッシュまたはメインメモリから,L1データキャッシュにキャッシュラインを取ってきた
  • L1命令キャッシュミスが起きて,L2キャッシュにアクセスしたところ,L2キャッシュもミスしたので,L3キャッシュまたはメインメモリから,L1命令キャッシュにキャッシュラインを取ってきた

これらの場合の他に,L2キャッシュのTLBミスが発生した場合も勘定に入れます(よく分かってないのですが,ページテーブルのキャッシュとして,TLBとの間のL2キャッシュも使用しているのでしょうかね?.

従って,

1
"L2キャッシュミス回数" = "Data Cache Refills from System" + "Instruction Cache Refills from System" + "L2 Cache Misses [TLB fill]"

と計算できます.

今回対象にしているプロセッサでは,(L3キャッシュを持つものならば)L3キャッシュミスは直接計測できます.

キャッシュに関するイベントを計測するスクリプト

データキャッシュ・命令キャッシュ・L2キャッシュ・L3キャッシュに関する測定をするスクリプトを作りました.
AMD Opteron. Model. 8354 で動作を確認しています.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
$ perf-stat-with-events.py ./a.out 1000000000
=== Running Environment ===
Performance counter stats for './mopt_ref_implementation 1000000000':

=== Counted Events ===
6122320253 Retired Instructions
2123804830 Data Cache Accesses
59707845 Data Cache Refills from L2
127228277 Data Cache Refills from System (Northbridge)
1630510550 Instruction Cache Fetches
80385 Instruction Cache Refills from L2
88990 Instruction Cache Refills from System (Northbridge)
18766878 Requests to L2 Cache [TLB fill]
8167131 L2 Cache Misses [TLB fill]
32867005 Read Requests to L3 Cache
16306069 L3 Cache Misses

=== Calculated Events ===
6122320253 Retired Instructions
2123804830 Data Cache Accesses
34.690% Data Cache Request Rate
186936122 Data Cache Misses
8.802% Data Cache Miss Ratio
1630510550 Instruction Cache Fetches
26.632% Instruction cache Request Rate
169375 Instruction Cache Misses
0.010% Instruction Cache Miss Ratio
205872375 L2 Requests
3.363% L2 Request Rate
146084145 L2 Misses
70.959% L2 Miss Ratio
32867005 Read Requests to L3 Cache
0.537% L3 Request Rate
16306069 L3 Misses
49.612% L3 Miss Ratio

=== Elapsed Time ===
7.371837186 seconds time elapsed

といった感じの出力が得られます.

改変等ご自由にどうぞ.
(print_calculated_events 関数がアレな感じですが,基本的にやっていることは上述のキャッシュミス計算などです)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#!/usr/bin/env python

# This script is written referring to
# Basic Performance Measurements for AMD Athlon 64,
# AMD Opteron and AMD Phenom Processors
# http://developer.amd.com/Assets/intro_to_ca_v3_final.pdf


import sys
import re
import subprocess
import types

# Modify this list as you like.
# The format of each element is:
# select: `NNN' for "perf stat -e rNNN"
# name: Event name used in output
events = [
{"select": "c0", "name": "Retired Instructions"},
{"select": "40", "name": "Data Cache Accesses"},
{"select": "1e42", "name": "Data Cache Refills from L2"},
{"select": "1e43", "name": "Data Cache Refills from System (Northbridge)"},
{"select": "c80", "name": "Instruction Cache Fetches"},
{"select": "c82", "name": "Instruction Cache Refills from L2"},
{"select": "c83", "name": "Instruction Cache Refills from System (Northbridge)"},
{"select": "c47d", "name": "Requests to L2 Cache [TLB fill]"},
{"select": "c47e", "name": "L2 Cache Misses [TLB fill]"},
{"select": "cf74e0", "name": "Read Requests to L3 Cache"},
{"select": "cf74e1", "name": "L3 Cache Misses"}
]

def get_event_with_name(name):
return [event for event in events if event["name"] == name][0]

def event_list():
ret = ""
for event in events:
ret += "-e r" + event["select"] + " "
return ret

def store_count_to_events(perf_output_lines):
# Sample perf-stat output line
# 1565650 raw 0xc0 # 0.000 M/sec ( +- 1.457% ) (scaled from 75.04%)
# <not counted> raw 0xc0 # 0.000 M/sec
count_pat = re.compile("^ <span style="font-weight:bold;">([0-9]+|<not counted>).</span>")
variance_pat = re.compile("\+- *([0-9]+\.[0-9]+)%")

lines = perf_output_lines
for event in events:
search_str = "raw 0x" + event["select"]
event_line = "".join([line for line in lines if line.find(search_str) != -1])

count_mat = count_pat.match(event_line)
variance_mat = variance_pat.search(event_line)

if count_mat is None:
print("Unexpected event format:\n %s"
% event_line)
exit(1)
if count_mat.group(1) != "<not counted>":
event["count"] = int(count_mat.group(1))
if variance_mat is not None:
event["variance"] = float(variance_mat.group(1))
else:
event["variance"] = -1.0
else:
event["count"] = -1
event["variance"] = -1.0

def print_running_env(perf_output_lines):
search_str = "Performance counter stats for"
print("".join([line for line in perf_output_lines if line.find(search_str) != -1]))

def print_elapsed_time(perf_output_lines):
search_str = "seconds time elapsed"
print("".join([line for line in perf_output_lines if line.find(search_str) != -1]))

def print_counted_events():
for event in events:
if event["count"] >= 0 and event["variance"] >= 0.0:
print("%15s %55s ( +- %6.2f%%)"
% (str(event["count"]), event["name"], event["variance"]))
elif event["count"] >= 0 and event["variance"] < 0.0:
print("%15s %55s"
% (str(event["count"]), event["name"]))
else:
print("%15s %55s"
% ("<not counted>", event["name"]))

def print_calculated_events():
def _clever_calc(rhs, terms):
"""
@returns:
if `terms' does not have any value less than 0:
The result of rhs
else:
Value less than 0
"""
if len([term for term in terms if term < 0]) > 0:
return -1
else:
return rhs

def _clever_print(val, ev_name):
"""
@parameters:
val: Value to print. Must be int or float.
Value less than 0 means that the event is <not counted>.
"""
is_valid_val = (val >= 0)
if is_valid_val and type(val) == types.IntType:
print("%15d %s" % (val, ev_name))
elif is_valid_val and type(val) == types.FloatType:
print("%14.3f%% %s" % (100.0 * val, ev_name))
elif not is_valid_val:
print("%15s %s" % ("<not counted>", ev_name))
else:
print("Unexpected calculated value: " + str(val))

retired_instructions = get_event_with_name("Retired Instructions")["count"]
_clever_print(retired_instructions, "Retired Instructions")

# Data Cache
data_cache_accesses = get_event_with_name("Data Cache Accesses")["count"]
_clever_print(data_cache_accesses, "Data Cache Accesses")

data_cache_request_rate = _clever_calc(float(data_cache_accesses) / float(retired_instructions),
[data_cache_accesses, retired_instructions])
_clever_print(data_cache_request_rate, "Data Cache Request Rate")

data_cache_refills_from_L2 = get_event_with_name("Data Cache Refills from L2")["count"]
data_cache_refills_from_system = get_event_with_name("Data Cache Refills from System (Northbridge)")["count"]
data_cache_misses = _clever_calc(data_cache_refills_from_L2 + data_cache_refills_from_system,
[data_cache_refills_from_L2, data_cache_refills_from_system])
_clever_print(data_cache_misses, "Data Cache Misses")

data_cache_miss_ratio = _clever_calc(float(data_cache_misses) / float(data_cache_accesses),
[data_cache_misses, data_cache_accesses])
_clever_print(data_cache_miss_ratio, "Data Cache Miss Ratio")

# Instruction Cache
instruction_cache_fetches = get_event_with_name("Instruction Cache Fetches")["count"]
_clever_print(instruction_cache_fetches, "Instruction Cache Fetches")

instruction_cache_request_rate = _clever_calc(float(instruction_cache_fetches) / float(retired_instructions),
[instruction_cache_fetches, retired_instructions])
_clever_print(instruction_cache_request_rate, "Instruction cache Request Rate")

instruction_cache_refills_from_L2 = get_event_with_name("Instruction Cache Refills from L2")["count"]
instruction_cache_refills_from_system = get_event_with_name("Instruction Cache Refills from System (Northbridge)")["count"]
instruction_cache_misses = _clever_calc(instruction_cache_refills_from_L2 + instruction_cache_refills_from_system,
[instruction_cache_refills_from_L2, instruction_cache_refills_from_system])
_clever_print(instruction_cache_misses, "Instruction Cache Misses")

instruction_cache_miss_ratio = _clever_calc(float(instruction_cache_misses) / float(instruction_cache_fetches),
[instruction_cache_misses, instruction_cache_fetches])
_clever_print(instruction_cache_miss_ratio, "Instruction Cache Miss Ratio")

# L2 Cache
L2_misses_TLB = get_event_with_name("Requests to L2 Cache [TLB fill]")["count"]
L2_requests = _clever_calc(data_cache_misses + instruction_cache_misses + L2_misses_TLB,
[data_cache_misses, instruction_cache_misses, L2_misses_TLB])
_clever_print(L2_requests, "L2 Requests")

L2_request_rate = _clever_calc(float(L2_requests) / float(retired_instructions),
[L2_requests, retired_instructions])
_clever_print(L2_request_rate, "L2 Request Rate")

L2_misses = _clever_calc(data_cache_refills_from_system + instruction_cache_refills_from_system + L2_misses_TLB,
[data_cache_refills_from_system, instruction_cache_refills_from_system, L2_misses_TLB])
_clever_print(L2_misses, "L2 Misses")

L2_miss_ratio = _clever_calc(float(L2_misses) / float(L2_requests),
[L2_misses, L2_requests])
_clever_print(L2_miss_ratio, "L2 Miss Ratio")

# L3 Cache
L3_requests = get_event_with_name("Read Requests to L3 Cache")["count"]
_clever_print(L3_requests, "Read Requests to L3 Cache")

L3_request_rate = _clever_calc(float(L3_requests) / float(retired_instructions),
[L3_requests, retired_instructions])
_clever_print(L3_request_rate, "L3 Request Rate")

L3_misses = get_event_with_name("L3 Cache Misses")["count"]
_clever_print(L3_misses, "L3 Misses")

L3_miss_ratio = _clever_calc(float(L3_misses) / float(L3_requests),
[L3_misses, L3_requests])
_clever_print(L3_miss_ratio, "L3 Miss Ratio")


def main():
command = "perf stat " + event_list() + " ".join(sys.argv[1:])
p = subprocess.Popen(command, shell=True,
stderr=subprocess.PIPE)
perf_output_lines = p.stderr.readlines()
store_count_to_events(perf_output_lines)

print("=== Running Environment ===")
print_running_env(perf_output_lines)
print("=== Counted Events ===")
print_counted_events()
print("\n=== Calculated Events ===")
print_calculated_events()
print("\n=== Elapsed Time ===")
print_elapsed_time(perf_output_lines)

if __name__ == "__main__":
main()

スクリプトの実装上の細かい注意点

キャッシュミスなどの計算値は,計算に必要なハードウェアイベントが正しく測定されていなければ出せません.
更に,計算値Aを利用して計算値Bを出す場合も,計算値Aが正しい値である必要があります.

つまり,「測定値が正しく採れなかった場合,影響が連鎖する」という性質があります.
スクリプトでは,
_clever_calc , _clever_print
関数によって,この連鎖関係を把握しています.

author Sho Nakatani a.k.a. laysakura

東京大学大学院 情報理工学系研究科 電子情報学専攻 修士課程で並列分散処理・ストリーム処理・データベースを研究。
2014年4月に株式会社ディー・エヌ・エーにエンジニアスペシャリストとして入社し、ソーシャルゲームのサーバサイド共通基盤の開発に従事。
2016年8月より、オンライン証券会社株式会社FOLIOに入社。バックエンドシステム開発・プロジェクトマネージメント・Engineering Managementに従事。