Data Structures and Algorithms 2

This module builds on Data Structures and Algorithms 1 by introducing students to parallel programming on shared memory and GPU architectures and the design techniques underpinning parallel applications, using a range of case studies drawn from typical real-world applications.

By the end of this module the student should be able to:

1. Be aware of the standard techniques of software performance measurement, including profiling, and apply these techniques to identify performance bottlenecks in real programs.
2. Understand the emerging importance of parallel programming in modern software development, and experiment with the performance impact of parallelising parts of an application.
3. Describe a variety of application-specific algorithms (sorting/numerical/image processing) and associated data structures in common use, and discuss the benefits and limitations of parallelisation.

1 Parallel programming

Why to parallelise, parallelism and concurrency, Amdahl's law, high-level approaches to parallelisation, parallel design

2 Low-level programming with threads

Starting and joining threads, sharing data safely, mutual exclusion, synchronisation objects, lock-free

3 High-level parallel programming

Task-based parallelism, message-passing parallelism, data-parallel problems, exploiting locality programming.

4 Instruction-level parallelism

SIMD instructions, automatic vectorisation

5 GPU Programming

GPU architectures, appropriate algorithms for GPUs, GPU profiling.

6 Parallel Patterns

Design patterns for parallel and concurrent programming. Awareness of common sorting, numerical, image processing and searching and optimization algorithms and how they can benefit from parallelisation.