Implement Cache-Oblivious Matrix Multiplication

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.