Algorithms for Memory Hierarchies

Vortragssprache:

Englisch

Course Description

Description

Traditional algorithms courses teach how to design algorithms in the Von Neumann model of computation: data is stored in a single level of memory (RAM) and the CPU can access any item in memory in unit time. This is a major simplification of modern processors which consists of several levels of memory where data might reside and with different access times for each one: from really fast but small caches, to RAM, to slow disks (for data too large to fit in RAM). Even modern caches consist of multiple levels. With the development of multicore systems in the past decade, the efficient use of memory hierarchy has become even more important when designing parallel algorithms for such systems.

In this course you will learn how to design sequential and parallel algorithms which take advantage of the fast local memories of each CPU on modern (multicore) architectures.

Scribing notes

Every student is expected to take notes during two lectures and typesetting them in Latex. You can work with the other person to produce a single document. The first draft of the typeset lecture notes will be due on Monday after the lecture. I will then work with you on editing the notes and producing the final version, which will then be posted here.

Latex is a powerful typesetting programing environment. If you are not familiar with Latex, this is an opportunity for you learn it. It will come in handy when writing your thesis or scientific papers.

There is a lot of Latex documentation online. Below are two links to help you get started.

  1. Wikibook on Latex
  2. Collection of Latex guides

Homework

Homework is due at the end of the course and is required to attend the final exam. You are allowed to collaborate on the homework with fellow students. However, you must write up your solution yourself and must list the names of all students that you collaborated with.

Homework

Final Exam

There will be an oral final exam at the end of the course. Each student will be allocated 30 min for the exam. The exam will be held on two different dates:

  • Wednesday, March 13, 2013 starting at 14:00
  • Thursday, April 4, 2013 starting at 14:00

Email Nodari with your preference of when you would like to take the exam and he will contact you with the exact time assigned to you.

 

Please register online well before your exam date, otherwise your results cannot be processed. Exchange students have to go to the Servicezentrum Studium und Lehre of the computer science department to get a 'Prüfungszulassung im Austauschstudium', which has to be signed by Professor Peter Sanders and Dr. Ioana Gheta at least a week before the exam. Without the twice-signed 'Prüfungszulassung', the exam cannot take place.

 

 

Schedule of Topics

 

Date
 Topic Scribe Schedule
 Scribed Lectures
Oct 17

Introduction: Memory hierarchy models

  • external memory (EM)
  • cache-oblivious (CO)
  • parallel external memory (PEM)
  • parallel cache-oblivious (PCO)

EM model: scanning, distribution, merging, sorting

 Ochsenreither unedited
Oct 24

EM model: distribution sorting

EM data structures: B-trees.

 Kirsten/Rehrmann link
Oct 31 EM data structures: persistent B-trees. Rehrmann/Gellert link
Nov 7 EM data structures: Buffer tree, priority queue Schrade link
Nov 14 CANCELED: Nodari is sick    
Nov 21 EM geometric algorithms: Distribution sweeping, line segment intersections Gellert link
Nov 28 EM graph algorithms: List ranking, algorithms on trees Ochsenrather/Hellmund  link
Dec 5 EM graph algorithms: Time forward processing, connected components, minimum spanning trees. Hellmund/Lange unedited
Dec 12

CO model: searching, sorting

 Gratia  unedited
Dec 19

CO data structures: funnels, priority queue

Applications: graph algorithms

 Kirsten/Herda link
Jan 9 PEM model: scanning, sorting Herda  unedited
Jan 16

PEM graph algorithms: list ranking, algorithms on trees, MST

 Klute/Hamann unedited
Jan 23

PEM geometric algorithms: parallel distribution sweeping

 Klute/Gratia unedited
Jan 30 PEM geometric algorithms: parallel distribution sweeping  Schrade unedited
Feb 6 PCO algorithms
  Hamann  unedited

 

 

Reading Material:

  1. Algorithms and Data Structures for External Memory. Book by J.S. Vitter.
  2. External Memory Geometric Data Structures, Lecture notes by L. Arge.
  3. I/O-efficient graph algorithms. Lecture notes by N. Zeh.
  4. Cache-oblivious data structures. Book chapter by L. Arge, G. S. Brodal, R. Fagerberg.

Final Exam Schedule

February 15:

  • 14:00 Mateus Grellert da Silva
  • 14:30 Romain Gratia

March 19:

  • 15:00 Robin Rehrmann

April 4:

  • 14:00 Mihai Herda
  • 14:30 Emanuel Schrade
  • 15:00 Michael Hamann
  • 15:30 Fabian Klute

Changelog:

10.02.2013: Final exam schedule is posted.

21.01.2013: Homework and exam times are posted

31.10.2012: Added information about scribing notes and Latex links

26.10.2012: Scribing schedule added