FIRST Research School

The first FIRST Lunch and Network Meeting of 2010 will be held at
Roskilde University on Thursday, February 11, from 11:00 to
13:00.

The programme of the meeting is as follows:

11:00 - 12:00: Talk by Rolf Fagerberg (IMADA,SDU) on "Dealing
              with the Memory Hierarchy the Cache-Oblivious
              Way" (see abstract below)

12:00 - 13:00: Lunch and general announcements

Please sign up no later than noon, Tuesday, February 9.

Looking forward to see you all.

-- Morten

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

Speaker:

   Rolf Fagerberg (Department of Mathematics and Computer
   Science, University of Southern Denmark)

Title:

   Dealing with the Memory Hierarchy the Cache-Oblivious Way

Abstract:

Computers contain a hierarchy of memory levels, with each level
acting as a cache for the next.  The access time increases with
each new level, making the cost of a memory access depend highly
on where in the hierarchy it is taking place. Consequently, the
memory access pattern of an algorithm can have a major impact on
its actual running time.

Analysis of algorithms in the standard RAM model is unable to
capture this, and more elaborate models have been defined. Most
widely used is the I/O model of Aggarwal and Vitter, which models
a memory hierarchy with two levels. The cache-oblivious model is
a generalization of the I/O model, which in a very elegant way
generalizes it to cover multi-level memory hierarchies, thereby
facilitating the design of algorithms adapting to the entire
memory hierarchy.

In this talk, we will give an introduction to the cache-oblivious
model, survey the results obtained in the decade passed since its
introduction in 1999, and illustrate some details of techniques
and results, of both theoretical and empirical nature, with a
focus on searching and sorting.