CSE Seminar Algorithms for Memory Hierarchies - Winter 09

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

Preliminary Sessions

  • Thursday, October 29, 2009: 13:00 in room 02.05.037
  • Monday, July 20, 2009 (13:00) in room 02.07.023.
  • The presentations will be organised as block sessions on March 8 and 9 (see schedule below)


  • deadline for paper: Fri, Dec 18, 2009.
  • deadline for review: Fri, Jan 15, 2010.
  • deadline for final paper: Fri, Feb 5, 2010


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.

Seminar Topics

This seminar will be a joint seminar with the Seminar "Algorithms for Memory Hierarchies" (Master Informatics)!

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.

Seminar Schedule

Day/Time Participants Topic Advisor
Mon, Mar 8, 9:30 Jörg Landthaler Complexity of sparse matrix multiplication in the I/O model Riko Jacob
Mon, Mar 8, 10:20 Isaias Compres Urena Cache-oblivious algorithms for dense linear algebra Michael Bader
Mon, Mar 8, 11:10 Alexei Perro Basic graphs and List ranking in the I/O model Riko Jacob
Tue, Mar 9, 9:30 Alexander Angeloski Cache-oblivious algorithms for stencil-based discretisations of PDEs Michael Bader
Tue, Mar 9, 10:20 Aleksandar Mihajlovic Space-filling curves and cache-oblivious traversals of adaptive meshes Michael Bader
Tue, Mar 9, 11:10 Haseeb Zia Parallel external memory model: sorting and basic graph algorithms Riko Jacob

Seminar Outline

Each student will give one presentation (max. 40 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 two block sessions on March 8 and 9 (9:30-12:30).