PDP Chapter 7: Sorting Algorithms

Sorting Algorithms

• Sorting is a fundamental operation in parallel and distributed processing.
• Several sorting algorithms exist, including Bubble Sort, Quick Sort, Bucket Sort, and Sample Sort.
• Comparison-based sorting algorithms have a lower bound of O(n log n) for n numbers.
• Bubble Sort has a complexity of O(n²). It is difficult to parallelize due to lack of concurrency, but a simple variant can uncover concurrency.

Topic Overview

• Issues arise when sorting on parallel computers.
• Bubble Sort and its variants are discussed.
• Quick Sort is examined.
• Bucket and Sample Sort are included.

Sorting: Overview

• Sorting is a widely used and well-understood kernel.
• The core operation in comparison-based sorting is comparing and exchanging elements.

Bubble Sort and its Variants

• Bubble Sort has a time complexity of O(n²).
• Bubble Sort is difficult to parallelize due to its sequential nature.
• Some variants offer potential for parallelism.

Sorting: Basics

• Parallel sorting sequences are often distributed across processors.
• Input and output lists are typically distributed.
• The sorted list is partitioned, ensuring each processor's elements in a partition are smaller than those in later partitions.

Sorting: Parallel Compare Exchange Operation

• A parallel compare-exchange operation involves processors exchanging elements and keeping the appropriate minimum or maximum value locally.
• Process P_i and P_j send data to each other, then maintain the minimum and maximum in their respective regions.

Sorting: Basics

• The parallel counterpart to sequential comparison involves assigning the smaller element to the processor with the smaller ID in O(t_s+t_w) time.
• The process is called compare split if each processor has more than one element (n/p elements per processor).
• After compare split, smaller n/p elements reside at P_i and larger n/p elements at P_j, with i<j.
• The time taken is O(t_s+t_wn/p).

Sorting: Parallel Compare Split Operation

• Each process (P_i or P_j) sends blocks of n/p elements to the other.
• Processes then merge (received block + local block), maintaining appropriate halves for each (smaller or larger elements).

Odd-Even Transposition

• After n phases of odd-even element swapping, the sequence is sorted.
• Each phase involves O(n) comparisons.
• In serial, the complexity is O(n²).

Parallel Odd-Even Transposition

• Given one element per processor, each processor performs one compare-exchange per iteration.
• The time complexity for this approach is O(n).
• It's optimal compared to the baseline serial algorithm but not optimally efficient overall.

Parallel Odd-Even Transposition Procedure

• A detailed procedure using ID and compare exchange minimum and maximum is described.

Parallel Odd-Even Transposition

• Algorithm considers blocks of n/p elements per processor.
• Initially, a local sort is performed on each processor's portion.
• Subsequent steps replace compare-exchange with compare-split operations.
• Time complexity is given in terms of local sort, comparisons, and communication.

Example: MPI Odd-Even Sort

• Code snippets demonstrating an MPI implementation for the Odd-Even Sort algorithm.

Quicksort

• Quicksort is a commonly used sequential sorting algorithm.
• It's simple, has low overhead, and its average case complexity is optimal (O(n log n)).
• The pivot selection is critical to performance.

Quicksort Algorithm

• Selects a pivot element from the list.
• Divides the input list into two sublists: elements smaller than the pivot, and elements larger than the pivot.
• Recursively applies the quicksort algorithm to the sublists.

Quicksort: Performance and Task Generation

• Performance depends heavily on the quality of the pivot selection.
• Dynamic task generation means the tree shape and size depend on the input array's data.

Bucket and Sample Sort

• Bucket Sort divides the range of input numbers into intervals (buckets).
• Elements are assigned to buckets based on their value.
• Elements within each bucket are locally sorted.
• Performance is related to bucket size distribution and sorted buckets.

Parallel Bucket Sort

• Parallelization of bucket sort is straightforward.
• Individual processors are responsible for ranges of input values.
• Elements are routed to their assigned processors via all-to-all communication.
• Each processor sorts its received elements locally.

Parallel Bucket and Sample Sort

• Splitter selection is critical in assigning ranges/buckets to processors.
• The splitter selection method divides the input into blocks of size n/p and sorts each block.
• From each sorted block, evenly spaced elements are selected as sample elements to determine buckets.
• This guarantees few elements per bucket.

Parallel Bucket and Sample Sort: Analysis

• The internal sort takes O((n/p) log (n/p)) + O(P) time.
• The all-to-all broadcast, sorting sample elements, and selecting evenly spaced splitters contribute a time complexity.
• Reorganizing elements is O(n/p)
• Overall time complexity is given.
• Comparison of Bucket Sort to Odd-Even Transposition is provided.

MPI Sample Sort

• Code snippets showing an MPI implementation for Sample Sort are included.
• The code allocates memory for splitters, sorts local elements, selects equally spaced elements, computes bucket counts, determines starting locations for buckets, and performs an all-to-all communication to send/receive elements to designated processors (buckets).
• Finally, the code performs the final local sort step.

Explore the fundamental concepts of sorting algorithms in parallel computing. This quiz covers various algorithms like Bubble Sort, Quick Sort, Bucket Sort, and Sample Sort, including their complexities and challenges in parallelization. Test your understanding of comparison-based sorting techniques and their operational intricacies.