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 2022/23, 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)
||75% Written Examination
||Formative feedback: one class text delviered mid-Semester will be entirely formative and students will receive feedback on this before the first summative assessment. Students will also receive feedback on the summative class test before the main exam.
||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.
- 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.
- 5. Understand and explain the limitations of applying these models to predict actual parallel performance.
|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 Oliver Brown
Tel: (0131 6)50 5201
|Course secretary||Mr James Richards
Tel: 90131 6)51 3578