一覧OS-02-1 · メモリ階層とキャッシュ

キャッシュのアドレス分解とヒット判定

アドレスをタグ・インデックス・オフセットへ分け、アクセス順と容量によるミスの違いを調べます。

説明

CPUキャッシュはメモリの一部分をライン単位で保持します。要求したアドレスのラインがあればヒット、なければミスです。近いアドレスを続けて使う空間的局所性と、同じデータを再利用する時間的局所性によって効果が変わります。

1ライン16バイト、4ラインのダイレクトマップ方式を使います。アドレスから配置先を計算し、逐次アクセス・繰返し・同じ配置先の競合を比較します。最後にL1とL2のミス率を使って平均アクセス時間を計算し、階層の役割を確かめます。

1アドレスの三つの欄

下位4ビットがライン内位置、その上2ビットが4通りの配置先、それより上がタグです。

line_bytes = 16; slots = 4ライン幅と配置先数; split = lambda address: (address//(line_bytes*slots),(address//line_bytes)%slots,address%line_bytes)タグ・インデックス・オフセット; [(hex(a),split(a)) for a in [0,4,15,16,60,64]]境界付近のアドレス

0と4は同じライン、0と64は同じ配置先でタグが異なります。配置先だけではどのメモリ領域が入っているか分からないので、タグの一致も調べます。

2アクセスごとの状態を記録

各配置先に現在のタグを一つ保存します。未使用はNoneとし、ミスしたらその配置先のタグを置き換えます。

def cache_trace(addresses,slot_count=4):アクセス列と配置先数

tags = [None]*slot_count空のタグ配列

trace = []記録

for address in addresses:順番にアクセス

block = address//16メモリのライン番号

index,tag = block%slot_count,block//slot_count配置先とタグ

hit = tags[index] == tag現在のタグと一致するか

old = tags[index]置換前のタグ

tags[index] = tag要求ラインを保持

trace.append((address,index,tag,'hit' if hit else 'miss',old))判定を記録

return trace時系列を返す

列はアドレス・配置先・タグ・判定・置換前タグです。キャッシュのデータ内容を省き、どのラインを保持しているかだけを追うモデルです。各呼出しは空のキャッシュから開始します。

3隣り合う4バイト要素

0から60まで4バイト刻みで読むと、各ライン内の4要素を続けて使います。

sequential = list(range(0,64,4))隣接要素へのアクセス; sequential_trace = cache_trace(sequential)状態を計算; sequential_trace,sum(row[3] == 'miss' for row in sequential_trace)履歴とミス数

ミスは0・16・32・48の4回で、残る12回はヒットです。最初の読出しで16バイト全体が入るため、同じラインの後続要素を利用できます。

4同じ範囲をもう一度読む

64バイトの範囲はちょうど4ラインに収まります。二回連続で読むと後半のミスはどうなるか確認します。

twice = cache_trace(sequential+sequential)二周分を連続実行; [row[3] for row in twice[16:]]二周目の判定,sum(row[3] == 'miss' for row in twice)全体のミス数

二周目は全てヒットし、全32回でもミスは最初の4回だけです。キャッシュへ残っているデータを時間を置かず再利用する例です。

5容量に余裕があっても競合する

アドレス0と64を交互に読みます。使うデータは2ラインだけですが、両方とも配置先0です。

conflict = cache_trace([0,64,0,64,0,64])同じ配置先を交互に使用; conflictタグの入替え履歴

6回全てがミスです。一方を入れるたびにもう一方が追い出されます。ダイレクトマップでは、全体容量に収まることだけではヒットを保証できません。

6配置先数を増やす

同じ16バイトラインで配置先を8個へ増やすと、0と64は別の場所へ入ります。

expanded = cache_trace([0,64,0,64,0,64],8)配置先を8個へ; expanded,sum(row[3] == 'miss' for row in expanded)判定とミス数

ミスは最初の2回だけになります。セットアソシアティブ方式では、一つのセットに複数の格納場所を用意する方法もあります。この操作は配置先数を増やした比較で、連想度を変えた比較とは区別します。

7容量を超える繰返し

今度は5ラインを4配置先のキャッシュへ順に入れ、二周します。0と64が競合するほか、全5ラインを同時には保持できません。

five_lines = cache_trace([0,16,32,48,64]*2)容量より多いラインを二周; five_lines[5:],sum(row[3] == 'miss' for row in five_lines)二周目と全ミス数

二周目の0と64がミスとなり、全体は7ミスです。初回の必須ミス、容量による制約、配置による競合を考えると、ミス率だけより原因を詳しく説明できます。

8二段階の平均アクセス時間

L1に1ns、L1ミス時のL2確認に追加4ns、L2もミスした場合の主記憶に追加50nsとします。L1ミス率10%、L2の局所ミス率20%を使います。

l1_time,l2_extra,memory_extra = 1,4,50各段の追加時間; l1_miss,l2_local_miss = 0.1,0.2ミス率の分母を区別; l1_time+l1_miss*(l2_extra+l2_local_miss*memory_extra)平均時間,l1_miss*l2_local_miss主記憶へ到達する割合

平均2.4ns、主記憶へ到達する割合2%です。L2の20%はL1をミスしてL2へ来た要求の中の割合です。遅延の重なりやプリフェッチを含めない直列モデルなので、実機の測定値とは用途を分けます。

まとめ

ライン内位置・配置先・タグを分けると、ヒットと競合の理由をアドレスから説明できます。

空間的局所性と時間的局所性は、アクセス順と保持できる範囲に依存します。

階層の平均時間を求める際は、局所ミス率と全体に対するミス率の分母をそろえます。

操作履歴と解説を振り返れます。

Python 3

line_bytes = 16; slots = 4; split = lambda address: (address//(line_bytes*slots),(address//line_bytes)%slots,address%line_bytes); [(hex(a),split(a)) for a in [0,4,15,16,60,64]]

[('0x0', (0, 0, 0)), ('0x4', (0, 0, 4)), ('0xf', (0, 0, 15)), ('0x10', (0, 1, 0)), ('0x3c', (0, 3, 12)), ('0x40', (1, 0, 0))]

def cache_trace(addresses,slot_count=4):
    tags = [None]*slot_count
    trace = []
    for address in addresses:
        block = address//16
        index,tag = block%slot_count,block//slot_count
        hit = tags[index] == tag
        old = tags[index]
        tags[index] = tag
        trace.append((address,index,tag,'hit' if hit else 'miss',old))
    return trace

sequential = list(range(0,64,4)); sequential_trace = cache_trace(sequential); sequential_trace,sum(row[3] == 'miss' for row in sequential_trace)

([(0, 0, 0, 'miss', None), (4, 0, 0, 'hit', 0), (8, 0, 0, 'hit', 0), (12, 0, 0, 'hit', 0), (16, 1, 0, 'miss', None), (20, 1, 0, 'hit', 0), (24, 1, 0, 'hit', 0), (28, 1, 0, 'hit', 0), (32, 2, 0, 'miss', None), (36, 2, 0, 'hit', 0), (40, 2, 0, 'hit', 0), (44, 2, 0, 'hit', 0), (48, 3, 0, 'miss', None), (52, 3, 0, 'hit', 0), (56, 3, 0, 'hit', 0), (60, 3, 0, 'hit', 0)], 4)

twice = cache_trace(sequential+sequential); [row[3] for row in twice[16:]],sum(row[3] == 'miss' for row in twice)

(['hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit', 'hit'], 4)

conflict = cache_trace([0,64,0,64,0,64]); conflict

[(0, 0, 0, 'miss', None), (64, 0, 1, 'miss', 0), (0, 0, 0, 'miss', 1), (64, 0, 1, 'miss', 0), (0, 0, 0, 'miss', 1), (64, 0, 1, 'miss', 0)]

expanded = cache_trace([0,64,0,64,0,64],8); expanded,sum(row[3] == 'miss' for row in expanded)

([(0, 0, 0, 'miss', None), (64, 4, 0, 'miss', None), (0, 0, 0, 'hit', 0), (64, 4, 0, 'hit', 0), (0, 0, 0, 'hit', 0), (64, 4, 0, 'hit', 0)], 2)

five_lines = cache_trace([0,16,32,48,64]*2); five_lines[5:],sum(row[3] == 'miss' for row in five_lines)

([(0, 0, 0, 'miss', 1), (16, 1, 0, 'hit', 0), (32, 2, 0, 'hit', 0), (48, 3, 0, 'hit', 0), (64, 0, 1, 'miss', 0)], 7)

l1_time,l2_extra,memory_extra = 1,4,50; l1_miss,l2_local_miss = 0.1,0.2; l1_time+l1_miss*(l2_extra+l2_local_miss*memory_extra),l1_miss*l2_local_miss

(2.4000000000000004, 0.020000000000000004)

演習完了