2

配列のミス率を計算する方法を理解しようとしています。答えはありますが、その答えにたどり着いた経緯がわかりません。次のコードがあります。

int C[N1][N2];
int A[N1][N3];
int B[N3][N2];

initialize_arrays(A, B, C, N1, N2, N3);

for(i=0; i<N1; ++i)
   for(j=0; j<N2; ++j)
      for(k=0; k<N3, ++k)
         C[i][j] += A[i][k] * B[k][j];

次の情報もあります: N1=N2=N3=2048(これはどういう意味ですか??)。プロセッサには、ライン サイズが 64B の 32kB の L1 データ キャッシュがあります (L2 キャッシュなし)。（ラインサイズとは？）

配列 C のミス率は です(N^2/16)/N^3。私は式が であることを知ってい(total misses)/(total accesses)ます。総アクセス数はあるN^3のですが、総ミス数はどうやって出たのですか？

(N^3)/(N^3)配列 B:と A:のミス率も知っています(N^2/16)/N^3。誰かがここでも合計ミスをどうやって得たのか説明してもらえますか?

4

1 に答える 1

2

キャッシュは常に行の粒度でアクセス/管理されます。ここでは、行サイズは 64B です。つまり、1 つのキャッシュ ラインには 16 の要素が含まれることになります (64B / 4B = 16)。ここで次に重要なことは、17 番目の要素ごとに新しい行があり、行がキャッシュに入れられると、15 ヒットする可能性があるということです。

それを理解したところで、アクセスパターンを見てみましょう。A[0][0]、B[0][0]、C[0][0]、A[0][1]、B[1][0]、C[0][0]、A[ 0][2]、B[2][0]、C[0][0]、...... A[0][16]、B[16][0]、C[0][0 ]、A[0][17]、B[17][0]、C[0][0]、……など

ここで、行には 16 の要素があり、メモリ A[0][0] - A[0][15] 内の要素の行優先の配置を想定しても安全なので、最初のキャッシュ行の 1 つに属します (呼び出しましょうこの AL1) と同様に、B[0][0] ～ B[0][15] をライン BL1 に属するとします。この情報から、キャッシュ ラインに関するアクセス パターンを記述できます。AL1、BL1、CL1、AL1、BL129、CL1、AL1、BL257、CL1、..... AL1、BL2049、CL1、AL2、BL2176、CL1、....など。

現在、キャッシュ サイズは 32kB で、これはキャッシュが 512 行を保持できることを意味します。これは L1 であるため、双方向連想キャッシュであると仮定します。したがって、256 セットあります。これは、配列の 256 行ごとに、257 行目が 1 行目と同じセットにマップされることを意味します。

セット 1 にマッピングされている行にアクセスしたときのキャッシュの内容は次のようになります。

1 回目の反復 - 内部

Access to - AL1 - Miss
 AL1 
Access to - BL1 - Miss
 AL1
 BL1
Access to - CL1 - Miss
 CL1
 BL1

2 回目の反復 - 内部

Access to - AL1 - Miss
 CL1
 AL1
Access to - CL1 - Hit
 CL1
 AL1

3 回目の繰り返し - 内部

Access to - AL1 - Hit
 CL1
 AL1
Access to - BL257 - Miss
 BL257
 AL1
Access to - CL1 - Miss
 BL257
 CL1

4 回目の繰り返し - 内部

Access to - AL1 - Miss
 AL1
 CL1
Access to - CL1 - Hit
 AL1
 CL1

5 回目の繰り返し - 内部

Access to - AL1 - Hit
 CL1
 AL1
Access to - BL513 - Miss
 BL513
 AL1
Access to - CL1 - Miss
 BL513
 CL1

. . .

16 回目の反復 - 内部

Access to - AL1 - Miss
 AL1
 CL1
Access to - CL1 - Hit
 AL1
 CL1

17 回目の反復 - 内部

Access to - BL2049 - Miss
 BL2049
 CL1
Access to - CL1 - Hit
 BL2049
 CL1

18 回目の反復 - 内部

Access to - CL1 - Hit
 BL2049
 CL1

中間ループの最初の反復用。セット 1 には、

A -> M, M, H, M, H, M, H, M, H, M, H, M, H , M, H, M, ~ , ~ , ~ , ~ , ....... 
=> after 2048 iterations - 7 hits 9 misses, 16 accesses

B -> M, ~ , M, ~ ,  M, ~ , ........
=> after 2048 iterations - 0 Hits, 1024 misses, 1024 accesses

C -> M, H, M, H, M, H, M, H, M, H, M, H, M, H, M, H, H , H, H , H, ......
=> after 2048 iterations - 2040 hits, 8 misses, 2048 accesses

中間ループの 2 回目から 16 回目の反復では、

Exact hit / miss / access pattern as before.

中間ループの 17 回目から 2048 回目の反復では、

A -> same as before
B -> No accesses
C -> No accesses

要約すると、外側のループの 1 回の反復では、セット 1 に対して、

A -> N*9 misses , N * 16 accesses
B -> N/2 * 16 Misses , N/2 * 16 accesses
C -> 8 * 16 Misses , N * 16 accesses

外側のループでは、配列 C と A の 1 回目の反復 (上記で要約) と同じヒット / ミス / アクセス パターンがすべての代替反復で発生することがわかります。外側のループのすべての反復で同じヒット / ミス / アクセス パターンが発生しますアクセス パターン a 配列 B の 1 回目の反復。

というわけで（ついに！）

セット 1 では、プログラムの最後に、

A -> N^2 * 9 / 2 misses, N^2 * 8 accesses
B -> N^2 * 8 misses, N^2 * 8 accesses
C -> N * 64 misses, N^2 * 8 accesses

アクセス パターンは、すべてのセットで類似しています。したがって、プログラムの終わりまでに、すべてのセットで

A -> N^2 * 1152 misses, N^3 accesses
B -> N^3 misses, N^3 accesses
C -> N^2 * 8 misses, N^3 accesses

これは質問に示されているものとは異なることを知っています。方法がわかりませんでした。他の回答をいただけると幸いです。

于 2013-05-04T07:45:35.020 に答える