Difference between revisions of "Parallel Partition"

From CSE231 Wiki
Jump to navigation Jump to search
Line 50: Line 50:
  
 
==(Optional) Parallel Partition Challenge==
 
==(Optional) Parallel Partition Challenge==
The partitioning step can also be done [https://www.cse.wustl.edu/~angelee/archive/cse341/fall14/handouts/lecture08.pdf in parallel] with [[Scan_Assignment|Scan] remarkably similar to how [[Pack_Assignment|Pack]] worked.
+
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.challenge.quick}}

Revision as of 22:52, 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 remarkably similar to how Pack worked.

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