キャッシュの局所性：読み出す順序で何が変わるか

8 × 8を列ごとにを押し、ヒットが0回になる理由を説明してください。次に、4バイトのint型からなる1024 × 1024の行列と、ラインサイズ64バイト、容量32 KiBのダイレクトマップ方式のキャッシュを考えます。行ごとに足し合わせる場合と列ごとに足し合わせる場合、メモリから何バイト転送されるでしょうか。各行の末尾にライン1本分の余白を加えると、改善するでしょうか。

この問題をツールで開く

1. このページのモデルでは、1行は8 × 4 = 32バイトで、ライン2本分です。したがって行iの先頭はライン2i mod 8に割り当てられ、第0列が使うのはライン0、2、4、6だけ。a[4][0]がa[0][0]のあったラインを使うため、ループがa[0][1]に戻るときには必要なブロックがなく、64回中0回のヒットになります。行ごとなら、16バイトの各ブロックでミスは一度ずつ、計16回なので、ヒットは48回。ヒット率は1 − 4/16 = 75%です。

   $$8\times 4=32\text{bytes}=2\text{lines}:2i\mathrm{mod}8\in \{0,2,4,6\},64-16=48\text{hits by rows}$$

2. 大きい方のキャッシュには、32,768 / 64 = 512本のラインがあります。行ごとに読むと、64バイトの各ラインにint型の要素が16個入り、最初の読み出しだけがミスになります。ミスは1,048,576 / 16 = 65,536回、ヒット率は1 − 4/64 = 93.75%。転送量は65,536 × 64 = 4,194,304バイトで、行列全体をちょうど一度読み込む量です。

   $$\frac{32768}{64}=512\text{lines},\frac{1048576}{16}=65536\text{misses},65536\times 64=4194304$$

3. 列ごとでは、1行が4,096バイト、ライン64本分なので、行iの先頭はライン64i mod 512に割り当てられます。各列が使うラインは512本中8本だけです。a[8][0]がa[0][0]のブロックを追い出し、ループがa[0][1]に戻るよりずっと前に、必要なブロックは失われています。1,048,576回の読み出しがすべてミスとなり、転送量は67,108,864バイト。行ごとの16倍です。

   $$\frac{4096}{64}=64:64i\mathrm{mod}512\text{takes}8\text{values},1048576\times 64=67108864$$

4. 各行にint型の要素16個分の余白を加えると、1行は4,160バイト、ライン65本分になります。65と512は互いに素なので、各列の割り当て先は512本すべてのラインに広がります。それでもヒットはありません。1列で読み出すブロックは1,024個、キャッシュに収まるのは512個なので、次の列で必要になる前に、どのブロックも追い出されてしまいます。

   $$\frac{4160}{64}=65,\gcd (65,512)=1,1024\text{blocks}>512\text{lines}$$