# Teaching

The following lectures are offered regularly by the Research Group Parallel Computing. These lectures are optional in the Bachelor and Master programmes for "Software Engineering & Internet Computing", but can also be taken from other programmes. Consult the study plans of the faculty, or see us.

# By Semester

## 2019 Summer

- Introduction to Parallel Computing (184.710) - Bachelor
- Basics of Parallel Computing (191.114)- Master
- Advanced Multiprocessor Programming (184.726) - Master
- Projects, Bachelor's and Master's theses

## 2018/19 Winter

- High Performance Computing (184.725) - Master
- Parallel Algorithms: Scheduling (184.727) - Master
- Seminar in Parallel Computing for Master's (and PhD) students (184.745)
- Projects, Bachelor's and Master's theses

# By Course Name (ID)

# Introduction to Parallel Computing (184.710) - Bachelor

Credits: 6.0 ECTS, breakdown

- Lecture: 1.0 ETCS
- Exercises, self-study: 2.0 ECTS
- Programming projects: 3.0 ECTS

Credit will be given based on project hand-in and presentation
(during semester).

This course is given every year in the Winter Semester, ran in WS11,
WS12, WS13, WS14, WS15, WS16, WS17. The course will be offered next time in
SS19.

Introduction to parallel computing, basic concepts (performance, speed-up, Amdahl's law), history, and motivation. Basic algorithms, analysis. Shared-memory parallel computing, concrete languages/interfaces: OpenMP and pthreads, Cilk. Distributed memory parallel computing, concrete interface: MPI. New architectures (GPU and others), new languages, other paradigms. Practical programming exercises in OpenMP and/or pthreads, Cilk, and MPI.

## Literature

- Thomas Rauber, Gudula Rünger: Parallel Programming for Multicore
and Cluster Systems. Second Edition, Springer 2013.

Good overview, complements lecture well, also with topics/applications not in lecture. - Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar:
Introduction to Parallel Computing. Pearson Addison-Wesley
2003.

Good selection of material, good coverage. Beware, many detail mistakes/typos. - Michael McCool, Arch D. Robison, James Reinders: Structured Parallel Programming. Morgan Kaufmann, 2012.

# High Performance Computing (184.725) - Master

Credits: 4.5 ECTS

- Lecture: 2.0 ETCS
- Programming projects: 2.5 ECTS

Credit will be given based on lecture participation and programming project. Ran in SS13, SS14, SS15, SS16, SS17, SS18, and currently in WS18.

High-Performance Computing deals with computing systems (architectures, interfaces, algorithms) that provide the high performance percieved to be required by applications; and (more importantly) with (parallel computing) techniques and tools that are useful and necessary to get the best possible, requried and/or expected performance from given, parallel computing systems. This course will be given alternatingly and deal with interfaces, algorithms and architectures in HPC. Concrete topics may vary, but there will regularly be parts on advanced Message-Passing Interface (MPI) features, on memory systems and communication networks, on performance models for parallel systems, on benchmarks, packages, and applications.

Topics: HPC history and overview, architectures. HPC interfaces (MPI and others), advanced MPI, UPC, PGAS languages (UPC, X10/Habanero), parallel I/O and file systems, memory system, communication networks, algorithms for collective communication operations, HPC architecture, HPC packages, applications and algorithms, performance models.

Prerequisites: Introduction to parallel computing (lecture, or from elsewhere), Computer Systems/Architecture, Algorithms and Data structures.

## Literature

Books and papers. As a primer, the following is useful:

Georg Hager, Gerhard Wellein: Introduction to High Performance Computing for Scientists and Engineers. CRC Press, 2011.

# Advanced Multiprocessor Programming (184.726) - Master

Credits 4.5 ECTS, breakdown

- Lecture: 1.5 ETCS
- Exercises: 1.0 ECTS
- Project: 2.0 ECTS

Credit will be given based on exercise and project hand-in and presentation (during semester). Ran in SS12, SS13, SS14, SS15, SS16, SS17, SS18 and currently in SS19.

This lecture deals with modern, efficient techniques for (shared-memory) multi-processor programming, and will cover both theoretical (classical constructions, fundamental impossibility results and limitations) and practical aspects. The latter will survey algorithms for locking, and present a selection of lock- and wait-free data structures, and their use in supporting task parallel programming models as found in, e.g., Cilk and TBB, and in TU Wien's Pheet framework.

Topics: synchronization problems, mutual exclusion, synchronization primitives, consensus, memory models, atomic operations, locks, lock- and wait-free data structures (lists, stacks, queues, hashtables, search structures, ...), work-stealing, transactional. Practical implementation project in C++ using the work-stealing framework Pheet developed in the group. Alternatively: stand-alone project in Java or C#.

Prerequisites: Introduction to parallel computing (lecture, or from elsewhere), Computer Systems/Architecture, Algorithms and Data structures.

## Literature

Maurice Herlihy, Nir Shavit: The Art of Multiprocessor Programming. Morgan Kaufmann, Revised first edition, 2012.

# Parallel Algorithms (184.727) - Master

Credits 3.0 ECTS, breakdown

- Lecture: 1.0 ETCS
- Own study, discussion: 1.0 ECTS
- Exercises: 1.0 ECTS

Credit will be given based on exercises and participation. Ran in WS12, WS13, WS14, WS15, WS16, WS17 and currently in WS18

Prerequisites: Introduction to parallel computing (lecture), Algorithms and Data structures.

The specific topic of this course may vary by semester. Two types of lectures have been offered: T1 - PRAM, T2 - Scheduling

## Parallel Algorithms - PRAM (T1)

- Lecture on parallel algorithmics using the PRAM (Parallel Random-Access Machine) model, and models derived from/inspired by the PRAM. The course will be given alternatingly with the other master courses.
- Topics: The PRAM model, prefix-sums problems and algorithms, merging and sorting, algorithms on trees, graphs, numerical algorithms, fundamental lower bounds, limits to parallelization (P-complete problems under NC-reduction), BSP and other models, randomized parallel algorithms, PRAM simulations.
- Literature: Joseph Jaja: Introduction to Parallel Algorithms. Addison-Wesley, 1992.

## Parallel Algorithms - Scheduling (T2)

The course gives an introduction into the basics of scheduling theory, but will also highlight practical aspects when solving scheduling problems. The course introduces basic concepts and notation used in scheduling research. Then, selected topics are discussed in more detail, such as: shop scheduling, scheduling with parallel tasks, online scheduling, approximation algorithms in scheduling, divisible load scheduling, simulations and scheduling.

# Basics of Parallel Computing (191.114) - Master

Credits 3.0 ECTS, breakdown

- Lecture: 1.5 ETCS
- Own study, discussion: 0.5 ECTS
- Projet/Exercises: 1.0 ECTS

# Graph Partitioning and Graph Clustering in Theory and Practice (195.084)

Credits 3.0 ECTS, breakdown

- Exam: 80%
- Exercises: 20%

The lecture covers many different aspects of graph partitioning and graph clustering. After defining these problems and its objective functions properly, we show the hardness of some variants and present algorithms having a global view such as integer linear programs or spectral techniques. A large amount of the lecture is centered around the multilevel scheme which is explained in high detail for the graph partitioning problem. We then cover parallel, (semi-)external and evolutionary algorithms to tackle the problems. In addition, we talk about the currently most important algorithms to cluster graphs effectively. The main goal of the lecture is to give the students a first introduction the graph partitioning and clustering problems. This includes a set of ``easier'' subproblem problems and models that will be explained at the point of occurrence.

Prerequisites: Algorithms and Data Structures.

# Seminar in Parallel Computing for Master's (and PhD) students (184.745)

Credits: 3.0 ECTS

A follow-up (or independent) seminar to the lectures will regularly be offered under the headings "Distributed Systems" (184.194), "Programming Languages", or "Algorithms". A selection of papers will be suggested and discussed with the participants, from which individual themes centering around 2-5 papers can be defined. Credit is based on presentation, discussion, and written (10-20 page) summary.

Ran in WS12, SS13, WS13, SS14, WS14, SS15, WS15, SS16, WS16, SS17, WS17, SS18, and currently in WS18.

Prerequisites: Exposure to parallel computing.

# Projects, Bachelor's and Master's theses

Projects and theses (Bachelor's and Master's) can be offered at any time, in any of the above (or somehow related) areas. We can suggest topics, but are also open to own and alternative ideas. See here for some concrete suggestions.