CS 159 Introduction to Parallel Processing

Check out the greensheet for official information about the class.

Final Exam Study guide

The following link will get you the final exam study guide.

In-class notes

I will try to make available copies of the notes I use in class. You should take your own notes to make sure you have included facts that I spoke about in class that might not be on the copies I make available.

• Parallel Computers
• Message Passing Computing
• Embarrassingly Parallel Problems
• Partitioning
• Pipelined Computations
• Synchronous Computations
• Load Balancing
• Shared Memory Multiprocessing
• Concurrency with Java
  Sample code
• Sorting Algorithms
• Supplemental Sorting Notes
  • Bitonic Notes 1
  • Bitonic Notes 2
  • Odd Even Notes 1
  • Odd Even Notes 2
  • Odd Even Notes 3
• Matrix Calculations
• Linda
  Sample code

Homework Assignments

Support materials

A good MPI tutorial can be found at this site.

Here's some notes on how to install and use a script for viewing the contents of your home folder in the slave nodes on the cluster.

Here's a list of MPI functions that should help your programs on the cluster computer.

FAQ

Q. While working on the homework a particular synchronization problem occurred to me.
Let's say we have the following state:

queue: contains only source node
two worker threads.

and the following set of events happens, in this order:

worker thread 1 starts
worker thread 2 starts
worker thread 1 removes first item off queue and sets it as it's task and begins processing
worker thread 2 sees queue is empty

now here's the problem. worker thread 2 has no initial task, and the queue is empty.. so it should quit! that's clearly not what we want. it sounds like the termination condition for a thread should be: queue is empty AND no other thread is currently processing.

I'm thinking using the array list of worker threads as a notification object to pass to all threads, so when a thread tries to pull an item off the queue and finds nothing, it can ask all the threads in the arraylist of worker threads if any of them are processing. if at least one thread is processing, i think i should then wait() on that arraylist and once a thread finishes processing it should notifyAll() on the arraylist. does this sound like a good strategy or am i interpreting the problem wrong?

A. You're correct in noticing that it's not enough that the queue be empty to trigger the termination of a thread. I like your solution. You might not have to query each thread, however. What if each time a thread gets a task, you increment a counter and each time a thread returns to get a new task you decrement a counter. Then the value of the counter lets you know if there are any threads currently working on a task. Only if the counter goes to zero and there are no more tasks in the queue is it safe to terminate.

Last modified: 5/13/07