Hauptseminar: Algorithms for Memory Hierarchies

This seminar will be a joint seminar with the CSE Seminar Algorithms for Memory Hierarchies

Winter 09
Riko Jacob, Michael Bader
Time and Place
block seminar, schedule t.b.a.
Informatics (Master),
Computational Science and Engineering (3rd semester)
Semesterwochenstunden / ECTS Credits
2 SWS (2S) / 4 Credits


Deadline for registration is Oct 23 (end of the opening week of the semester). If you want to start preparing your talk in the summer holidays, already, please contact Michael Bader or Riko Jacob.

On modern computers, from desktop machines to supercomputers, memory can no longer be considered as a uniform list of addresses, even though the most common programming languages give exactly this impression. Multiple layers of cache memory, caches that are shared between CPU cores, non-uniform connection of CPU cores to main memory, and other features of modern hardware therefore make it complicated to achieve satisfying performance for many problem that have a reasonably complex access pattern to memory.

This seminar will tackle the resulting algorithmic problems and some proposed algorithmic solutions both from a theoretical and a practical point of view. Possible topics will be:

  • The I/O- and cache-oblivious model and basic algorithms
  • Lower bounds: sorting, permuting, and dense matrix multiplication
  • Complexity of sparse matrix multiplication in the I/O model
  • List ranking in the I/O model
  • Parallel external memory model: sorting and basic graph algorithms
  • Gaussian Elimination Paradigm in the cache-oblivious model
  • Cache-oblivious algorithms for dense linear algebra
  • Matrix multiplication using Peano orders
  • Cache-blocking for sparse-matrix operations
  • Space-filling curves and cache-oblivious traversals of adaptive meshes
  • Cache-oblivious algorithms for stencil-based discretisations of PDEs
  • ...

Seminar Outline

Each student will give one presentation (approx. 45 minutes) in the seminar. In addition to her or his talk, each student will have to prepare a short paper (8-10 pages), which will be reviewed by two other seminar participants. The paper and the two reviews will, in addition to the talk, be considered to determine the final grade.


The seminar talks will be given in presumably 3 or 4 block sessions during December and January.