Outline of Material for Test #2
General Algorithm Analysis Knowledge
- Be able to compute timings for algorithms using the network
model.
- Be prepared to use standard communication algorithms
(broadcast, reduction, etc) when describing and analyzing
parallel algorithms
- Be prepared to perform isoefficiency and cost optimality
analysis on any of the algorithms covered in the following
sections.
- In short, you are responsible for the basic analysis knowledge
that we have covered in Test#1
Parallel Sorting Algorithms
- Fundamentals
- Be able to define internal and external sorting algorithms.
- What is the compare-exchange operation? How is it implemented in
parallel
- What is the compare-split operation? How much time does it
require?
- What is a comparator? How do you draw one? What is a increasing
or decreasing comparator and how do you represent it (draw it).
- What does it mean to enumerate processors with respect to
sorting algorithms? Why is it important for parallel sorting
algorithms?
- Sorting Networks
- Be able to define a bitonic sequence, bitonic split and bitonic
merge.
- What is a bitonic merging network? What does it do? What is its
size? What is its depth? What does it look like?
- What is a bitonic sorting network? What does it do? What is its
size? What is its depth? What does it look like?
- How do we map a bitonic sorting network onto a hypercube? What
does the communication patterns look like?
- Be able to derive execution times for the bitonic sorting algorithm
on a hypercube architecture. Be able to discuss both mapping one
element per processor and many elements per processor.
- Be able to perform a scalability analysis of the bitonic sorting
algorithm on the hypercube architecture.
- Bubble Sort and Its Variants
- Be able to discuss the problem of parallelizing the bubble sort
algorithm.
- Be able to discuss the odd-even transposition algorithm. How many
steps does it have? What is the computation time? Is the
algorithm scalable?
- Quick-sort
- Why is it difficult to develop an efficient parallel quick-sort
algorithm by simply running independent subproblems in
parallel?
- What steps are involved in the hypercube quick-sort algorithm?
- Why is pivot selection critical for an efficient hypercube sorting
algorithm?
- What is the scalability of the quick-sort algorithm?
- Be prepared to estimate parallel running times for the hypercube
based quick-sort algorithm.
- Bucket Sort and Sample Sort
- What is the bucket sort? What assumptions does it make? What is
its serial run time?
- What steps are involved in the parallel bucket sort algorithm?
- What is a Sample Sort, how does it differ from Bucket Sort?
- How do we form a sample set in the Sample Sort? How big
is the sample?
- How do we sort the Sample in Sample Sort?
- What is the performance bottleneck for the Sample Sort?
- Be able to estimate running time for these algorithms.
- Be able to perform a scalability analysis of these algorithms.
Study Homework Assignments!