COMP40180 Parallel Algorithms Design and Analysis

Academic Year 2013/2014

The aim of this module is to Introduce students to parallel algorithm design and analysis, with a particular emphasis on practical implementation of parallel algorithms using the message-passing interface MPI and the C programming language and possibly some other programming environments. The module introduces a number of different strategies for parallelisation of computationally intensive algorithms. Methods for evaluating the performance of parallel algorithms are discussed

Students are required to implement a number of parallel algorithms and evaluate the performance of these algorithms on multi-processor machines.

Topics covered in the module include:
Introduction to parallel computing;
Abstract models of parallel computers, such as the PRAM model;;
Basic communication operators;;
Message-passing and MPI;
Performance and scalability analysis of parallel algorithms;
Task assignment and dynamic load balancing;
Parallel applications, such as discrete optimization; linear algebra, dense and sparse parallel matrix solvers; iterative and direct parallel linear solvers etc.

Show/hide contentOpenClose All

Curricular information is subject to change

Learning Outcomes:

By the end of this module, students should

Understand the main principles underlying the parallelisation of high-performance algorithms;
Understand the theory underlying performance analysis of parallel algorithms;
Be able to apply simple models of communication operators to estimate the performance of parallel algorithms;
Be able to write a parallel program that implements the algorithms discussed on the course;
Be able to carry out an empirical evaluation of the performance of a parallel algorithm on a real multi-processor machine

Student Effort Hours: 
Student Effort Type Hours
Lectures

24
Practical

40
Computer Aided Lab

12
Autonomous Student Learning

40
Total

116
 
Requirements, Exclusions and Recommendations

Not applicable to this module.



 
Description % of Final Grade Timing
Examination: Written Examination

60

 2 hour End of Trimester Exam
Assignment: Assignments

40

 Week 12

Compensation

This module is not passable by compensation

Resit Opportunities

In-semester assessment

Remediation

If you fail this module you may repeat, resit or substitute where permissible