Difference between revisions of "Parallel Partition"

From CSE231 Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 50: Line 50:
  
 
==(Optional) Parallel Partition Challenge==
 
==(Optional) Parallel Partition Challenge==
The partitioning step can also be done in [https://www.cse.wustl.edu/~angelee/archive/cse341/fall14/handouts/lecture08.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 [https://www.cse.wustl.edu/~angelee/archive/cse341/fall14/handouts/lecture08.pdf in parallel] with [[Scan|Scan]] remarkably similar to how [[Pack|Pack]] worked.
  
{{CodeToImplement|ParallelPartitioner|partitionRange|sort.challenge.quick}}
+
{{CodeToImplement|ParallelPartitioner|partitionRange|sort.quick.challenge}}
  
 
{{Parallel|PivotLocation partitionRange(int[] data, int min, int maxExclusive)}}
 
{{Parallel|PivotLocation partitionRange(int[] data, int min, int maxExclusive)}}
Line 58: Line 58:
 
=Testing Your Solution=
 
=Testing Your Solution=
 
==Correctness==
 
==Correctness==
{{TestSuite|ParallelPartitionerTestSuite|sort.challenge.quick}}
+
{{TestSuite|_ParallelPartitionerTestSuite|sort.quick.challenge}}

Latest revision as of 09:31, 1 April 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 remarkably similar to how Pack worked.

class: ParallelPartitioner.java Java.png
methods: partitionRange
package: sort.quick.challenge
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.quick.challenge
source folder: testing/src/test/java