Postgraduate Course: Design and Analysis of Parallel Algorithms (INFR11179)
|School||School of Informatics
||College||College of Science and Engineering
|Credit level (Normal year taken)||SCQF Level 11 (Postgraduate)
||Availability||Available to all students
|Summary||This module introduces theoretical design principles and analysis techniques that enable the creation and evaluation of efficient, scalable and portable algorithms for parallel computers. Concrete examples will span a range of application areas and architectural models seeking wherever possible to exploit commonality through appropriate abstraction.
Introduction: Conceptual frameworks for parallelism, message passing, shared address space, PRAM. Cost models for parallel algorithms. Cost efficiency and scalability. Inter-model emulation. Simple examples.
Problem solving strategies: Embarrassing parallelism, divide & conquer, pipelining, step-by-step parallelisation. Amdahl's Law. Gustafson's law.
Useful primitives: Collective communications, reduction, prefix.
Algorithms in selected problem areas, for example: Sorting (bitonic mergesort, hyperquicksort). Matrix oriented algorithms (multiplication, solving linear systems). Graph algorithms (spanning trees, single source & all-to-all shortest paths).
Entry Requirements (not applicable to Visiting Students)
||Other requirements|| None
Information for Visiting Students
|High Demand Course?
Course Delivery Information
|Academic year 2019/20, Available to all students (SV1)
|Learning and Teaching activities (Further Info)
Lecture Hours 20,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
|Assessment (Further Info)
|Additional Information (Assessment)
||100% Written Examination
||Formative feedback: Two sets of pencil-and-paper problems submitted during the semester with feedback returned within three weeks and feedback on exam papers.
||Hours & Minutes
|Main Exam Diet S1 (December)||Design and Analysis of Parallel Algorithms||2:00|
On completion of this course, the student will be able to:
- Define the structure of, and cost models associated with, the PRAM, mesh and hypercube models of parallel computation.
- Define the metrics of cost, speed-up and efficiency and use these as conceptual tools with which to analyse and discriminate between alternative candidate parallel algorithms for given problems; demonstrate, by the use of appropriately chosen examples, the importance of scalability in parallel algorithm design.
- Explain and, with appropriate use of diagrams, sketch the structure and operation of well known parallel algorithms in a range of application areas, including sorting, matrix and graph based problems.
- Apply a range of parallel algorithm design techniques (including divide-and-conquer and pipelining) to previously unseen problems, in order to create new parallel algorithms, which they will be able to describe using an informal mix of pseudo-code, textual explanation and diagrams.
|The recommended textbook for the course is A. Grama, A. Gupta, G. Karypis & V. Kumar 'Introduction to Parallel Computing', (2nd Ed), 2003.|
|Graduate Attributes and Skills
||Solution Exploration, Evaluation and Prioritisation.
Communication of complex ideas in accessible language
Working in an interdisciplinary field
Programming and Scripting
|Additional Class Delivery Information
||2 lectures per week
|Keywords||Algorithms,DAPA,Parallel,EPCC,HPC,High Performance Computing,Parallelism,Parallel Computing
|Course organiser||Dr Daniel Holmes
|Course secretary||Mr Ben Morse
Tel: (0131 6)51 3398