|
|
EFFICIENT
PARALLEL ALGORITHMS - COMP308
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Instructor Information:
Name: Dr. Igor Potapov
Phone Number: 0151-795-4258
E-mail: potapov
[at] liverpool.ac.uk
Office Hours: Friday 12.00-13.00
Brief Description
This is a very introductory module on
parallel algorithmics and its relations to sequential computations. It will
be deal with how to compute things faster in parallel by breaking a problem into
smaller pieces and solve larger problems without resorting to larger
computers; what kind of parallel speedup is required, what architecture
should be used and whether a problem is amenable at all to a parallel attack.
Another issue is a programming language and a software supporting
implementation of parallel algorithms (Java, PVM, Compositional C++).
Syllabus
Fundamental Aspects of Classical Parallel Computation and Alternative
Models for Parallel Computing:
- The conceptual models of parallel
computers (the Parallel Random Access Machine and its variations) and
networks of processors. Tractable and intractable problems for parallel
computers. Basic PRAM Algorithms. [2 weeks]
- Commonly employed techniques in
efficient parallel algorithm design: Doubling, prefix sums computation,
balanced binary trees, Parallel divide-and-conquer etc. [1 week]
- Description of many specific
efficient algorithms for a variety of problems including, for example,
sorting, expression evaluation, graph theory (connected components, Euler
tours, vertex and edge coloring, matchings), computational geometry,
string-matching; sorting networks. [2 weeks]
- Communication networks and algorithms:
algorithms on meshes, hypercubes. [1 week]
- Implementations of parallel
algorithms: message-passing systems and PVM (Parallel Virtual Machine).
[1 week]
- Swarm algorithms and cellular
automata. [1 week]
- Self-assembling and Parallel
Bio-Computation. DNA computing, Membrane Computing [1 week]
- Quantum Computation and
Algorithms. [1 week]
Administration
details:
|
Lecture
|
Monday
|
10.00
|
Ashton Building lec. Theatre
|
|
Lecture
|
Tuesday
|
10.00
|
Ashton Building lec. Theatre
|
|
Lecture
|
Friday
|
10.00
|
Ashton Building lec. Theatre
|
Pre-requisites: COMP202 preferred
Assessment weightings:
20% continuous assessment (Class test + practical assignment)
80% written examination
Required Materials:
Required
Texts:
Introduction to Algorithms, Second Edition
Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
Introduction to Parallel Computing: Design and
Analysis of Algorithms.
Vipin Kumar, Ananth Grama, Anshul Gupta, and George Karypis,
Benjamin Cummings, November, (1st edition –1993) (2nd edition-2003).
Efficient
Parallel Algorithms.
A.Gibbons, W.Rytter, Cambridge
University Press 1988.
|
Week
|
|
Topics Covered
|
|
1
|
Introduction
|
Lecture 1-Introduction to Parallel Computations ppt
Lecture 2-Introduction to Parallel Computations
Lecture 3-PRAM model ppt
|
|
2
|
PRAM
Model
|
Lecture 4-Concurrent Write vs
Exclusive Write (PRAM) ppt
Lecture 5-Basic PRAM
algorithms ppt
Lecture 6-General algorithmic
techniques ppt
|
|
3
|
Algorithms on trees
|
Lecture 7-Parallel
prefix sum computation ppt
Lecture 8-The
Euler-tour technique ppt
Lecture 9-Parallel
Algorithms for expression evaluation ppt
|
|
4
|
Algorithms on graphs
|
Lecture 10-Parallel Pebble Game. ppt
Lecture 11-Parallel
computation of the Transitive Closure. ppt
Lecture 12-Fine-grained
and coarse-grained algorithms.
|
|
5
|
Mesh
algorithms
|
Lecture 13-Parallel construction of Euler cycle. ppt
Lecture 14-Mesh Connected Networks;Sorting Algorithms. ppt
|
|
6
|
Sorting
Networks
|
Lecture 15-Sorting networks ppt
Lecture 16-Bitonic and Merging sorting networks ppt
Lecture 17-Batcher’s merging network ppt
|
|
7
|
Message Passing
Computing
|
Lecture 18-Basic
Communication Operations:
Lecture 19-Broadcasting and Gossiping ppt
Lecture 20-Tractable
and intractable problems ppt
Lecture 21-Message
Passing Computing pdf
|
|
8
|
Unconventional
models and paradigms
|
Lecture
22-Parallel Virtual Machine pdf
Lecture
23-Cellular automata ppt
Lecture
24-Cellular automata
|
|
9
|
Unconventional
models and paradigms
|
Lecture 25-Swarm algorithms ppt
Lecture
26-Membrane computing ppt
|
|
10
|
Unconventional
models and paradigms
|
Lecture 28-DNA Computing ppt
Lecture 29-Quantum Computing
Lecture 30-Overview
|
|
|
|
|
|