キャッシュの書き込みと置換
write-back・write-throughと書込みミス時の方針を、保持データと転送量で比較します。
説明
キャッシュへ書いた値をいつ下位メモリへ反映するかは方式によって異なります。write-throughは書込み時に下位へも反映し、write-backは変更したラインを保持して、追出しなどの必要時に反映します。dirtyは下位と異なる変更済みデータを含む状態です。
4バイトのラインと16バイトの主記憶を使います。同じバイトを二回変更してから追い出し、主記憶がいつ変わるかを追います。次に書込みミスでラインを確保する場合としない場合を比べ、最後に置換先の選び方を確認します。
1主記憶からラインを取り込む
主記憶のアドレス0〜15には、それぞれ0〜15の値を置きます。まず0〜3の4バイトをキャッシュへ読み込みます。
memory = bytearray(range(16))主記憶16バイト; line = {'base':0,'data':bytearray(memory[:4]),'dirty':False}先頭4バイトを別の領域へコピー; list(memory),line主記憶とキャッシュキャッシュは主記憶のコピーを持ち、dirtyはFalseです。bytearrayで別の領域を作っているので、片方の変更が自動的にもう片方へ反映される設定にはしていません。
2write-backで1バイト変更
キャッシュ内のオフセット1へ99を書きます。下位メモリにはまだ反映せず、dirtyを立てます。
line['data'][1] = 99キャッシュの1バイトを変更; line['dirty'] = True変更済みを記録; list(line['data']),line['dirty'],list(memory[:4])二つの保持値を比較キャッシュは[0,99,2,3]、主記憶は[0,1,2,3]です。最新の値はキャッシュ側にあります。dirtyはエラーという意味ではなく、書戻しが必要な変更を含むという管理情報です。
3同じ場所をもう一度変更
次に同じバイトへ98を書きます。途中の99を主記憶へ送らず、最新値98を保持します。
line['data'][1] = 98最新値で上書き; list(line['data']),list(memory[:4]),line['dirty']最新コピーと下位メモリdirtyはTrueのままです。書戻し時には現在のラインを送るので、上書きされて残っていない99を後から別送する必要はありません。
4dirtyラインを追い出す
同じ格納場所へアドレス8のラインを入れる前に、古い4バイトを主記憶へ書き戻します。ここではライン全体を転送する方式とします。
memory[line['base']:line['base']+4] = line['data']古い基点へ4バイトを書き戻す; writeback_bytes = len(line['data'])書戻し量; line = {'base':8,'data':bytearray(memory[8:12]),'dirty':False}新しいラインを読み込む; list(memory[:4]),writeback_bytes,line主記憶・転送量・新ライン主記憶のアドレス1が98になります。古いラインの書戻し4バイトに加え、新しいラインの読込み4バイトが必要です。cleanなラインなら、この書戻しは不要です。
5write-throughなら毎回反映する
同じ初期状態から、1バイト書込みごとにキャッシュと主記憶を更新します。下位への転送も1バイト単位と置きます。
through_memory = bytearray(range(16)); through_cache = bytearray(through_memory[:4])初期状態を作り直す; through_cache[1] = through_memory[1] = 99一回目を両方へ反映; first = list(through_memory[:4])一回目の状態; through_cache[1] = through_memory[1] = 98二回目も反映; first,list(through_memory[:4]),2各時点と下位への書込み量主記憶も99、98と変わり、二回で2バイトの書込みです。この小さい例ではライン全体4バイトを書き戻すより少なくなります。write-backが常に転送バイト数を減らすとは限らず、更新回数や転送単位にも依存します。
6書込みミスでラインを確保する
空のキャッシュからアドレス1へ書くwrite-allocateの例です。下位から4バイトを取得し、そのうち1バイトを変更します。
allocate_memory = bytearray(range(16))初期主記憶; allocated = bytearray(allocate_memory[:4])書込み前にラインを取得; allocated[1] = 99キャッシュへ変更; {'read_bytes':4,'cached_value':allocated[1],'memory_value':allocate_memory[1]}読込み量と保持値write-backとの組合せなので主記憶は1、キャッシュは99です。続けて同じラインを読むならキャッシュを使えます。書込みミス時の確保方針と、反映時期の方針は別の判断です。
7書込みミスで確保しない
no-write-allocateでは、ここでは1バイトを下位へ直接書き、キャッシュへラインを入れません。後で読むときに初めて4バイトを取得します。
bypass_memory = bytearray(range(16))初期主記憶; bypass_memory[1] = 99下位へ直接1バイト書く; later_read = bytearray(bypass_memory[:4])後の読出しで取得; {'write_bytes':1,'later_read_bytes':4,'value':later_read[1]}転送量と読出し値最初の書込みだけなら4バイト読込みを避けられますが、後で読むとミスします。書いた領域を再利用するかどうかによって、確保する利点が変わります。
8LRUとFIFOの追出し先
2ラインを置けるセットに0と1を入れ、0を再利用してから2を追加します。LRUは最近使っていない1、FIFOは先に入った0を追い出します。
from collections import OrderedDict使用順を保持する辞書; lru = OrderedDict([(0,'clean'),(1,'dirty')])二つのラインと状態; lru.move_to_end(0)0を最近使用した位置へ; lru_victim = lru.popitem(last=False)最も古い使用のラインを追出し; fifo = [0,1]; fifo_victim = fifo.pop(0)先に入った順の追出し; lru_victim,fifo_victim選ばれたライン追出し先が異なり、この状態ではLRUが選ぶ1はdirtyなので書戻しが必要です。置換方針、dirty管理、書込みミスの方針を組み合わせて、実際の転送が決まります。
まとめ
write-backは変更済みラインを保持し、追出し時などに下位へ反映します。
書込みミスで確保するかどうかと、書込みを反映する時期は別の方針です。
転送量は更新回数・転送単位・置換先のdirty状態に左右されます。
操作履歴と解説を振り返れます。
Python 3
memory = bytearray(range(16)); line = {'base':0,'data':bytearray(memory[:4]),'dirty':False}; list(memory),line([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], {'base': 0, 'data': bytearray(b'\x00\x01\x02\x03'), 'dirty': False})line['data'][1] = 99; line['dirty'] = True; list(line['data']),line['dirty'],list(memory[:4])([0, 99, 2, 3], True, [0, 1, 2, 3])
line['data'][1] = 98; list(line['data']),list(memory[:4]),line['dirty']([0, 98, 2, 3], [0, 1, 2, 3], True)
memory[line['base']:line['base']+4] = line['data']; writeback_bytes = len(line['data']); line = {'base':8,'data':bytearray(memory[8:12]),'dirty':False}; list(memory[:4]),writeback_bytes,line([0, 98, 2, 3], 4, {'base': 8, 'data': bytearray(b'\x08\t\n\x0b'), 'dirty': False})through_memory = bytearray(range(16)); through_cache = bytearray(through_memory[:4]); through_cache[1] = through_memory[1] = 99; first = list(through_memory[:4]); through_cache[1] = through_memory[1] = 98; first,list(through_memory[:4]),2([0, 99, 2, 3], [0, 98, 2, 3], 2)
allocate_memory = bytearray(range(16)); allocated = bytearray(allocate_memory[:4]); allocated[1] = 99; {'read_bytes':4,'cached_value':allocated[1],'memory_value':allocate_memory[1]}{'read_bytes': 4, 'cached_value': 99, 'memory_value': 1}bypass_memory = bytearray(range(16)); bypass_memory[1] = 99; later_read = bytearray(bypass_memory[:4]); {'write_bytes':1,'later_read_bytes':4,'value':later_read[1]}{'write_bytes': 1, 'later_read_bytes': 4, 'value': 99}from collections import OrderedDict; lru = OrderedDict([(0,'clean'),(1,'dirty')]); lru.move_to_end(0); lru_victim = lru.popitem(last=False); fifo = [0,1]; fifo_victim = fifo.pop(0); lru_victim,fifo_victim((1, 'dirty'), 0)
演習完了