Design and Analysis of Parallel Algorithms (Level 11) (VS1) (P01363)

? Credit Points : 10 ? SCQF Level : 11 ? Acronym : INF-P-DAPA-V

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.

Entry Requirements

? This course is only available to part year visiting students.

? This course is a variant of the following course : P00995

? Pre-requisites : For Informatics PG students only, or by special permission of the School. Students should also have familiarity with, and ability to apply, asymptotic ("big-O") notation and associated techniques to describe and analyse the behaviour of simple iterative and recursive algorithms (for example, mergesort, nested loop matrix multiplication). The specific algorithms are not important - what matters is experience of working at this level of abstraction. This course is only available to part-year visiting students who are only in Edinburgh for Semester 1.

Subject Areas

Home subject area

Parallel and Distributed Computing, (School of Informatics, Schedule O)

Delivery Information

? Normal year taken : Postgraduate

? Delivery Period : Semester 1 (Blocks 1-2)

? Contact Teaching Time : 2 hour(s) per week for 10 weeks

First Class Information

Date	Start	End	Room	Area	Additional Information
20/09/2007	09:00	09:50	Room G18, Adam Ferguson Building	Central

All of the following classes

Type	Day	Start	End	Area
Lecture	Monday	09:00	09:50	Central
Lecture	Thursday	09:00	09:50	Central

Summary of Intended Learning Outcomes

It is anticipated that students who complete the course 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. They will be able to 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 pseudocode, textual explanation and diagrams.