Timetable information in the Course Catalogue may be subject to change.

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics - Distance Learning

Postgraduate Course: Design and Analysis of Parallel Algorithms (INFD11024)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 11 (Postgraduate)
Course typeOnline Distance Learning AvailabilityNot available to visiting students
SCQF Credits10 ECTS Credits5
SummaryThis course 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 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)
Pre-requisites Co-requisites
Prohibited Combinations Other requirements None
Course Delivery Information
Academic year 2022/23, Not available to visiting students (SS1) Quota:  None
Course Start Semester 2
Timetable Timetable
Learning and Teaching activities (Further Info) Total Hours: 100 ( Programme Level Learning and Teaching Hours 2, Directed Learning and Independent Learning Hours 98 )
Assessment (Further Info) Written Exam 75 %, Coursework 25 %, Practical Exam 0 %
Additional Information (Assessment) 75% Exam, 25% Coursework
Feedback Provided through regular weekly tutorial sessions and discussions on output of practical exercises as well as on formative assignment.
No Exam Information
Learning Outcomes
On completion of this course, the student will be able to:
  1. Define the structure of, and cost models associated with, the PRAM, mesh and hypercube models of parallel computation.
  2. 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.
  3. Explain and, with appropriate use of diagrams, sketch the structure and operation of well known parallel algorithms in a range of application areas..
  4. 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. 5. Understand and explain the limitations of applying these models to predict actual parallel performance.
Reading List
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
Special Arrangements This is an Online Learning course. On-campus students should refer instead to INFR11179 - Design and Analysis of Parallel Algorithms
KeywordsAlgorithms,DAPA,Parallel,EPCC,HPC,High Performance Computing,Parallelism,Parallel Computing,Online
Course organiserDr Oliver Brown
Tel: (0131 6)50 5201
Course secretaryMr James Richards
Tel: 90131 6)51 3578
Help & Information
Search DPTs and Courses
Degree Programmes
Browse DPTs
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Important Information