Repo: ovfor4/CSAPP/cachelab-handout
Part A
SOON
Part B
for array A[i][j]
- when
jis increasing, I consider this as moving in horizontal direction - when
iis increasing, moving in vertical direction
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 (simple 32x32 and 64x64)
At first, it’s easy to think of the simple blocking method
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++)
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.
Insight
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 1024 (consider the minimum address difference so that collision would happen), so main diagonal is the issue (but we aren’t going to solve this now)
Improved version for 64x64
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.
For 61x67 (and other general cases)
This technique has been shown in the lecture, so it’s fairly easy
for (i = 0; i < N; i += GENERAL_BLOCK_SIZE)
for (j = 0; j < M; j += GENERAL_BLOCK_SIZE)
for (j2 = 0; j2 < GENERAL_BLOCK_SIZE && (j+j2) < M; j2++)
for (i2 = 0; i2 < GENERAL_BLOCK_SIZE && (i+i2) < N; i2++)
t0 = A[i+i2][j+j2];
B[j+j2][i+i2] = t0;
And you might wonder why it’s j2-i2 in the inner loop.
We should notice 61 and 67 are not multiples of GENERAL_BLOCK_SIZE and even prime numbers, meaning “misplace” when loading cache (not all of the loaded locations are used)
At a larger scale, we are accessing A in horizontal direction and B in vertical direction. Considering “misplace”, we know we should “preserve” the mis-loaded part of A while giving up that of B, which cannot be utilized (the time gap between 2 aceesses is toooo long).
And an obvious solution is to prevent eviction of A by minimizing the number of times the cache blocks are loaded (each time a cache block is loaded, it can only evict only one another block), so we should access B horizontally, so i2 is increaing in the innest loop.
You might run helper/main.py to verify this theory
Cache Lab loop-order control experiment
=====================================================================
matrix A=67x61, B=61x67, tile=8x8
cache: 32 sets, direct mapped, 32 B/line, 8 ints/line
A base = 0x0, B base = 0x40000
case A misses B misses total misses
----------------------------------------------------------
j2-i2 continuous 847 1081 1928
j2-i2 reset/tile 1223 1081 2304
i2-j2 continuous 877 1238 2115
i2-j2 reset/tile 1062 1238 2300
Cross-tile benefit = reset-per-tile misses - continuous misses
order A benefit B benefit total
------------------------------------------------
j2-i2 376 0 376
i2-j2 185 0 185
Derived comparison
---------------------------------------------------------------------
Per-tile-only gap (j2-i2 - i2-j2): +4 misses
Extra cross-tile benefit of j2-i2: A=+191, B=+0
Final continuous-cache advantage of j2-i2: 187 fewer misses
A and B are fully “symmetric” if cache is cleared each time when it finishes a block
However, we can notice that A benefits more from unreset cache than B (B benefits 0 LOL)
Thus clearly j2-i2 is better than i2-j2 given the outer is i-j
NB: In this case, block size of 16 is better than 8, and you may find out the reason (I used 8 initially, and I’m a bit sleepy now so not gonna change anything). But it’s fairly a good explanation of order of i2 and j2
Diagonal issue for 32x32
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.
So we just need to temporarily write the processed stuff to a corner in B, and then move to the correct position.
A similar technique (load all 8 elements to temp vars to reduce some cache miss) is used again here.
Format issue
If you use more than 12 variables, try re-use the same variable
Driver issue
The official driver is written in python2, which is definitely outdated and really hard to be installed in modern systems.
driver-NEW.py is the modern python3 version, which has the same function and even same output
End
➜ cachelab-handout git:(main) ✗ python3 driver-NEW.py
Part A: Testing cache simulator
Running ./test-csim
Your simulator Reference simulator
Points (s,E,b) Hits Misses Evicts Hits Misses Evicts
3 (1,1,1) 9 8 6 9 8 6 traces/yi2.trace
3 (4,2,4) 4 5 2 4 5 2 traces/yi.trace
3 (2,1,4) 2 3 1 2 3 1 traces/dave.trace
3 (2,1,3) 167 71 67 167 71 67 traces/trans.trace
3 (2,2,3) 201 37 29 201 37 29 traces/trans.trace
3 (2,4,3) 212 26 10 212 26 10 traces/trans.trace
3 (5,1,5) 231 7 0 231 7 0 traces/trans.trace
6 (5,1,5) 265189 21775 21743 265189 21775 21743 traces/long.trace
27
Part B: Testing transpose function
Running ./test-trans -M 32 -N 32
Running ./test-trans -M 64 -N 64
Running ./test-trans -M 61 -N 67
Cache Lab summary:
Points Max pts Misses
Csim correctness 27.0 27
Trans perf 32x32 8.0 8 291
Trans perf 64x64 8.0 8 1287
Trans perf 61x67 10.0 10 1932
Total points 53.0 53