Modul

See partial achievement.

The students acquire a systematic understanding for algorithmic problems and their solutions in the field of parallel algorithms, building on existing knowledge in algorithmics. Additionally, they are able to apply learned techniques to related problems and to interpret and comprehend current research topics.

After successful attendance of the course, the students are able to

• explain terms, structures, basic problem definitions and algorithms from the lecture;
• decide which algorithms and data structures are suitable for solving a given problem and, if necessary, adapt them to the requirements ofa specific problem;
• execute algorithms and data structures, conduct a mathematically precise analysis, and prove their algorithmic properties;
• explain machine models from the lecture and analyze algorithms and data structures in them;
• analyze new problems from application contexts, reduce them to their algorithmic core and design an abstract model; design own solutions in this model using concepts and techniques from the lecture, analyze them and prove the algorithmic properties.

See partial achievement.

Models and their relation to real machines:
• shared memory - PRAM
• message passing - BSP
• circuits

Analysis: speedup, efficiency, scalability

Basic techniques:
• SPMD
• parallel divide-and-conquer
• collective communication
• load balancing

Concrete algorithms (examples):
• collective communication (including large data volumes): broadcast,
• reduce, prefix sums, all-to-all exchange
• matrix computations
• sorting
• list ranking
• minimum spanning trees
• load balancing: master worker with adaptive problem size, random
• polling, random distribution

The partial achievement Parallel Algorithms Exercise must be started before.

Lecture and exercise with 3 semester hours per week, 5 ECTS correspond to approx. 150 working hours, consisting of
• approx. 30 h attendance of the lecture and exercise session / block seminar
• approx. 60 h preparation and follow-up work
• approx. 30 h working on exercise sheets / preparation of seminar presentation
• approx. 30 h exam preparation