Implement Cache-Oblivious Matrix Multiplication

Topic Overview

Performance Without Tuning

Cache-oblivious algorithms achieve good memory locality without knowing L1, L2, or L3 sizes. They recurse until subproblems fit in some unknown cache, then run a base-case kernel. Harald Prokop's thesis formalized the model; FFTW and BLIS use related blocking ideas.

cCopy
Loading…

Matrix Multiply Intuition

Naive triple loops miss cache constantly on large N. Blocked multiply fixes locality but needs a tuned block size. Cache-oblivious recursion picks up most of the benefit automatically.

For example, a 1024x1024 multiply recursively halves until 64x64 subblocks fit in L1 on most machines, without the code ever reading sysctl cache sizes.

For this exercise, you will implement recursive matrix multiply and benchmark against naive code. This task asks you to complete the recursive quadrant logic instead of falling back to naive multiply at the top level.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• 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

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Your Task

Implement cache-oblivious matrix multiplication, which recursively splits the problem in half until the blocks are tiny. It never needs to know the cache size, yet at every level of recursion some block size fits in cache. Instead of timing it, run both algorithms against a simulated cache and count misses. The recursive version wins by a growing margin as N increases.

Input

One experiment per line: N CACHE LINE BASE. The matrices are N×N. CACHE and LINE are in bytes. BASE is the recursion cut-off. N ≤ 48, and the cache has at most 256 lines.

Setup

• A, B, C are N×N arrays of 8-byte integers, row-major, stored back to back from address 0: A at 0, B at 8N², C at 16N². The address of X[r][c] is base(X) + 8·(r·N + c).
• A[i][j] = i + j, B[i][j] = i − j, C = 0.
• The cache is fully associative LRU with CACHE / LINE lines and starts empty for each algorithm.
• Every multiply-add step C[i][j] += A[i][k] · B[k][j] makes three accesses, in the order A[i][k], B[k][j], C[i][j].

Algorithms

• naive: for i, for j, for k.
• recursive rec(i0, j0, k0, m, n, p) multiplies the m×p block of A at (i0, k0) by the p×n block of B at (k0, j0) into C at (i0, j0):
  • if m, n and p are all ≤ BASE: naive i, j, k loops over the block;
  • else halve the largest of m, n, p (ties: m before n before p), first half ⌊x/2⌋ then the rest. Recurse on the first half, then the second.

Output

cCopy
Loading…

Rates use one decimal and the ratio two. Print a blank line between experiments.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A cache model with one touch(address) function; both algorithms call it through the same multiply-add helper.
2. The recursion splits exactly as specified; don't tune it to the cache size (that would make it cache-aware).

Hidden tests cover a matrix that overflows the cache by a wide margin, N not a power of two, a base case of 1, and a cache large enough that both algorithms only take compulsory misses.