Parallel Sorting

Question 1

What is the best sequential comparison-based sorting algorithm running time?

Answer 1

O(nlogn)

Question 2

What is the difference between a compare exchange operation and a compare split operation?

Answer 2

Compare split contains more than one element per processor with each of the two processors have n/p elements.

Question 3

What is the computational cost of performing a compare split operation when processors contain sub-arrays of size n/p?

Answer 3

ts + (tw * n / p)

ts = comparison time
tw = data transfer time

Question 4

How can we parallelize divide-and-conquer-based sorting algorithms using functional decomposition?
Is functional decomposition sufficient to obtain an efficient comparison-based parallel sorting algorithm?

Answer 4

By dividing the problem into smaller independent subproblems thru functional decomposition, we can parallelize these independent sections to achieve faster execution times.

We need data decomposition because data is always distributed and won’t be on one processor.

Question 5

The bitonic sort is a parallel version of which divide and conquer sorting algorithm?

Answer 5

Merge Sort

Question 6

How is the merge step implemented in the bitonic sort?
Is there merge also parallelized?

Answer 6

Bitonic sort recursively split the input into halves and then repeatedly performs bitonic merging operations to combine them until all is sorted.

Question 7

What are sorting networks?
How can they be used to define sorting algorithms?

Answer 7

Networks of comparators designed for sorting.

Used to order which comparisons and exchanges are performed.

Question 8

What is an increasing comparator? How is it implemented?

Answer 8

compares two elements and orders them in increasing order.

Used for increasing tones for bitonic sequences.

Question 9

In the bitonic sorting algorithm, why do we need both increasing and decreasing comparator elements in the sorting network?

Answer 9

To perform compare and exchange operations using the sorting process.

Question 10

What is the definition of a bitonic sequence?

Answer 10

A sequence of increasing and then decreasing elements (or vice versa) with no repetitions in pattern.

Question 11

What happens to a bitonic sequence when we perform a bitonic split?

Answer 11

The sequence is divided into two smaller bitonic sequences to be sorted.

Question 12

What does a bitonic merging network do to a bitonic sequence?

Answer 12

Merge two bitonic sequences into a single bitonic sequence.

Question 13

What is the depth of a bitonic sorting network that can sort a sequence of size 2^n.

Answer 13

log2(n)

Question 14

What is the cost of a serial bitonic sorting algorithm when applied to a sequence of size n?

Answer 14

O(n log2 n)

Question 15

If we want to sort n numbers on p processors with n-p elements per processor, what is the depth of the bitonic sorting network that would be used to sort this sequence?

What operations do the elements of this bitonic sorting network represent?

Answer 15

Depth: O(log2 n)

n/2 comparators

Question 16

In a bitonic sorting algorithm for n numbers on p processors, we will use a serial sort to sort n/p elements.

Is this sort performed at the beginning or the end of the parallel sorting algorithm? Why does it need to be performed at this time?

Answer 16

In the beginning

Used to locally sort each on each processor before they combine into parallel phases.

Question 17

Be able to state the parallel running time of the bitonic sort of n numbers on p processors

Answer 17

Tp = O(n/plogn/p) + O(n/plog2p) + O(n/plog2p)
Tp = Local sort + comparisons + communication

Question 18

Is bubble sort as it is typically implemented in serial easily parallelized? Why or why not?

Answer 18

Is difficult to parallelize since the algorithm has no concurrency.

Question 19

What is the odd-even transposition sort? Is this sort parallelizable?

Answer 19

Repeatedly compares odd and even indices until sorted
Yes, it’s parallelizable

Question 20

What is the serial complexity of the odd-even transposition sort?

Answer 20

O(n^2)

Question 21

When using the odd-even transposition sort with n/p elements per processor, what base operation is used to define the algorithm?

Answer 21

The first step is a local sort with O(n/p log n/p)

Question 22

What are the comparison and communication costs of the parallel odd-even transposition sort?

Answer 22

Comparisons and Communications are both O(n).

Question 23

Where are most of the computational time spent in the serial quicksort algorithm?

Answer 23

Partitioning each subproblem

Question 24

A scalable parallel quicksort algorithm requires both functional decomposition and data decomposition.
Be able to explain how both of these parallel decomposition techniques are used in the parallel quicksort.

Answer 24

Functional Decomposition: Divides problem into smaller, independent subproblems that can be solved in parallel.

Data Decomposition: Divides input data into small chunks that can be processed in parallel.

Question 25

Given a pivot in an array of numbers, how does one partition the array using multiple processors executing in parallel?

Answer 25

Once an array has been divided by its pivot, we can work on the subarrays independently.

Question 26

In the global rearrangement phase of the array splitting step, what parallel algorithm needs to be performed to determine where to store the split sub-arrays into the global array?

Question 27

Why is the performance of the parallel quick sort algorithm more sensitive to pivot selection than the serial algorithm?

Answer 27

Because picking a bad pivot will lead to load imbalance which lowers parallel efficiency.

Question 28

What is the bucket sort algorithm and under what conditions can it produce a O(n) serial sorting algorithm?

Answer 28

Numbers are divided into m equal sized intervals with then each bucket sorted independently.

When data is even distributed among the buckets.

Question 29

How can we parallelize the bucket sort algorithm?

Answer 29

Have p processors each do a bucket from m buckets.

Question 30

How is the sample sort a generalization of the bucket sort algorithm?

Answer 30

The sample uses a set of splitters instead of using an algebraic method, making the cost increase to n log n.

Question 31

How are splitters selected in the parallel sample sort?

Answer 31

Picking the medians of the medians.

Question 32

What are the possible methods of sorting the sample in the parallel sample sort algorithm?

Question 33

How are the sample sort and the quick sort related?