## Fall 2014: Theory Seminar

Donald Bren Hall, Room 1425, 1:00pm

November 21, 2014:

#
Cache-Adaptive Algorithms

##
Jenny Lam

We introduce the cache-adaptive model, which generalizes the
external-memory model to apply to environments in which the amount of
memory available to an algorithm can fluctuate. The cache-adaptive model
applies to operating systems, databases, and other systems where the
allocation of memory to processes changes over time. We prove that if an
optimal cache-oblivious algorithm has a particular recursive structure,
then it is also an optimal cache-adaptive algorithm. Cache-oblivious
algorithms having this form include Floyd–Warshall all pairs
shortest paths, naive recursive matrix multiplication, matrix transpose,
and Gaussian elimination. While the cache-oblivious sorting algorithm
Lazy Funnel Sort does not have this recursive structure, we prove that
it is nonetheless optimally cache-adaptive. We also establish that if a
cache-oblivious algorithm is optimal on “square”
(well-behaved) memory profiles then, given resource augmentation it is
optimal on all memory profiles.

We give paging algorithms for the case where the cache size changes
dynamically. We prove that LRU with 4-memory and 4-speed augmentation is
competitive with optimal. Moreover, Belady's algorithm remains optimal
even when the cache size changes. Cache-obliviousness is distinct from
cache-adaptivity. We exhibit a cache-oblivious algorithm that is not
cache- adaptive and a cache-adaptive algorithm for a problem having no
optimal cache-oblivious solution.

(Based
on a
paper from SODA 2014 by Michael A. Bender, Roozbeh Ebrahimi, Jeremy
T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley.)