# DEGREE REGULATIONS & PROGRAMMES OF STUDY 2016/2017

 University Homepage DRPS Homepage DRPS Search DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

# Postgraduate Course: Design and Analysis of Parallel Algorithms (INFR11028)

 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 the design principles and analysis techniques which enable the creation 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. * 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). Relevant QAA Computing Curriculum Sections: Concurrency and Parallelism, Data Structures and Algorithms
 Pre-requisites Co-requisites Prohibited Combinations Other requirements This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser. The following mathematics skills are also assumed: - familiarity with binary numbers, conversion to/from decimal - simple facts about and manipulation of logs and exponentials - O notation, proper definition and intuitive feel - summation of simple arithmetic and geometric series - matrix multiplication and Gaussian Elimination - very simple, neat recurrences, cf. easiest ones in MforInf2 The specific algorithms are not important - what matters is experience of working at this level of abstraction.
 Pre-requisites None
 Not being delivered
 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. They will be able to 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, including sorting, matrix and graph based problems. 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 pseudocode, textual explanation and diagrams.
 V. Kumar, A. Grama, A. Gupta & G. Karypis, 'Introduction to Parallel Computing: Design and Analysis of Algorithms', (2nd Ed), 2003.
 Course URL http://course.inf.ed.ac.uk/dapa Graduate Attributes and Skills Not entered Keywords Not entered
 Course organiser Dr Iain Murray Tel: (0131 6)51 9078 Email: I.Murray@ed.ac.uk Course secretary Ms Katey Lee Tel: (0131 6)50 2701 Email: Katey.Lee@ed.ac.uk
 Navigation Help & Information Home Introduction Glossary Search DPTs and Courses Regulations Regulations Degree Programmes Introduction Browse DPTs Courses Introduction Humanities and Social Science Science and Engineering Medicine and Veterinary Medicine Other Information Combined Course Timetable Prospectuses Important Information
© Copyright 2016 The University of Edinburgh - 3 February 2017 4:26 am