SCQF Level: 08
Module Code: CMP202
Credit Value: 20
Term: Term 2
School: School of Arts, Media and Games
This module builds on Data Structures and Algorithms 1 by introducing students to some of the practical performance concerns in the selection and implementation of algorithms, using a range of case studies drawn from typical real-world applications.
The aim of this Module is to provide the student with : To develop computational and algorithmic thinking and show how data structures and algorithms are used efficiently in 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 Measuring performance
Basic techniques, sources of error [round off, range, instability, discretisation], profiling, analysing and presenting results
2 Parallel programming
Why to parallelise, Amdahl's law, high-level approaches to parallelisation, parallel design
3 Low-level programming with threads
Starting and joining threads, sharing data safely, mutual exclusion, synchronisation objects, lock-free
4 High-level parallel programming
Task-based parallelism, data-parallel problems, exploiting locality
5 Instruction-level parallelism
SIMD instructions, automatic vectorisation
6 Header 6
GPU architectures, appropriate algorithms for GPUs, GPU profiling
7 Application case studies
Awareness of common sorting, numerical, image processing and searching and optimization algorithms (and associated data structures) and a recognition as to which are relevant for chosen field of study e.g. Spatial trees, pathfinding and AI, database indexing, password hashing, simulation, file carving] and which can benefit from parallelisation.
Statement on Teaching, Learning and Assessment
The module is taught using one or two two-hour lectorials each week, which introduce theoretical material and immediately put it into practice through guided lab exercises. Students demonstrate their attainment of the learning outcomes through the submission of a portfolio of completed lab exercises and a detailed performance analysis of a complex application of their choice based on one (or more) of the case studies.
Teaching and Learning Work Loads
|Supervised Practical Activity||28|
|Unsupervised Practical Activity||28|
Credit Value – The total value of SCQF credits for the module. 20 credits are the equivalent of 10 ECTS credits. A full-time student should normally register for 60 SCQF credits per semester.