PROJECT (groups)

• Parallel Rendering of Movie Frames, by A. Rajendran and V. Ramanujam
  
• Image Processing, by D. Runnels and F. Zand
  
• Parallel Volume Rendering, by Y. Mu and C. Smith
  
• Image Recognition, by G. Bond, L. Scardino and W. Arena
  
• Convex Hull, S. Roberts and D. Lajaunie
  
• Pattern Matching, G. Donaldson and M. Trouard
  
• Shortest Path, by R. Greer and G. Kirkland
  
• Graph Connectivity, R. Rekhi and D. M. Booth
  
• Matrix Multiplication, by J. McCoy and G. Adams
  
• Sparse Matrix Operations, by X. Huan and A. M. Farcas
  
• Queries in a Distributed Database, by J. Henry and C. Williams
  
• Othello, by T. Wilson and J. Bjursell
  

Usefull MPI links

Information about the clock() and other timing function

Material covered:

Current trends in multiprocessing

Shared memory computers
Distributed memory computers
Clusters
Shared-distributed memory computers
ASCI Project
ASCI Red
ASCI Blue Mountian
ASCI Pacific Blue
ASCI Option White


Why parallel computing?
Discussion of the project(s)

Distributed systems -- a bit of an overview
Formal model of a distributed system

Asynchronous systems
Synchronous systems
Timing model
Complexity of algorithms:

Time complexity Message complexity

Simple algorithms:
Broadcast
Convergecast
Flooding
Building a spanning tree
Building a depth-first spanning tree for a given root
Building a depth-first spanning tree without a given root


Leader election (in a ring topology):
The problem
Two algorithms for asynchronous systems:
Simple algorithm O(n^2)
Modified algorithm O(nlogn)

Two algorithms for synchronous systems:
Non-uniform algorithm
Uniform algorithm


Mutual exclusion for shared memory systems

Introduction to shared memory systems
Algorithm based on Test&Set registers
Algorithms based on Read-Modify-Write registers
Bakery algorithm and its limitations
Bounded mutual exclusion for two processors
Bounded mutual exclusion for n processors
Fast mutual exclusion for not-too-busy system


Fault-tolerant consensus

Synchronous system with simple crash failures

Resiliency
Consensus in an f-resilient system

Synchronous system with Byzantine failures

Homework 1 (individual)

Implement the broadcast algorithm (without using the broadcast primitive available in the MPI library). Test it on the "wiglaf" machine. Send me the working code. Due by: before class, Monday, September 18th.

Homework 2 (group)

Design and implement the initial WWW site for the group project. Due by: before class, Monday, September 18th.

Homework 3 (group)

Prepare a 5 minute presentation that will introduce your project to teh class. Due by: in class, Monday, September 25th.

Homework 3 (individual)

Compare the performance of the MPI broadcast and gather operations with your own implementations of the broadcast and convergecast algorithms for a varying number of processors and a varying length of the message. Write a paper describing the results of your experiments. Due by: before class, Wednesday, October 4th.

Homework 4 (group)

Update the WWW site for your project. Go to other project pages and reflect on what you like and what you do not like to improve your site. Add content! Due by: before class, Wednesday, October 11th.

Homework 5 (individual)

Compare the performance of the two ring election algorithms for asynchronous systems. Implement them using MPI as the data communication primitive. Run the experiments for varying message size and varying assignments of node identifiers and varying numbers of processors in the ring. Write a paper describing the results of your experiments. Due by: before I come to my office on Wednesday, October 25th.

Reading assignment - pages 1-109