Cache-Oblivious Algorithms
o
Optimal memory access
n
Matrix multiply, Fast Fourier Transform
n
B-trees, Priority Queues
n
o
Concurrent?
o
o
Lock-free?
n
At least one thread can always make
progress.
o
