Postgraduate Course: Design and Analysis of Parallel Algorithms (INFR11179)
Course Outline
School  School of Informatics 
College  College of Science and Engineering 
Credit level (Normal year taken)  SCQF Level 11 (Postgraduate) 
Availability  Available to all students 
SCQF Credits  10 
ECTS Credits  5 
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. 
Course description 
Syllabus:
Introduction: Conceptual frameworks for parallelism, message passing, shared address space, PRAM. Cost models for parallel algorithms. Cost efficiency and scalability. Intermodel emulation. Simple examples.
Problem solving strategies: Embarrassing parallelism, divide & conquer, pipelining, stepbystep 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 & alltoall shortest paths).

Entry Requirements (not applicable to Visiting Students)
Prerequisites 

Corequisites  
Prohibited Combinations  
Other requirements  None 
Information for Visiting Students
Prerequisites  None 
High Demand Course? 
Yes 
Course Delivery Information

Academic year 2019/20, Available to all students (SV1)

Quota: 80 
Course Start 
Semester 1 
Timetable 
Timetable 
Learning and Teaching activities (Further Info) 
Total Hours:
100
(
Lecture Hours 20,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
76 )

Assessment (Further Info) 
Written Exam
100 %,
Coursework
0 %,
Practical Exam
0 %

Additional Information (Assessment) 
100% Written Examination 
Feedback 
Formative feedback: Two sets of pencilandpaper problems submitted during the semester with feedback returned within three weeks and feedback on exam papers.

Exam Information 
Exam Diet 
Paper Name 
Hours & Minutes 

Main Exam Diet S1 (December)  Design and Analysis of Parallel Algorithms  2:00  
Learning Outcomes
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, speedup 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 divideandconquer 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 pseudocode, textual explanation and diagrams.

Reading List
The recommended textbook for the course is A. Grama, A. Gupta, G. Karypis & V. Kumar 'Introduction to Parallel Computing', (2nd Ed), 2003. 
Additional Information
Graduate Attributes and Skills 
Solution Exploration, Evaluation and Prioritisation.
Critical thinking
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 
Contacts
Course organiser  Dr Daniel Holmes
Tel:
Email: dholmes@exseed.ed.ac.uk 
Course secretary  Mr Ben Morse
Tel: (0131 6)51 3398
Email: Ben.Morse@ed.ac.uk 

