Implement Cache-Oblivious Matrix Transpose

Recursive Blocking Without Tuning Cache Size

Cache-oblivious algorithms use recursive divide-and-conquer so subproblems eventually fit in L1, L2, or L3 without hard-coded tile sizes. Matrix transpose is the textbook demo: naive a[j][i]=b[i][j] scans one matrix with huge stride.

Recursive Transpose Sketch

Split the matrix into quadrants. Transpose each quadrant recursively until the base case fits in cache. Combine with a simple in-register transpose at the leaf.

cCopy
Loading…

• Same idea underpins FFT and dense linear algebra libraries
• Tiling with fixed 32 or 64 also works but must be retuned per machine
• Measure L2 misses dropping versus naive transpose
• Works for non-square matrices with careful base cases

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a recursive cache-oblivious transpose and compare against naive code. This exercise requires reporting both runtime and cache-miss counters.