[Crib-list] Prof. Leiserson at 4th CRiB seminar Friday July 1

[Jeremy Kepner]

Dear Colleagues,
  we are privileged to have Prof. Charles Leiserson (MIT) speak on
Cache Oblivious Algorithms (see abstract below) at the next
Computational Research in Boston (CRiB) seminar, which will be held
12:30 July 1 at MIT in Room 4-370 (*not* Stata).
Pizza and drinks will be provided. For details see:

	http://www-math.mit.edu/crib/

The goal of CRiB is to provide a forum for interactions among scientists
and engineers throughout the Boston area working on a range of
computational problems.
    Please feel free to circulate this announcement among your
colleagues.  If you would like to be added or deleted from the e-mail
list, please visit the above website.
    Finally, if you would like to speak at the seminar or would like to
recommend someone to speak at the seminar, please send e-mail to
crib-admin at mit.edu.

Regards.

The organizers.
Alan Edelman (MIT - Math & CSAIL)
Lars Hernquist (Harvard - Astronomy)
Chris Hill (MIT - Earth and Atmospheric Science)
Jeremy Kepner (MIT - Lincoln Laboratory)
Steven Johnson (MIT - Math)

----------------------------------------

Charles Leiserson (MIT CSAIL)
Topic: 	Cache Oblivious Algorithms
Abstract 	

Computers with multiple levels of caching have traditionally required
techniques such as data blocking in order for algorithms to exploit the
cache hierarchy effectively. These "cache-aware" algorithms must be
properly tuned to achieve good performance using so-called ``voodoo''
parameters which depend on hardware properties, such as cache size and
cache-line length.

Surprisingly, however, for a variety of problems -- including matrix
multiplication, FFT, and sorting -- asymptotically optimal
"cache-oblivious" algorithms do exist that contain no voodoo parameters.
They perform an optimal amount of work and move data optimally among
multiple levels of cache. Since they need not be tuned, cache-oblivious
algorithms are more portable than traditional cache-aware algorithms.

We employ an "ideal-cache" model to analyze these algorithms. We prove
that an optimal cache-oblivious algorithm designed for two levels of
memory is also optimal across a multilevel cache hierarchy. We also show
that the assumption of optimal replacement made by the ideal-cache model
can be simulated efficiently by LRU replacement. We also provide some
empirical results on the effectiveness of cache-oblivious algorithms in
practice.

This talk represents joint work with Matteo Frigo, Harald Prokop, and
Sridhar Ramachandran.