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:
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?