In this part of the Cache Lab, the mission is simple yet devious: optimize matrix transposition for three specific sizes: 32x32, 64x64, and 61x67. Our primary enemy? Cache misses.
A standard transposition swaps rows and columns directly:
1 | void trans(int M, int N, int A[N][M], int B[M][N]) |
While correct, this approach is a cache-miss nightmare because it ignores how data is actually stored in memory.
To optimize effectively, we first have to understand our hardware constraints. The lab specifies a directly mapped cache with the following parameters:
| Parameter | Value |
|---|---|
| Sets (S) | 32 |
| Block Size (B) | 32 bytes |
| Associativity (E) | 1 (Direct-mapped) |
| Integer Size | 4 bytes |
| Capacity per line | 8 integers |
We will use Matrix Tiling and Loop Unrolling to optimize the codes.
In this case, a row of the matrix needs 32/8 = 4 sets of cache to store. And cache conflicts occur every 32/4 = 8 rows. This makes 8x8 tiling the sweet spot.
By processing the matrix in 8×88 \times 8 blocks, we ensure that once a line of A is loaded, we use all 8 integers before it gets evicted. We also use loop unrolling with 8 local variables to minimize the overhead of accessing B.
1 | int i,j,k; |
Since 61 and 67 are not powers of two, the conflict misses don’t occur in a regular pattern like they do in the square matrices. This “irregularity” is actually a blessing. We can get away with simple tiling. A 16x16 block size typically yields enough performance to pass the miss-count threshold.
1 | int BLOCK_SIZE = 16; |
This is the hardest part. In a 64x64 matrix, a row needs 8 sets, but conflict misses occur every 32/8=432/8 = 4 rows. If we use 8x8 tiling, the bottom half of the block will evict the top half.
We can try a 4x4 matrix tiling first.
1 | int BLOCK_SIZE = 4; |
But this isn’t enough to pass the miss-count threshold.
We try a 8x8 matrix tiling. We solve this by partitioning the 8×88 \times 8 block into four 4×44 \times 4 sub-blocks and using the upper-right corner of B as a “buffer” to store data temporarily.
Block A=(ATLATRABLABR)→TransposeBlock B=(ATLTABLTATRTABRT)\text{Block } A = \begin{pmatrix} A_{TL} & A_{TR} \\ A_{BL} & A_{BR} \end{pmatrix} \quad \xrightarrow{\text{Transpose}} \quad \text{Block } B = \begin{pmatrix} A_{TL}^T & A_{BL}^T \\ A_{TR}^T & A_{BR}^T \end{pmatrix}
Here are the steps:
1 | int i, j, k; |
Note: The key trick here is traversing B by columns where possible (so B stays right in the cache) and utilizing local registers (temporary variables) to bridge the gap between conflicting cache lines.
Optimizing matrix transposition is less about the math and more about mechanical sympathy—understanding the underlying hardware to write code that plays nice with the CPU’s cache.
The jump from the naive version to these optimized versions isn’t just a marginal gain; it’s often a 10x reduction in cache misses. It serves as a stark reminder that in systems programming, how you access your data is just as important as the algorithm itself.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。