CS 159 Final Study Guide

This material is designed to get you to think about the kinds of facts that are important in this class. I make no claim that it is comprehensive. There are topics that may not be mentioned in this guide that are on the final because they appear in the textbook or in my notes.

Earlier study guides

The following links will get you the two earlier study guides for the first two midterms:

• Study Guide for Midterm 1
• Study Guide for Midterm 2

Chapter 10

• Explain how compare-exchange is accomplished between processors using MPI sends and recvs.
• Explain the block version of this approach (data partitioning).
• What is the parallel bubble sort algorithm and how does it compare to the sequential bubble sort algorithm.
• What is the odd-even transposition sort algorithm? Give an analysis of its performance relative to a sequential version.
• Describe the parallel merge sort algorithm. How does the way the processors are connected together influence this algorithm?
• Describe the odd-even merge sort algorithm and be able to analyze its timing.
• What is the bitonic sort algorithms and what is its timing?

Parallel Sort Theoretical material

• What is a sorting network?
• What is the 0-1 principle and what does it have to do with sorting networks?
• Draw the bitonic sort network for n = 8 or 16. Do the same for the odd-even merge sort.
• Do you understand the diagrams that show how the bitonic sort algorithm works? (Check out the links referenced in the handout notes.)
• Can you figure out how many compare-exchange elements it takes to implement the bitonic sort network or the odd-even merge-sort network?
• Can you determine the number of stages it will take to carry out either of these algorithms?

Matrix Computations

• Describe the row-column method for matrix-vector multiplication.
• Describe the linear combination of columns method for matrix-vector multiplication.
• How do these algorithms carry over to matrix-matrix multiplication?
• What is the difference beetween the Jacobi method and the Gauss-Seidel method for solving systems of linear equations?
• How do these various algorithms map to the parallel architectures we have examined (e.g. message-passing distributed memory, shared memory)?

Linda and Friends

• What is Linda?
• What is a tuple? What is tuple-space?
• What is an anti-tuple or template?
• What are the basic operations?
• How can we set up some basic parallel mechanisms such as barriers using Linda operations?
• Can you write a pseudo language version of a Linda program for some simple algorithm (see the matrix-vector multiplication example)?
• What are the issues related to implementing Linda in a parallel environment?
• What are JavaSpaces? What does it have to do with Linda?
• How is the JavaSpaces framework different from the Linda paradigm?