Skip to main content

Loading the code workspace…

LC

Implement Cache-Oblivious Matrix Transpose

hard4/8

Structure of Arrays vs Array of Structures Benchmark Implement Cache-Friendly BFS Using Level-by-Level Traversal

Language

Compiler

2.0s Limit 256MB

Submit and pass all tests to enable saving to GitHub.

Implementation

Implement cache-oblivious matrix transpose using recursive divide-and-conquer.

Requirements:

Implement naive transpose (strided access)
Implement blocked transpose with fixed block size
Implement cache-oblivious transpose (recursive)
Benchmark all three approaches (1000x1000 matrix)
Show performance comparison (10-20x speedup)
Use recursive subdivision until base case
Explain why cache-oblivious adapts to any cache size
Print timing results and analysis
Demonstrate understanding of cache lines
Compare naive vs blocked vs cache-oblivious

Why This Matters

Cache-oblivious algorithms come from Harald Prokop's MIT thesis and Charles Leiserson's group, and the recursive blocking you implement here is the same idea behind FFTW's self-tuning transforms and cache-oblivious B-trees used in some database indexes. The appeal is portability: a naive transpose can be 20x slower than blocked code on one machine and a different multiple on another, while the recursive version adapts to L1/L2/L3 automatically without hand-tuned constants.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0

← Structure of Arrays vs Array of Structures BenchmarkImplement Cache-Friendly BFS Using Level-by-Level Traversal →