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

キャッシュコヒーレンスと偽共有

異なる変数が同じキャッシュラインに入る場合の所有権移動を追い、配置を変えて比較します。

説明

複数コアが同じメモリを使うとき、各キャッシュのコピーの整合性を保つためにコヒーレンス機構が働きます。他コアのコピーを無効化する方式では、変数単位ではなくキャッシュライン単位で処理します。

64バイトのラインを仮定し、別々のコアが別々の8バイトカウンタを交互に更新する例を使います。同じラインにある場合と、ラインを分けた場合の所有権移動を数えます。読み取り共有、同じ変数の共有、アトミック操作との違いも整理します。

1別の変数でも同じラインに入る

Aのカウンタを0x1000、Bを0x1008に置きます。各8バイトで、アドレスを64で割った商がライン番号です。

line_size = 64この例のライン幅; addresses = {'A':0x1000,'B':0x1008}カウンタの配置; [(name,hex(address),address//line_size,address%line_size) for name,address in addresses.items()]アドレス・ライン・位置

二つは異なるアドレスですが、同じライン64のオフセット0と8です。変数の8バイト範囲は重ならなくても、コヒーレンスの管理単位は共有しています。

2書込み所有者の交替を記録

一つのラインを書き込める所有者を一コアとする簡略モデルです。別コアが書くと所有者を交替し、前のコピーを無効化します。

def ownership_trace(events):書込みの時系列

owners = {}ラインごとの所有者

result = []記録

for core,address in events:順に書込む

line = address//64管理単位のライン

previous = owners.get(line)前所有者

invalidated = previous is not None and previous != core他コアのコピーを無効化するか

owners[line] = core新しい所有者

result.append((core,hex(address),line,previous,invalidated))所有権移動を保存

return result履歴

列は書込コア・アドレス・ライン・前所有者・無効化の有無です。実際のMESIなどの全状態は省き、交互の書込みで所有者が何回変わるかに着目しています。

3交互更新でラインが往復する

コア0がA、コア1がBを一回ずつ書く組を4回繰り返します。

events = [(0,addresses['A']),(1,addresses['B'])]*4別カウンタの交互更新; shared_trace = ownership_trace(events)所有者の履歴; shared_trace,sum(row[4] for row in shared_trace)履歴と無効化回数

最初の取得を除き7回の所有者交替です。プログラム上は別の変数だけを使っていても、同じラインへの交互書込みで通信が増えます。これがfalse sharingの例です。

4ライン境界をまたぐ位置へ移す

Bを0x1040へ移し、Aとは別の64バイトラインに置きます。更新回数とコアは同じです。

separated = [(0,0x1000),(1,0x1040)]*4別ラインの配置; separate_trace = ownership_trace(separated)同じ更新順で計算; separate_trace,sum(row[4] for row in separate_trace)所有者と無効化回数

各コアが自分のラインを保持し続け、このモデルでは所有者交替0回です。配置には先頭アドレスのアラインメントと、実際のCPUのラインサイズを考慮する必要があります。

5同じコアでまとめて更新する

配置を元に戻しても、コア0の4回の後にコア1の4回を行えば交替は1回です。

batched = [(0,0x1000)]*4+[(1,0x1008)]*4コアごとにまとめた更新; batched_trace = ownership_trace(batched)所有権の履歴; sum(row[4] for row in batched_trace),batched_trace交替回数と順序

アクセス順も通信回数へ影響します。ただし実際にまとめて実行するには、処理順序や応答性の要件を守れることが条件です。計算モデルで減った回数を、そのまま速度倍率とは扱いません。

6読み取りだけなら共有できる

二つのコアが読み取るだけなら、両方が共有状態Sのコピーを持てます。片方が書き込むと、他方を無効Iへし、書込側を変更済みMへ移す例を考えます。

states = {0:'S',1:'S'}両コアに読取り共有のコピー; before = states.copy()書込み前の状態; states[0] = 'M'; states[1] = 'I'コア0の書込みで他方を無効化; before,states共有から排他的な変更へ

読取り共有そのものが毎回の無効化を生むわけではありません。同じラインの共有と、少なくとも一方の書込みが組み合わさることが、false sharingによる競合を考える条件です。

7同じ変数を使う場合

今度は両コアが同じアドレス0x1000を書きます。これは変数自体を共有するtrue sharingです。

same_variable = ownership_trace([(0,0x1000),(1,0x1000)]*4)同じカウンタへの更新; sum(row[4] for row in same_variable)所有者交替

交替は同じ7回ですが原因は別です。パディングで別の変数を離す方法では、一つの共有変数を二つのラインへ分割することはできません。通信を減らすには更新の集約など、処理方法の検討が必要です。

8コヒーレンスと更新の原子性

二つの処理が同じ初期値0を読み、それぞれ1を足して書くと、一方の加算が失われる順序を作れます。

counter = 0; read_a = counter; read_b = counter両方が同じ初期値を読む; counter = read_a+1; after_a = counterAが更新; counter = read_b+1Bが古い値から更新; read_a,read_b,after_a,counter読取値と最終値

最後は1で、二回増やしたつもりの2にはなりません。キャッシュのコピーを整合させる仕組みだけでは、読取り・加算・書込み全体は不可分になりません。アトミック操作やロックによる正しさと、ライン共有による性能を分けて扱います。

まとめ

別の変数でも同じラインへ書き込むと、コア間の無効化が増えることがあります。

配置・アラインメント・アクセス順を変えると、所有権移動の頻度も変わります。

コヒーレンスは複合操作の原子性を保証せず、同期による正しさは別に設計します。

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

Python 3

line_size = 64; addresses = {'A':0x1000,'B':0x1008}; [(name,hex(address),address//line_size,address%line_size) for name,address in addresses.items()]

[('A', '0x1000', 64, 0), ('B', '0x1008', 64, 8)]

def ownership_trace(events):
    owners = {}
    result = []
    for core,address in events:
        line = address//64
        previous = owners.get(line)
        invalidated = previous is not None and previous != core
        owners[line] = core
        result.append((core,hex(address),line,previous,invalidated))
    return result

events = [(0,addresses['A']),(1,addresses['B'])]*4; shared_trace = ownership_trace(events); shared_trace,sum(row[4] for row in shared_trace)

([(0, '0x1000', 64, None, False), (1, '0x1008', 64, 0, True), (0, '0x1000', 64, 1, True), (1, '0x1008', 64, 0, True), (0, '0x1000', 64, 1, True), (1, '0x1008', 64, 0, True), (0, '0x1000', 64, 1, True), (1, '0x1008', 64, 0, True)], 7)

separated = [(0,0x1000),(1,0x1040)]*4; separate_trace = ownership_trace(separated); separate_trace,sum(row[4] for row in separate_trace)

([(0, '0x1000', 64, None, False), (1, '0x1040', 65, None, False), (0, '0x1000', 64, 0, False), (1, '0x1040', 65, 1, False), (0, '0x1000', 64, 0, False), (1, '0x1040', 65, 1, False), (0, '0x1000', 64, 0, False), (1, '0x1040', 65, 1, False)], 0)

batched = [(0,0x1000)]*4+[(1,0x1008)]*4; batched_trace = ownership_trace(batched); sum(row[4] for row in batched_trace),batched_trace

(1, [(0, '0x1000', 64, None, False), (0, '0x1000', 64, 0, False), (0, '0x1000', 64, 0, False), (0, '0x1000', 64, 0, False), (1, '0x1008', 64, 0, True), (1, '0x1008', 64, 1, False), (1, '0x1008', 64, 1, False), (1, '0x1008', 64, 1, False)])

states = {0:'S',1:'S'}; before = states.copy(); states[0] = 'M'; states[1] = 'I'; before,states

({0: 'S', 1: 'S'}, {0: 'M', 1: 'I'})

same_variable = ownership_trace([(0,0x1000),(1,0x1000)]*4); sum(row[4] for row in same_variable)

counter = 0; read_a = counter; read_b = counter; counter = read_a+1; after_a = counter; counter = read_b+1; read_a,read_b,after_a,counter

(0, 0, 1, 1)

演習完了