Algorithms for Memory Hierarchies
Typ: | Vorlesung (V) | ||
---|---|---|---|
Semester: | WS 12/13 | ||
Zeit: | 17.10.2012 15:45-17:15 50.34 Raum -120 24.10.2012 15:45-17:15 50.34 Raum -120 31.10.2012 15:45-17:15 50.34 Raum -120 07.11.2012 15:45-17:15 50.34 Raum -120 14.11.2012 15:45-17:15 50.34 Raum -120 21.11.2012 15:45-17:15 50.34 Raum -120 28.11.2012 15:45-17:15 50.34 Raum -120 05.12.2012 15:45-17:15 50.34 Raum -120 12.12.2012 15:45-17:15 50.34 Raum -120 19.12.2012 15:45-17:15 50.34 Raum -120 02.01.2013 15:45-17:15 50.34 Raum -120 09.01.2013 15:45-17:15 50.34 Raum -120 16.01.2013 15:45-17:15 50.34 Raum -120 23.01.2013 15:45-17:15 50.34 Raum -120 30.01.2013 15:45-17:15 50.34 Raum -120 06.02.2013 15:45-17:15 50.34 Raum -120 |
||
Dozent: | |||
SWS: | 2 | ||
LVNr.: | 2400017 | ||
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.
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.
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
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:
- Algorithms and Data Structures for External Memory. Book by J.S. Vitter.
- External Memory Geometric Data Structures, Lecture notes by L. Arge.
- I/O-efficient graph algorithms. Lecture notes by N. Zeh.
- 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