Postgraduate Course: Design and Analysis of Parallel Algorithms (EPCD11007)
Course Outline
| School | School of Informatics |
College | College of Science and Engineering |
| Credit level (Normal year taken) | SCQF Level 11 (Postgraduate) |
| Course type | Online Distance Learning |
Availability | Not available to visiting students |
| SCQF Credits | 10 |
ECTS Credits | 5 |
| Summary | This 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 2024/25, Not available to visiting students (SS1)
|
Quota: None |
| Course Start |
Semester 1 |
| Course Start Date |
16/09/2024 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
100
(
Online Activities 30,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
68 )
|
| Assessment (Further Info) |
Written Exam
0 %,
Coursework
100 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
100% Coursework split into:«br /»
1) Formative question (0%)«br /»
2) Summative short answer question (25%)«br /»
3) Exam-style short-answer questions (75%) - offered over usually one to two weeks maximum. |
| Feedback |
Provided through regular weekly tutorial sessions and discussions on output of practical exercises as well as on formative and summative assignments. |
| No Exam Information |
Learning Outcomes
On completion of this course, the student 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; 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.
- 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.
- Understand and explain the limitations of applying these models to predict actual parallel performance.
|
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 instead refer to EPCC11007. |
| Keywords | Algorithms,DAPA,Parallel,EPCC,HPC,High Performance Computing,Parallelism,Parallel Computing |
Contacts
| Course organiser | Dr Evgenij Belikov
Tel: (01316) 505109
Email: |
Course secretary | Mr James Richards
Tel: 90131 6)51 3578
Email: |
|
|
University Homepage