From 291012b8c04c306b934754525766bae5a75082fe Mon Sep 17 00:00:00 2001 From: _ov4 Date: Mon, 9 Nov 2026 10:43:56 +0000 Subject: improve diagonal --- cachelab-handout/trans.c | 34 +++++++++++------------ cachelab-handout/trans.h | 72 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 88 insertions(+), 18 deletions(-) create mode 100644 cachelab-handout/trans.h diff --git a/cachelab-handout/trans.c b/cachelab-handout/trans.c index 2a46f92..833e44f 100644 --- a/cachelab-handout/trans.c +++ b/cachelab-handout/trans.c @@ -10,6 +10,8 @@ #include #include "cachelab.h" +#include "trans.h" + int is_transpose(int M, int N, int A[N][M], int B[M][N]); /* @@ -116,25 +118,21 @@ void transpose_submit(int M, int N, int A[N][M], int B[M][N]) // solve diagonal issue if (i == j) { - for (j2 = 0; j2 < CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE; j2 += CASE_64_64_BLOCK_SIZE) - { - for (t4 = 0; t4 < CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE; t4 += CASE_64_64_BLOCK_SIZE) - { - // move 4x4 - for (i2 = 0; i2 < CASE_64_64_BLOCK_SIZE; i2++) - { - t0 = A[i * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + j2 + i2][j * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + t4 + 0]; - t1 = A[i * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + j2 + i2][j * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + t4 + 1]; - t2 = A[i * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + j2 + i2][j * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + t4 + 2]; - t3 = A[i * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + j2 + i2][j * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + t4 + 3]; + // A00,01 -> B00,01 + CP_4_BY_8(i*8 + 0*4, j*8 + 0*4, i2); + B_SMALL_TRANSPOSE(i*8 + 0*4, j*8 + 0*4, i2); + B_SMALL_TRANSPOSE(i*8 + 0*4, j*8 + 1*4, i2); + + // A10,11 -> B10,11 + CP_4_BY_8(i*8 + 1*4, j*8 + 0*4, i2); + B_SMALL_TRANSPOSE(i*8 + 1*4, j*8 + 0*4, i2); + B_SMALL_TRANSPOSE(i*8 + 1*4, j*8 + 1*4, i2); + + // swap B01, B10 + // B10 is cached + B_SWAP_4_BY_4(i*8 + 1*4, j*8 + 0*4, + i*8 + 0*4, j*8 + 1*4, i2); - B[j * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + t4 + 0][i * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + j2 + i2] = t0; - B[j * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + t4 + 1][i * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + j2 + i2] = t1; - B[j * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + t4 + 2][i * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + j2 + i2] = t2; - B[j * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + t4 + 3][i * CASE_64_64_MAGIC_NUMBER * CASE_64_64_BLOCK_SIZE + j2 + i2] = t3; - } - } - } continue; } diff --git a/cachelab-handout/trans.h b/cachelab-handout/trans.h new file mode 100644 index 0000000..0d89704 --- /dev/null +++ b/cachelab-handout/trans.h @@ -0,0 +1,72 @@ +#define CP_4_BY_8(base_i, base_j, tmp) \ +do \ +{ \ +for (tmp = 0; tmp < 4; tmp++) \ +{ \ + t0 = A[base_i + tmp][base_j + 0]; \ + t1 = A[base_i + tmp][base_j + 1]; \ + t2 = A[base_i + tmp][base_j + 2]; \ + t3 = A[base_i + tmp][base_j + 3]; \ + t4 = A[base_i + tmp][base_j + 4]; \ + t5 = A[base_i + tmp][base_j + 5]; \ + t6 = A[base_i + tmp][base_j + 6]; \ + t7 = A[base_i + tmp][base_j + 7]; \ + B[base_i + tmp][base_j + 0] = t0; \ + B[base_i + tmp][base_j + 1] = t1; \ + B[base_i + tmp][base_j + 2] = t2; \ + B[base_i + tmp][base_j + 3] = t3; \ + B[base_i + tmp][base_j + 4] = t4; \ + B[base_i + tmp][base_j + 5] = t5; \ + B[base_i + tmp][base_j + 6] = t6; \ + B[base_i + tmp][base_j + 7] = t7; \ +} \ +} while (0) + + +#define SWAP(x, y, tmp) \ +do \ +{ \ +tmp = x; x = y; y = tmp; \ +} while (0) + + +#define B_SMALL_TRANSPOSE(base_i, base_j, tmp) \ +do \ +{ \ +SWAP(B[base_i + 0][base_j + 1], B[base_i + 1][base_j + 0], tmp); \ +SWAP(B[base_i + 0][base_j + 2], B[base_i + 2][base_j + 0], tmp); \ +SWAP(B[base_i + 0][base_j + 3], B[base_i + 3][base_j + 0], tmp); \ + \ +SWAP(B[base_i + 1][base_j + 2], B[base_i + 2][base_j + 1], tmp); \ +SWAP(B[base_i + 1][base_j + 3], B[base_i + 3][base_j + 1], tmp); \ + \ +SWAP(B[base_i + 2][base_j + 3], B[base_i + 3][base_j + 2], tmp); \ +} while (0) + + +#define B_SWAP_4_BY_4(i1, j1, i2, j2, tmp) \ +do \ +{ \ +for (tmp = 0; tmp < 4; tmp++) \ +{ \ + t0 = B[i1 + tmp][j1 + 0]; \ + t1 = B[i1 + tmp][j1 + 1]; \ + t2 = B[i1 + tmp][j1 + 2]; \ + t3 = B[i1 + tmp][j1 + 3]; \ + \ + t4 = B[i2 + tmp][j2 + 0]; \ + t5 = B[i2 + tmp][j2 + 1]; \ + t6 = B[i2 + tmp][j2 + 2]; \ + t7 = B[i2 + tmp][j2 + 3]; \ + \ + B[i2 + tmp][j2 + 0] = t0; \ + B[i2 + tmp][j2 + 1] = t1; \ + B[i2 + tmp][j2 + 2] = t2; \ + B[i2 + tmp][j2 + 3] = t3; \ + \ + B[i1 + tmp][j1 + 0] = t4; \ + B[i1 + tmp][j1 + 1] = t5; \ + B[i1 + tmp][j1 + 2] = t6; \ + B[i1 + tmp][j1 + 3] = t7; \ +} \ +} while (0) -- cgit v1.3.1-4-g156e