コンピュータシステムの深い理解（4）-キャッシュラボ
Depth Understanding Computer Systems Cache Lab
行列転置関数を最適化して、キャッシュミスをできるだけ少なくします。キャッシュサイズは次のとおりです。32グループ、直接マップ、行あたり32バイトのデータ。
1.ミッション
行列転置を実装する関数を記述します。また、関数呼び出し中にキャッシュミスをできるだけ少なくします。次の関数で最終的なコードを記述します。
char transpose_submit_desc[] = 'Transpose submission' void transpose_submit(int M, int N, int A[N][M], int B[M][N])； 32×32 ：必要なミスの数は300未満です。
行列分割のアイデアを適用します。
競合ミスは、実際には同じブロック内の2つの要素にアクセスする場合です。これは、他のブロックが途中でアクセスされ、ロードされたブロックが削除され、2番目のアクセスが失敗するためです。このため、同じブロック内の複数の要素に一度にアクセスでき、アクセス後にこのブロックにアクセスする必要がなくなり、競合ミスの数を大幅に減らすことができます。ここでは、最初の8つの要素が同じブロックにあり、これらの8つの要素を直接取り出すことができます。そうすれば、8つの要素が配置されているブロックにアクセスする必要がなくなります。
8x8チャンクを検討してください。
void trans_1(int M, int N, int A[N][M], int B[M][N]) { int ii, jj, i, val1, val2, val3, val4, val5, val6, val7, val0 for(jj = 0 jj < 32 jj += 8) for(ii = 0 ii < 32 ii += 8) { for(i = ii i < ii + 8 i++) { val0 = A[i][jj] val1 = A[i][jj + 1] val2 = A[i][jj + 2] val3 = A[i][jj + 3] val4 = A[i][jj + 4] val5 = A[i][jj + 5] val6 = A[i][jj + 6] val7 = A[i][jj + 7] B[jj][i] = val0 B[jj + 1][i] = val1 B[jj + 2][i] = val2 B[jj + 3][i] = val3 B[jj + 4][i] = val4 B[jj + 5][i] = val5 B[jj + 6][i] = val6 B[jj + 7][i] = val7 } } } 64x64
8x8ブロックし、bで最初に変換します
void trans_2(int M, int N, int A[N][M], int B[M][N]) { int i, j, ii, jj, val0, val1, val2, val3, val4, val5, val6, val7 for(ii = 0 ii < N ii += 8) { for(jj = 0 jj < M jj += 8) { //For each row in the 8*4 block for(i = 0 i < 4 i++) { val0 = A[ii + i][jj + 0] val1 = A[ii + i][jj + 1] val2 = A[ii + i][jj + 2] val3 = A[ii + i][jj + 3] val4 = A[ii + i][jj + 4] val5 = A[ii + i][jj + 5] val6 = A[ii + i][jj + 6] val7 = A[ii + i][jj + 7] B[jj + 0][ii + i] = val0 B[jj + 1][ii + i] = val1 B[jj + 2][ii + i] = val2 B[jj + 3][ii + i] = val3 B[jj + 0][ii + 4 + i] = val4 B[jj + 1][ii + 4 + i] = val5 B[jj + 2][ii + 4 + i] = val6 B[jj + 3][ii + 4 + i] = val7 } //First copy the first 4 rows for(i = 0 i < 4 i++)//Do the fantastic transformation! { //get this row of the right-upper 4*4 block val0 = B[jj + i][ii + 4] val1 = B[jj + i][ii + 5] val2 = B[jj + i][ii + 6] val3 = B[jj + i][ii + 7] //update this row to its correct value val4 = A[ii + 4][jj + i] val5 = A[ii + 5][jj + i] val6 = A[ii + 6][jj + i] val7 = A[ii + 7][jj + i] B[jj + i][ii + 4] = val4 B[jj + i][ii + 5] = val5 B[jj + i][ii + 6] = val6 B[jj + i][ii + 7] = val7 //update the left lower 4*4 block of B B[jj + 4 + i][ii + 0] = val0 B[jj + 4 + i][ii + 1] = val1 B[jj + 4 + i][ii + 2] = val2 B[jj + 4 + i][ii + 3] = val3 } //update the right lower 4*4 block for(i = 4 i < 8 i++) for(j = 4 j < 8 j++) B[jj + j][ii + i] = A[ii + i][jj + j] } } } 61x67
16x16ブロック
void trans_3(int M, int N, int A[N][M], int B[M][N]) { int ii, jj, i, j, val0, val1, val2, val3, val4, val5, val6, val7 for(ii = 0 ii + 16 < N ii += 16) for(jj = 0 jj + 16 < M jj += 16) { for(i = ii i < ii + 16 i++) { val0 = A[i][jj + 0] val1 = A[i][jj + 1] val2 = A[i][jj + 2] val3 = A[i][jj + 3] val4 = A[i][jj + 4] val5 = A[i][jj + 5] val6 = A[i][jj + 6] val7 = A[i][jj + 7] B[jj + 0][i] = val0 B[jj + 1][i] = val1 B[jj + 2][i] = val2 B[jj + 3][i] = val3 B[jj + 4][i] = val4 B[jj + 5][i] = val5 B[jj + 6][i] = val6 B[jj + 7][i] = val7 val0 = A[i][jj + 8] val1 = A[i][jj + 9] val2 = A[i][jj + 10] val3 = A[i][jj + 11] val4 = A[i][jj + 12] val5 = A[i][jj + 13] val6 = A[i][jj + 14] val7 = A[i][jj + 15] B[jj + 8][i] = val0 B[jj + 9][i] = val1 B[jj + 10][i] = val2 B[jj + 11][i] = val3 B[jj + 12][i] = val4 B[jj + 13][i] = val5 B[jj + 14][i] = val6 B[jj + 15][i] = val7 } } for(i = ii i < N i++) for(j = 0 j < M j++) B[j][i] = A[i][j] for(i = 0 i < ii i++) for(j = jj j < M j++) B[j][i] = A[i][j] }