Title: Cache-Oblivious Data Structures
Speaker: John Iacono
Polytechnic University
Brooklyn, New York, USA 


Date: Friday, May 13, 2005
Time 11-12
Venue: Room 3464, HKUST


Abstract
For many data structures, it has been long observed
that the dominating component of the runtime is not the
number of CPU cycles used, but rather the time spent transferring
data from one level of the memory heiarchy to another.

In order to model this, the external-memory model (or I/O model or
Disk Access Model) was developed. The external-memory model defines a
memory hierarchy of two levels: one level is fast but has limited
size, M, and the other level is slow but has unlimited size. Data can
be transferred between the two levels in aligned blocks of size B, and
performance in this model is measured as the number of such memory
transfers. For example, the classic external-memory data structure is
the B-tree, which supports O(log_B N) dictionary operations. The
B-tree is explicitly parameterized by B, which must be known. While
this is a significant limitation, another problem is that B-trees are
designed to optimize the number of block transfers between only two
levels levels of the memory heiarchy, while modern systems have many
levels in their heiarchy.

In response to these problems, the cache-oblivious model was
developed.  The cache-oblivious model requires the additional property
that the data structure is not parameterized by B or M, though the
number of memory transfers (and analysis) still depend on these
parameters. One consequence of this property is that an optimal
cache-oblivious algorithm is simultaneously optimal between every pair
of levels in every possible memory hierarchy.

In this talk we will present on overview of the cache-oblivious model,
and the fundamental cache-oblivious data structures that have been
invented.