Repo: ovfor4/CSAPP/cachelab-handout

Part B

NB:

Your code only needs to be correct for these three cases and you can optimize it specifically for these three cases. In particular, it is perfectly OK for your function to explicitly check for the input sizes and implement separate code optimized for each case.

I haven’t found any general solution to this yet, because 32x32 or 64x64 aren’t normal matrices, conversely, deliberately designed.

General idea (I don’t think it’s cheating):

  • 32x32 requires you to solve diagonal issue (only, perhaps), as described in the handout
  • 64x64 requires you to re-consider how to block for the minimum miss
  • 61x67 requires you to have general and size-unrelated blocking (this is quite normal and doesn’t need a lot of techniques if your brain is online during the lecture)

First version

At first, it’s easy to think of the simple blocking method

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp, i2, j2;
    const int blockSize = 8;

    // given N, M are multiples of blockSize
    // just to test
    for (i = 0; i < N/blockSize; i++)
    {
        for (j = 0; j < M/blockSize; j++)
        {
            // now i, j are indecies of groups
            for (i2 = 0; i2 < blockSize; i2++)
            {
                for (j2 = 0; j2 < blockSize; j2++)
                {
                    tmp = A[i*blockSize + i2][j*blockSize + j2];
                    B[j*blockSize + j2][i*blockSize + i2] = tmp;
                }
            }
        }
    }
}

When $N=M=32$

We can ignore cache impact of A first because it’s accessed in stride-1. However, B is accessed in column. In this case, cache can hold 32 cache blocks, which means 8 columns, enough for a group of B (8x8).

correctness=1 misses=344

It’s nearly full mark, so we can review this soon.

And when $N=M=64$, however, it can hold only 4 columns, so we reduce the size to 4.

correctness=1 misses=1892 at lease we have some marks.

Minor improvement

Insert the following code to check addresses of A and B

FILE *fp = fopen("debug.log", "w");
if (fp == NULL) {
    perror("lol");
    return;
}
fprintf(fp, "address of A and B: %p %p\n", A, B);
fclose(fp);

address of A and B: 0x4004100 0x4044100

The difference is 0x40000, which is multiple of 32, so main diagonal is the issue (but we aren’t going to solve this now)

And we notice that B is processing in column, so it can only utilize cache block of size 4 rather than 8 (the right part of cached B would be evicted). So the idea is that we should use some temp variables (but only 12, so it’s not working here), or find a temp place to store this. A method could be thought easily (only 12 variables are allowed, but we can use some corners as temp), but this indeed increases the miss number contributed by temp region. However, if we can process (move between places) row by row, by getting the datum to a temp variable (it’s in register as we have less than 12 variables) first, writing to that position, followed by writing the temp variable to the correct position, we can bypass use of temp array region (after we finish that region, we wont’t care if it’s evicted).

The process is

  • A00 -> B00
  • A01 -> temp B01
  • B01 -> temp var, A10 -> B01, temp var -> B10, simultaneously
  • A11 -> B11

And it’s working, 1287 miss, just below 1300, full mark 😊

Actually, when I was working on this lab, I somehow first finished 64x64 first.

Diagonal issue

And we should notice

Since your transpose function is being evaluated on a direct-mapped cache, conflict misses are a potential problem. Think about the potential for conflict misses in your code, especially along the diagonal. Try to think of access patterns that will decrease the number of these conflict misses.