Modul
Parallel Algorithms [M-INFO-100796]
Credits
5Recurrence
Jedes WintersemesterDuration
1 SemesterLanguage
EnglishLevel
4Version
3Responsible
Organisation
- KIT-Fakultät für Informatik
Bricks
Identifier | Name | LP |
---|---|---|
T-INFO-111857 | Parallel Algorithms Pass | 1 |
T-INFO-101333 | Parallel Algorithms | 4 |
Competence Certificate
See partial achievement.
Competence Goal
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.
Prerequisites
See partial achievement.
Content
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
Recommendation
The partial achievement Parallel Algorithms Exercise must be started before.
Workload
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