THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2012/2013
- ARCHIVE for reference only
THIS PAGE IS OUT OF DATE

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

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

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Course typeStandard AvailabilityAvailable to all students
Credit level (Normal year taken)SCQF Level 11 (Postgraduate) Credits10
Home subject areaInformatics Other subject areaNone
Course website http://www.inf.ed.ac.uk/teaching/courses/dapa Taught in Gaelic?No
Course descriptionThis 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 (not applicable to Visiting Students)
Pre-requisites Co-requisites
Prohibited Combinations Other requirements For Informatics PG and final year MInf students only, or by special permission of the School. 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.
Additional Costs None
Information for Visiting Students
Pre-requisitesNone
Displayed in Visiting Students Prospectus?Yes
Course Delivery Information
Delivery period: 2012/13 Semester 1, Available to all students (SV1) Learn enabled:  No Quota:  None
Location Activity Description Weeks Monday Tuesday Wednesday Thursday Friday
CentralLecture1-11 09:00 - 09:50
CentralLecture1-11 09:00 - 09:50
First Class Week 1, Thursday, 09:00 - 09:50, Zone: Central. Rm B1 Forrest hill
Exam Information
Exam Diet Paper Name Hours:Minutes
Main Exam Diet S2 (April/May)2:00
Delivery period: 2012/13 Semester 1, Part-year visiting students only (VV1) Learn enabled:  No Quota:  None
Location Activity Description Weeks Monday Tuesday Wednesday Thursday Friday
CentralLecture1-11 09:00 - 09:50
CentralLecture1-11 09:00 - 09:50
First Class Week 1, Thursday, 09:00 - 09:50, Zone: Central. Rm B1 Forrest hill
Exam Information
Exam Diet Paper Name Hours:Minutes
Main Exam Diet S1 (December)2:00
Summary of Intended Learning Outcomes
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.
Assessment Information
Written Examination 80
Assessed Assignments 20
Oral Presentations 0

Assessment
Two sets of pencil-and-paper problems.

If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year.
Special Arrangements
None
Additional Information
Academic description Not entered
Syllabus * 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
Transferable skills Not entered
Reading list V. Kumar, A. Grama, A. Gupta & G. Karypis, 'Introduction to Parallel Computing: Design and Analysis of Algorithms', (2nd Ed), 2003.
Study Abroad Not entered
Study Pattern Lectures 20
Tutorials 0
Timetabled Laboratories 0
Non-timetabled assessed assignments 20
Private Study/Other 60
Total 100
KeywordsNot entered
Contacts
Course organiserDr Iain Murray
Tel: (0131 6)51 9078
Email: I.Murray@ed.ac.uk
Course secretaryMiss Kate Weston
Tel: (0131 6)50 2701
Email: Kate.Weston@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
Timetab
Prospectuses
Important Information
 
© Copyright 2012 The University of Edinburgh - 14 January 2013 4:09 am