配列から配列へ要素をコピーする関数におけるキャッシュミス数とキャッシュヒット数の数え方

Question

C言語で以下のような2次元配列から2次元配列へ要素をコピーする関数があるとします

typedef int array[2][2];

void copy_arr(array A, array B){
    int i, j;
    
    for(i=0; i<2; ++i){
        for(j=0; j<2; ++j){
            A[j][i] = B[i][j];
        }
    }
}

もし

• キャッシュが1ブロックサイズ=8バイトで合計容量16バイトまで
• sizeof(int)が4バイト
• キャッシュがダイレクトマップ方式で最初は空
• Bがアドレス0から始まってAがアドレス16から始まる

とした場合ですが、

1. キャッシュにB[i][j]が無い(ミス)ので、Bの配列を全てキャッシュに格納(容量が16バイトまでなのでキャッシュはBの要素で埋まる)した後にB[i][j]を読み込む

2. キャッシュにA[j][i]が無い(ミス)ので、Aの配列を全てキャッシュに格納(容量が16バイトまでなのでキャッシュはAの要素で埋まる)した後にA[j][i]を読み込む

3. キャッシュにB[i][j+1]が無い(ミス)ので、Bの配列を全てキャッシュに格納(容量が16バイトまでなのでキャッシュはBの要素で埋まる)した後にB[i][j+1]を読み込む

4.キャッシュにA[j+1][i]が無い(ミス)ので、Aの配列を全てキャッシュに格納(容量が16バイトまでなのでキャッシュはAの要素で埋まる)した後にA[j+1][i]を読み込む

（以下(8)まで同じ要領でミスが続く)
となりミス率は100% (ヒット率は0%) だと思っていたのですが教科書によるとB[1][1]をコピーする時唯一ヒットとなると書いてありました。これはなぜなのでしょうか…？

Answer 1

ダイレクトマップ方式を完全に誤解していました。

ブロックサイズが8なのでブロックオフセットのビット数は2^b = B より b = 3
セット数はS=2なのでセットインデックスのビット数はS = 2^s より s = 1

よってキャッシュのどのセット(今回の場合だと 0 or 1)に配列がロードされるかはアドレスの第3ビットによって決定されるのでしたね

BとAのそれぞれの要素をArr[int1][int2]の形式にすると

B[0][0]	B[0][1]	B[1][0]	B[1][1]
0-3バイト目	4-7バイト目	8-11バイト目	12ｰ15バイト目

A[0][0]	A[0][1]	A[1][0]	A[1][1]
16-19バイト目	20-23バイト目	24-27バイト目	28ｰ31バイト目

アドレスを見るとそれぞれB[0]は0x0000, B[1]は0x1000, A[0]は0x10000, そしてA[1]は0x11000 ⇛ 第3ビットによりA[0],B[0]はセット0へ,A[1],B[1]はセット1へ格納となるのですね

流れとしては
i=0, j=0
B[0][0]をセット0へ(ミス)⇛ セット0のキャッシュが空の為,新しく格納
A[0][0]をセット0へ(ミス)⇛ B[0]を追出し

i=0, j=1
B[0][1]をセット0へ(ミス)⇛ A[0]を追出し
A[1][0]をセット1へ(ミス)⇛ セット1のキャッシュが空の為,新しく格納

i=1, j=0
B[1][0]をセット1へ(ミス)⇛ A[1]を追出し
A[0][1]をセット0へ(ミス)⇛ B[0]を追出し

i=1, j=1
B[1][1]は既にB[1]がセット1に格納されていた為何もしない(ヒット)
A[1][1]をセット1へ(ミス)⇛ B[1]を追出し

で結局唯一のヒットはB[1][1]の時ということがわかりました。

Answer 2

キャッシュが1ブロックサイズ=8バイト

ということであれば、B[1][0]を参照した場合、B[1]（2個分8バイト）だけがキャッシュに乗ります。それを前提に考え直してみてください。

Comments

[ijuya_yika]

ご回答ありがとうございます。
頂いたコメントを元に考え直したのですが、参照の順番は`B[0]`(ミス) ➝ `A[0]`(ミス) ➝ `B[0]`(ヒット) ➝
`A[1]`(ミス) ➝ `B[1]`(ミス) ➝ `A[0]`(ミス) ➝ `B[1]`(ヒット) ➝ `A[1]`(ミス)で良いと思うのですが、`B[0][1]`の参照の際にヒットにはならないのでしょうか?