Difference between revisions of "Parallel Partition"

From CSE231 Wiki
Jump to navigation Jump to search
m (Cosgroved moved page Parallel Partitioner to Parallel Partition)
Line 1: Line 1:
 +
Partition does almost all of the work of quicksort.  Further, the classic sequential partition, although wonderful, dominates the span of the quicksort algorithm.  If we can parallelize partition, the span can be improved from <math>\mathcal{O}(n)</math> down to <math>\mathcal{O}(\lg^k{}n)</math>.
 +
 +
For N=16:
 +
 +
{| class="wikitable" style="text-align:center;"
 +
!
 +
! colspan="16" | <- - - - - - - - - - - - - - N - - - - - - - - - - - - - ->
 +
|-
 +
! ^
 +
| colspan="16" style="background-color:#CCCCFF;" | partition [0, 16)
 +
|-
 +
! &#124;
 +
| colspan="8" style="background-color:#CCCCFF;" | partition [0, 8)
 +
| colspan="8" | partition [8, 16)
 +
|-
 +
! lg N
 +
| colspan="4" style="background-color:#CCCCFF;" | partition [0, 4)
 +
| colspan="4" | partition [4, 8)
 +
| colspan="4" | partition [8, 12)
 +
| colspan="4" | partition [12, 16)
 +
|-
 +
! &#124;
 +
| colspan="2" style="background-color:#CCCCFF;" | partition [0, 2)
 +
| colspan="2" | partition [2, 4)
 +
| colspan="2" | partition [4, 6)
 +
| colspan="2" | partition [6, 8)
 +
| colspan="2" | partition [8, 10)
 +
| colspan="2" | partition [10, 12)
 +
| colspan="2" | partition [12, 14)
 +
| colspan="2" | partition [14, 16)
 +
|-
 +
! v
 +
| style="background-color:#CCCCFF;" | base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
|}
 +
 
==(Optional) Parallel Partition Challenge==
 
==(Optional) Parallel Partition Challenge==
 
The partitioning step can also be done in [http://www.classes.cec.wustl.edu/~cse341/web/handouts/lecture07.pdf parallel with scan].  While not particularly practical, it can get the CPL down to <math>\mathcal{O}(\lg^k{}n)</math>.
 
The partitioning step can also be done in [http://www.classes.cec.wustl.edu/~cse341/web/handouts/lecture07.pdf parallel with scan].  While not particularly practical, it can get the CPL down to <math>\mathcal{O}(\lg^k{}n)</math>.

Revision as of 22:46, 31 March 2023

Partition does almost all of the work of quicksort. Further, the classic sequential partition, although wonderful, dominates the span of the quicksort algorithm. If we can parallelize partition, the span can be improved from down to .

For N=16:

<- - - - - - - - - - - - - - N - - - - - - - - - - - - - ->
^ partition [0, 16)
| partition [0, 8) partition [8, 16)
lg N partition [0, 4) partition [4, 8) partition [8, 12) partition [12, 16)
| partition [0, 2) partition [2, 4) partition [4, 6) partition [6, 8) partition [8, 10) partition [10, 12) partition [12, 14) partition [14, 16)
v base base base base base base base base base base base base base base base base

(Optional) Parallel Partition Challenge

The partitioning step can also be done in parallel with scan. While not particularly practical, it can get the CPL down to .

class: ParallelPartitioner.java Java.png
methods: partitionRange
package: sort.challenge.quick
source folder: student/src/main/java

method: PivotLocation partitionRange(int[] data, int min, int maxExclusive) Parallel.svg (parallel implementation required)

Testing Your Solution

Correctness

class: ParallelPartitionerTestSuite.java Junit.png
package: sort.challenge.quick
source folder: testing/src/test/java