	Universität Karlsruhe (TH) – Fakultät für Informatik
	ILKD – Algorithmentheorie, Algorithm-Engineering

Algorithm-Engineering

Cache-Effiziente und Cache-Oblivious Algorithmen

Praktikum

Einleitungen

C++: Von Java nach C++ [pdf]
Caches, TLBs: Rahman [link]
Cache-efficient and External memory algorithms: Sanders [link]
Cache-oblivious algorithms: Kumar [link], Demaine [link]
PAPI performance counters: PAPI home page [link]
Our PAPI intallation guide (if you want to install it at home): [link]

Folien

C++ Einführung (04.05.2004) [pdf]
Project 1,2,3 presentations (27.04.2005) [pdf]
Einführung in wissenschaftliches Schreiben/Latex (29.06.2005) [pdf]

Themen

Matrix-Transposition (Warm-up Übung für alle Teilnehmer)
Quellen: Frigo et al. [pdf], Kumar [link], Chatterjee et al. [pdf]
Aufgabenblatt: [pdf]

Sorting
Project 1: Implement and tune cache-oblivious distribution sorting
Quellen: basic version - Frigo et al. [pdf] , optimized randomized version - Kumar [link]

The goal of this project is to implement the cache-oblivious distribution sorting algorithm. In case of success your implementation should outperform the quicksort variant std::sort from the STL library. As a starting point you should take the implementation of Kumar [link].

       Ansprechpartner: Roman Dementiev, Room 222

     Project 2: Tuning Super Scalar Sample Sort
        Quellen: Sanders et al [postscript], source code on request

The goal of this project is to tune the existing implementation of the Super Scalar Sample Sort (see Sanders et al [postscript]). You will concentrate on several optimizations that were not investigated in the paper. Your implementation should have a speedup over std::sort from the STL library. You might test your code on different modern processors we have: Opteron, Intel Prescott Pentium 4, PowerPC G5.

       Ansprechpartner: Roman Dementiev, Room 222

Priority queues
    Project 3: Space efficient sequence queues with STL interface
       Quellen: Sanders [postscript], source code [link], STL priority queue doc page [link]

In this project you will reimplement the cache-efficient sequence heaps of Sanders [postscript] making them space efficient. Space efficiency can be achieved by implementing the sequence data structure as singly linked list of memory pages. The second goal of this project is to make your implementation compatible with std::priority_queue from STL. Finally you compare the performance of your tuned implementation with the performance of the binary heaps.

        Ansprechpartner: Roman Dementiev, Room 222

Search trees
    Project 4: Cache-oblivious search trees
        Quellen: basic version - Bender et al. (2002) [pdf] , enhancement using indirection - Bender et al. (2000) [pdf], Section 3.2

The first goal of this project is to implement the cache-oblivious search tree according to Bender et al. (2002) and compare its performance to std::map. The basic implementation should be enhanced using indirection as described in Bender et al. (2000). Further improvements are possible if time permits. The delete operation can be omitted due to time constraints.

          Ansprechpartner: Dominik Schultes, Room 222

     Project 5: Cache-aware (a,b)-trees using techniques adopted from Super Scalar Sample Sort
        Quellen: Sanders et al. [postscript], Mehlhorn et al. [pdf], Section 7.2

The goal of this project is to implement a cache-aware (a,b)-tree (see Mehlhorn et al.). When such a tree is traversed, we have to decide at each node which branch to take. This decision should be done using techniques adopted from Super Scalar Sample Sort (Sanders et al.). The performance should be compared to std::map. Furthermore, a comparison between Project 4 and 5 could be done.

Ansprechpartner: Dominik Schultes, Room 222

Messungen

We have prepared a user-friendly C++ timer class (timer.h and timer.cpp) that can read the most useful in our praktikum PAPI performance counters. Documentation for the timer class: [doxy]. An example that uses the timer class is here. The example measures the running time, cache and TLB misses of the std::sort from STL. The tar ball also contains a Makefile and a gnuplot script that draws a figure with the values of the counters.

Computers

For the projects and exercises we will provide our computer pool, where the PAPI library is installed. You will be able to make an ssh connection to our computers from the outside to conduct the experiments remotely.

Zeitplan

1. Woche 17.04 - 23.04	C++ Einführung	Mi 20.04.2005 9:45 Raum 211
2. Woche 24.04 - 30.04	C++ Einführung	Mi 27.04.2005 9:45 Raum 211
3. Woche 1.05 - 7.05	C++ Einführung	Mi 4.05.2005 9:45 Raum 211
4. Woche 8.05 - 14.05	Warm-up Übung: Matrix-Transposition	Deadline: 11.05.2005 13:00
5. Woche 15.05 - 21.05	Projektpresentation
7. Woche 22.05 - 28.05
8. Woche 29.05 - 4.06
9. Woche 5.06 - 11.06
10. Woche 12.06 - 18.06
11. Woche 19.06 - 25.06
12. Woche 26.06 - 2.07
13. Woche 3.07 - 9.07	Abschlusspräsentation