SCAN and Reduce
SCAN application — SCAN in quicksort
Let`s say if we have an array A[0:11] = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9]
How do we make use parallel computing to do the quick sort here.
In order to do a quick sort, we should first find a number as a pivot point.
Let take the A[9] = 3 as the pivot point.
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9]
^
|
pivot
so we can load each number into a memory cell, and compare all the number with A[9].
We create an array to store the result – if the number if greater than the pivot number, we assign it to 0, otherwise 1.
so we have
original array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9]
A[:] <= pivot ? [1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
scan the array
above we will have:[0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]
we can easily get the L[0:4] = [3, 1, 1, 2, 3]
Psedo code:
1. first we compute the flags,
2. do a scan to get the indices
3.