High Performance Computing (WS 2008/09)

This page is available in German only.

Aktuelle Hinweise

Diese Seite befindet sich noch im Aufbau.

Allgemeine Informationen

Dozent:

Alexandros Stamatakis WWW

Umfang und Hörerkreis:

2 SWS Vorlesung (voraussichtlich 3 ECTS-Punkte, vorbehaltlich Einstufung durch den Prüfungsausschuss)
Vorlesung für Studierende der Bioinformatik
Vorlesung für Studierende der Informatik
Vorlesung für Studierende der Medieninformatik

Zeit und Ort:

10-12

Amalienstr. 17, Raum A105

Voraussetzungen

Beherrschung des Stoffs des Bioinformatik/Informatik/Medieninformatik Grundstudiums.

Skript

Es wird vorlesungsbegleitend ein Folienskript erstellt.

Datum	Skript
15.10.08	Lecture 0
22.10.08	Lecture 1 Two nice papers about floating point arithmetics : "What every computer scientist should know about floating-point arithemtics" "The pitfalls of verifying floating point arithmetics"
28.10.08	Lecture 2
05.11.08	Lecture 3
12.11.08	Lecture 4
19.11.08	Lecture 5 Lecture 5 PDF(autopin slides)
26.11.08	Lecture 6 Twelve ways to fool the masses when giving performance results on parallel computers (by David H. Bailey) may also be considered as a HowTo by some
03.12.08	Lecture 7
10.12.08	Lecture 8
16.12.08	Lecture 9
07.01.09	Lecture 10 Interview with an OpenMPI (Open Message Passing Interface) developer, not very technical, but interesting (many thanks to Sebastian Pölsterl for the link)
14.01.09	Lecture 11
21.01.09	Lecture 12 Generic MPI master-worker code
28.01.09	Lecture 13

Inhalt der Vorlesung

Die Vorlesung behandelt folgende Themen:

Überblick über gängige Rechnerarchitekturen (shared-memory processors, multi-core processors, IBM Cell/Playstation III, IBM BlueGene)
Profiling und Optimierung sequentieller C-Programme
Shared-memory Parallelisierung mit Pthreads und OpenMP
Distributed-memory Parallelisierung mit MPI (Message Passing Interface)
Beispiele aus der Praxis (Bioinformatik, Numerik)

Das Ziel der Vorlesung ist es ein grundsätzliches Verständnis für parallele Rechnerarchitekturen, insbesondere die neuen MultiCore und AcceleratorSysteme, sowie für die entsprechenden Programmiertechniken zu vermitteln. Als Grundlage für die Optimierung paralleler Programme dient das Profiling und die Optimierung sequentieller C Programme für allgemeine numerische Probleme, unter Berücksichtigung der jeweiligen CacheHierarchien und Rechnerarchitekturen. Die relativ maschinenahe Programmiersprache C wird dabei gezielt eingesetzt, um das Verständnis für die zugrundeliegenden Architekturen zu verbessern. Einige gängige Parallelrechnerarchitekturen sollen genauer vorgestellt werden und gegenwärtige Trends im Bereich der Hochleistungsarchitekturen anhand der top500 Liste (www.top500.org) erörtert werden. Der zweite Teil der Vorlesung wird sich intensiv mit den Programmiertechniken und Interfaces zur Programmierung von Parallelrechnern mit gemeinsamem sowie verteiltem Speicher beschäftigen. Im letzten Teil der Vorlesung werden Beispielanwendungen aus der Praxis wie z.B. die BLAS Bibliothek für Anwendungen der linearen Algebra und eigene Arbeiten im Bereich des Hochleistungsrechnens für die Bioinformatik vorgestellt.

Scheinerwerb

Nur für Masterstudenten: ECTS-Punkte erhält, wer mindestens 50% der Punkte zu den Programmieraufgaben erreicht und erfolgreich an der 20-minütigen Semestralprüfung teilnimmt.
Die Semestralprüfung findet als mündliche Prüfung statt. Die Programmieraufgaben werden alle zwei Wochen gestellt.

Wer ECTS Punkte erwerben will, muss sich zur Vorlesung bis zum 24. Oktober per email anmelden.

Für Diplomstudenten: Diplomstudenten können am Ende des Semesters probeweise zur Vorbereitung auf die Diplomprüfung an der mündlichen Prüfung teilnehmen.

Programmieraufgaben

Programmieraufgabe 0

Source code
Optimierung eines einfachen C-Programmes zur Matrixmultiplikation (Loop unrolling und Cache-Blocking) and here is one possible beer-winning solution

Programming task 1: Matrix Multiplication (continued), due: 12.11.2008

Integrate ATLAS-BLAS or any other BLAS implementation of your choice into the program mmult
Measure the speedup attained in comparison to the naïve implementation
Measure the speedup attained compared to your hand-optimized version
I will not give any help with linking and compiling problems
This is one of the typical problems one has to solve with this type of libraries
To compile you will have to use something like: -I/root/ATLAS-LIB/Linux_P4SSE2/include/
To link you will have to use something like: -L/root/ATLAS-LIB/Linux_P4SSE2/lib/ -lcblas -latlas
You might also have to set the LD_LIBRARY_PATH variable

Programming task 2: Matrix Multiplication (yet another time), due: 26.11.2008

Parallelize the optimized sequential matrix-multiplication with Pthreads (you could see that coming)
The code shall run correctly with an arbitrary number of Threads
Build in a command line switch called -T such that the user can specify the number of threads to use, i.e., mmult -T 4 should run the program with 4 threads....
I will not tell you what the target architecture is You are allowed to build in an adaptation function (time for this will not be counted) that dynamically determines the optimal block size!
Apart pthreads library no other external libraries allowed!
You may of course further optimize the sequential code first
This is once again a beer homework :-) group that produces fastest code gets a bottle of Augustiner each

Programming task 3: Exploiting Wave-Front Parallelism in Dynamic Programming Algorithms with Pthreads, due: 10.12.2008

Source-code is available here and should hopefully be self-explanatory
Parallelize the very constructed version of the Smith-Waterman algorithm by exploiting wave-front parallelism with Pthreads
You are not allowed to change the scoring function and need to invoke it every time for each cell
Think about efficient ways to synchronize the Pthreads, a simple fork-join paradigm will most probabaly yield slowdowns instead of speedups
The code shall run corectly with an arbitrary number of threads!
Build in a command line switch called -T such that the user can specify the number of threads to use, i.e., smithWaterman -T 4 should run the program with 4 threads....
I will execute the program on an 8-way dual-core Sun x4600 system with four threads (but also test correctness with other thread numbers!)
Apart the pthreads library no other external libraries are allowed!
You may of course further optimize the sequential code first (except for the scoring function!)
This is once again a BEER homework :-) group that produces fastest code gets a bottle of Augustiner each
One possible solution for this task is provided here

Programming task 4: Profiling & Parallelizing RAxML with OpenMP, due: 31.12.2008

Phylogenetic inference program parallelization with OpenMP Download code here
Compile with "make -f Makefile.gcc"
Execute as follows: "./raxmlHPC -m GTRGAMMA -s dna.phy.dat -p 12345 -n T1"
Input dataset is included in archive
Profile the code using gprof
Find the 3-4 most compute-intensive functions
Parallelize them with OpenMP
You don't need to understand what the program is doing, just understand the loops!
I will only judge correctness, i.e., no beers this time
One possible solution for this task is provided here