05-05-2012, 12:33 PM
Parallel Programming
EDU-R8rNbqcxu4PKqT5.ppt (Size: 212.5 KB / Downloads: 348)
Sorting Problem
Permute: unordered sequence ordered sequence
Typically key (value being sorted) is part of record with additional values (satellite data)
Most parallel sorts designed for theoretical parallel models: not practical
Our focus: internal sorts based on comparison of keys
Attributes of Sequential Quicksort
Average-case time complexity: (n log n)
Worst-case time complexity: (n2)
Occurs when low, high lists maximally unbalanced at every partitioning step
Can make worst-case less probable by using sampling to choose pivot value
Example: “Median of 3” technique
Quicksort Good Starting Point for Parallel Algorithm
Speed
Generally recognized as fastest sort in average case
Preferable to base parallel algorithm on fastest sequential algorithm
Natural concurrency
Recursive sorts of low, high lists can be done in parallel
Definitions of “Sorted”
Definition 1: Sorted list held in memory of a single processor
Definition 2:
Portion of list in every processor’s memory is sorted
Value of last element on Pi’s list is less than or equal to value of first element on Pi+1’s list
We adopt Definition 2: Allows problem size to scale with number of processors