Pack
Contents
Motivation
One of the applications for scan is the pack operation. Given an input array, the operation produces an output array containing only the elements that satisfy some specified predicate.
The problem with parallelizing pack is that although it is easy to determine whether an element should be filtered out into the output, we can't know where to put the element in the output array. It seems that placing an element into the output requires knowledge of the placement of the previous elements. This is where prefix sum becomes very useful.
Think about quick sort. In the partition step, we are given a pivot and need to separate the array by the predicate of whether an element is larger than the pivot. This is the perfect place to use the pack operation. You are going to build a more general pack filter in this studio, but you can still attempt the parallel partitioner challenge here: Quicksort Parallel Partitioner.
Background
For example, if you have a String array input:
| Africa | Asia | SouthAmerica | NorthAmerica | Europe | Australia | Antarctica |
You want to filter out all Strings which do not contain "c". You can first create a flag array in which all the indices where arr[index] contains an "c" is flagged as "1" and all other positions are marked as "0".
| 1 | 0 | 1 | 1 | 0 | 0 | 1 |
The prefix sum of this flag array is:
| 1 | 1 | 2 | 3 | 3 | 3 | 4 |
Notice how each position that that was flagged now has a distinct number assigned to it in the prefix sum array. We can use this to help us index the output array.
| Africa | SouthAmerica | NorthAmerica | Antarctica |
Client
| class: | ParallelPackClient.java | CLIENT |
| package: | main | |
| source folder: | student/src/pack.client/java |
| ParallelPackClient |
|---|
String[] continentNames = { "Africa", "Asia", "SouthAmerica", "NorthAmerica", "Europe", "Australia", "Antarctica" };
launchApp(() -> {
String[] packedNamesWhichContainC = ParallelPack.pack(String[].class, continentNames, (continentName) -> {
return continentName.contains("c");
});
System.out.println(Arrays.toString(continentNames));
System.out.println(Arrays.toString(packedNamesWhichContainC));
});
|
| ParallelPackClient Output |
|---|
[Africa, Asia, SouthAmerica, NorthAmerica, Europe, Australia, Antarctica] [Africa, SouthAmerica, NorthAmerica, Antarctica] |
Code To Investigate and Implement
ParallelPacker
| class: | ParallelPacker.java |  |
| methods: | inclusiveSumScanner arrayGenerator pack |
|
| package: | pack.exercise |
|
| source folder: | student/src/main/java |
constructor
| constructor |
|---|
public ParallelPacker(OutOfPlaceSumScanner inclusiveSumScanner, IntFunction<C[]> arrayGenerator) {
if (inclusiveSumScanner.isInclusive()) {
this.inclusiveSumScanner = inclusiveSumScanner;
} else {
throw new IllegalArgumentException();
}
this.arrayGenerator = arrayGenerator;
}
|
inclusiveSumScanner
method: public OutOfPlaceSumScanner inclusiveSumScanner() 
(sequential implementation only)
Return the value of the appropriate instance variable initialized in the constructor.
arrayGenerator
method: public IntFunction<C[]> arrayGenerator() (sequential implementation only)
Return the value of the appropriate instance variable initialized in the constructor.
pack
method: public C[] pack(C[] array, Predicate<C> predicate) 
(parallel implementation required)
Applications which use scan tend to have step after step each with CPL. Pack is no different. Each step can be parallelized.
Be sure to invoke your parallel scan from the Scan studio.
Hint: Your parallel sum scanner can only accept an int[]. How might you convert the initial C[] (consider the "predicate" parameter").
The arrayGenerator.apply(int) takes in an integer representing the length of, and returns an empty C[] of that size. How might you know, based off prior information (perhaps a scanned array), know how long this array should be?
Testing Your Solution
| class: | PackTestSuite.java |  |
| package: | pack.exercise | |
| source folder: | testing/src/test/java |
Pledge, Acknowledgments, Citations
| file: | pack-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge
