Date: 14:40-15:20, Wednesday, March 25, 2009
   
Venue: FIT Building 1-315, Tsinghua University
   
Title: Cache-Oblivious Algorithms - A Unified Approach to Hierarchical Memory Algorithms
   
Speaker: Gerth Stølting Brodal
   
Biography:
Gerth Stølting Brodal is an Associate Professor at the Department of Computer Science, Aarhus University, Denmark. He received his PhD in computer science in 1997 from the Aarhus University for the thesis ``Worst Case Efficient Data Structures''. From 1997 to 1998 he was a Post. Doc. in the group of Kurt Mehlhorn at the Max-Planck-Institute for Theoretical Computer Science in Saarbrücken, Germany. From 1998-2005 he was affiliated with BRITCS (Center for Basic Research In Computer Science) located at the Department of Computer Science, Aarhus University. Since 2004 he is an Associate Professor (tenured) at the Department of Computer Science, Aarhus University. Since March 2007 he is affiliated with the Center for Massive Data AlgorithmITCS, Aarhus University, founded by the Danish National Research Foundataion. His main research interests are the design and analysis of algorithms and data structures. He has done work on fundamental data structures, including dictionaries and priority queues, persistent data structures, computational geometry, graph algorithms, I/O-efficient and cache-oblivious algorithms and data structures, string algorithms, and computational biology.
 
Abstract:
Modern computer systems are characterized by having a hierarchical memory organization. During the last decades several computational models have been suggested to integrate characteristITCS of hierarchical memory into the design of algorithms. Many of these models have only had limited success - in the sense that they have been applied only to a few algorithmic problems - but two models have received considerable attention. Aggarwal and Vitter in 1987 suggested the two-level I/O model, that focuses on the number of blocks of data transfered between two memory levels. This is motivated by the fact that in many computations the bottleneck is the block transfers between two adjacent memory levels, where the characteristITCS of the two memory levels are known to the algorithm. This model was generalized by Frigo, Leiserson, Prokop and Ramachandran in 1999, who introduced the simple but powerful ideal-cache model as a formal model of computation for developing algorithms in environments with multiple unknown memory levels. Frigo et al. coined the terminology of "cache-oblivious algorithms". In this talk we will introduce the basic ideas and techniques used when designing cache-oblivious algorithms, survey recent results within the area, and discuss current trends within the area.

 

 


[Close]