Postgraduate Course: Design and Analysis of Parallel Algorithms (INFR11028)
Course Outline
| School |
School of Informatics |
College |
College of Science and Engineering |
| Course type |
Standard |
Availability |
Available to all students |
| Credit level (Normal year taken) |
SCQF Level 11 (Postgraduate) |
Credits |
10 |
| Home subject area |
Informatics |
Other subject area |
None |
| Course website |
http://www.inf.ed.ac.uk/teaching/courses/dapa |
|
|
| Course description |
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
| 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 |
Course Delivery Information
|
| Delivery period: 2010/11 Semester 1, Available to all students (SV1)
|
WebCT enabled: No |
Quota: None |
| Location |
Activity |
Description |
Weeks |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| Central | Lecture | | 1-11 | 09:00 - 09:50 | | | | | | Central | Lecture | | 1-11 | | | | 09:00 - 09:50 | |
| First Class |
Week 1, Thursday, 09:00 - 09:50, Zone: Central. Room 2.12, Appleton Tower |
|
| Delivery period: 2010/11 Semester 1, Part-year visiting students only (VV1)
|
WebCT enabled: No |
Quota: None |
| Location |
Activity |
Description |
Weeks |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| Central | Lecture | | 1-11 | 09:00 - 09:50 | | | | | | Central | Lecture | | 1-11 | | | | 09:00 - 09:50 | |
| First Class |
Week 1, Thursday, 09:00 - 09:50, Zone: Central. Room 2.12, Appleton Tower |
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. |
| Please see Visiting Student Prospectus website for Visiting Student Assessment information |
Special Arrangements
| Not entered |
Contacts
| Course organiser |
Dr Michael Rovatsos
Tel: (0131 6)51 3263
Email: mrovatso@inf.ed.ac.uk |
Course secretary |
Miss Kate Weston
Tel: (0131 6)50 2701
Email: Kate.Weston@ed.ac.uk |
|
copyright 2010 The University of Edinburgh -
1 September 2010 6:11 am
|
University Homepage