Implement Cache-Oblivious Matrix Transpose

Topic Overview

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.

Your Task

Transposing a matrix reads one array row by row and writes the other column by column, so one side always walks against the cache. Blocking fixes this with a tile size tuned to the cache. A cache-oblivious transpose recursively halves the larger dimension until the pieces are small, which works for every cache size without knowing it. Implement all three, check that each produces the correct transpose, and count the misses of each in a simulated cache.

Input

cCopy
Loading…

Rules

• A is at address 0, and B starts at the first line boundary after A (ceil(N*N*ELEM / LINE) * LINE). Every copy step reads A[i][j] (address (i*N + j) * ELEM) and then writes B[j][i]. Each algorithm starts with an empty cache.
• naive: for i, for j.
• blocked B: tiles of B x B, visited tile row by tile row. Inside a tile, for i, for j. Edge tiles are clipped.
• recursive BASE: rec(r0, r1, c0, c1). If both extents are <= BASE, copy naively. Otherwise split the rows in half if rows >= cols, else split the columns, and recurse on the first half, then the second.
• After each run, check that B[j][i] == A[i][j] everywhere (fill A with 0, 1, 2, …).
• Errors: cache: invalid geometry (the line must be a power of two, the number of sets a power of two), matrix: invalid, blocked: block size must be positive, and recursive: base size must be positive.

Output

cCopy
Loading…

A result that is not a transpose prints WRONG instead of transpose correct.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Implement each algorithm once, as real loops over real arrays. The simulator only watches the addresses those loops generate.
2. Keep read misses (A) and write misses (B) separate, so you can see which side each algorithm fixes.

Hidden tests cover a small 4-way cache where power-of-two rows make blocking useless while a small recursion base still helps, a matrix size that is not a power of two (edge tiles), a block larger than the matrix, a recursion base of 1, and invalid settings.