Difference between revisions of "Pack"

From CSE231 Wiki
Jump to navigation Jump to search
m (fixed small typo)
 
(34 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
=Motivation=
 
=Motivation=
−
One of the applications for scan is pack operation. Given an input array, the operation produces an output array containing only the elements that satisfy some specified predicate.
+
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.
 
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.
Line 8: Line 8:
 
=Background=
 
=Background=
  
−
For example, if you have an integer array input:
+
For example, if you have a String array input:
 
{| class="wikitable"
 
{| class="wikitable"
−
|2||6||1||3||7||9||4
+
|Africa||Asia||SouthAmerica||NorthAmerica||Europe||Australia||Antarctica
 
|}
 
|}
−
You want to filter out all elements that are less than five. You can first create a flag array in which all the positions i where input[i] is less than 5 is flagged as "1" and all other positions are marked as "0".
+
 
 +
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".
 
{| class="wikitable"
 
{| class="wikitable"
 
|1||0||1||1||0||0||1
 
|1||0||1||1||0||0||1
Line 22: Line 23:
 
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.
 
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.
  
−
=Code To Investigate=
+
{| class="wikitable"
 +
|Africa||SouthAmerica||NorthAmerica||Antarctica
 +
|}
 +
 
 +
=Client=
 +
{{Client|ParallelPackClient|main|pack.client}}
 +
 
 +
{{CollapsibleCode|ParallelPackClient|
 +
<syntaxhighlight lang="java">
 +
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));
 +
});
 +
</syntaxhighlight>}}
 +
 
 +
{{CollapsibleConsole|ParallelPackClient Output|<pre style="border: 0px; background: #000; color:#fff;">[Africa, Asia, SouthAmerica, NorthAmerica, Europe, Australia, Antarctica]
 +
[Africa, SouthAmerica, NorthAmerica, Antarctica]</pre>}}
 +
 
 +
=Code To Investigate and Implement=
 +
==ParallelPacker==
 +
{{CodeToImplement|ParallelPacker|inclusiveSumScanner<br/>arrayGenerator<br/>pack|pack.exercise<br/>}}
 +
===constructor===
 +
{{CollapsibleCode|constructor|
 +
<syntaxhighlight lang="java">
 +
public ParallelPacker(OutOfPlaceSumScanner inclusiveSumScanner, IntFunction<C[]> arrayGenerator) {
 +
if (inclusiveSumScanner.isInclusive()) {
 +
this.inclusiveSumScanner = inclusiveSumScanner;
 +
} else {
 +
throw new IllegalArgumentException();
 +
}
 +
this.arrayGenerator = arrayGenerator;
 +
}
 +
</syntaxhighlight>}}
 +
===inclusiveSumScanner===
 +
{{Sequential|public OutOfPlaceSumScanner inclusiveSumScanner()}}
 +
 
 +
Return the value of the appropriate instance variable initialized in the constructor.
 +
 
 +
===arrayGenerator===
 +
{{Sequential|public IntFunction<C[]> arrayGenerator()}}
 +
 
 +
Return the value of the appropriate instance variable initialized in the constructor.
  
−
{{CodeToInvestigate|ParallelPack|createArray<br>isChangedFromNeighborOnTheLeft|pack.studio}}
+
===pack===
  
−
==createArray==
+
{{Parallel|public C[] pack(C[] array, Predicate<C> predicate)}}
−
You will definitely want to invoke createArray to... well... create the necessary array of a specified type and length.
 
  
−
<pre> private static <T> T[] createArray(Class<T[]> arrayType, int length) {
+
Applications which use scan tend to have step after step each with <math>\log n</math> CPL. Pack is no different. Each step can be parallelized.
−
return arrayType.cast(Array.newInstance(arrayType.getComponentType(), length));
 
−
}</pre>
 
  
−
==isChangedFromNeighborOnTheLeft==
+
'''Be sure to invoke your parallel scan from the [[Scan]] studio.'''
−
Invoking isChangedFromNeighborOnTheLeft is optional but still worth investigating.  Since our implementation of Hillis and Steele scan does not mutate the input data, it is not required. If you were to use a scan which mutated the input, you could still divine whether or not to copy the value into the packed array by using this method on the sum scan.
+
 
 +
'''Hint:''' Your parallel sum scanner can only accept an int[]. How might you generate an int[] from the given C[] (consider the "predicate" parameter").  
  
−
<pre> private static boolean isChangedFromNeighborOnTheLeft(int[] prefixSum, int index) {
+
The arrayGenerator.apply(int) takes in an integer, and returns an empty C[] of that length. How might you know, based off prior information (perhaps a scanned array), how long this array should be?
−
if (index > 0) {
 
−
return prefixSum[index - 1] < prefixSum[index];
 
−
} else {
 
−
return prefixSum[0] == 1;
 
−
}
 
−
}</pre>
 
  
−
=Code To Implement=
+
<!--
 +
===isChangedFromNeighborOnTheLeft===
 +
Invoking isChangedFromNeighborOnTheLeft is optional but still worth investigating.  Since our implementation of Hillis and Steele scan does not mutate the input data, it is not required.  If you were to use a scan which mutated the input, you could still divine whether or not to copy the value into the packed array by using this method on the sum scan.
  
−
==Parallel Pack==
+
<syntaxhighlight lang="java">
  
−
{{CodeToImplement|ParallelPack|pack|pack.studio}}
+
private static boolean isChangedFromNeighborOnTheLeft(int[] prefixSum, int index) {
 +
if (index > 0) {
 +
return prefixSum[index - 1] < prefixSum[index];
 +
} else {
 +
return prefixSum[0] == 1;
 +
}
 +
}
  
−
{{Parallel|public static <T> T[] pack(Class<T[]> arrayType, T[] arr, Predicate<T> predicate)}}
+
</syntaxhighlight>
 +
-->
  
 
=Testing Your Solution=
 
=Testing Your Solution=
−
{{TestSuite|PackTestSuite|pack.studio}}
+
{{TestSuite|PackTestSuite|pack.exercise}}
 +
 
 +
=Pledge, Acknowledgments, Citations=
 +
{{Pledge|pack}}

Latest revision as of 18:49, 22 March 2023

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 Java.png
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.svg (sequential implementation only)

Return the value of the appropriate instance variable initialized in the constructor.

arrayGenerator

method: public IntFunction<C[]> arrayGenerator() Sequential.svg (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.svg (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 generate an int[] from the given C[] (consider the "predicate" parameter").

The arrayGenerator.apply(int) takes in an integer, and returns an empty C[] of that length. How might you know, based off prior information (perhaps a scanned array), how long this array should be?


Testing Your Solution

class: PackTestSuite.java Junit.png
package: pack.exercise
source folder: testing/src/test/java

Pledge, Acknowledgments, Citations

file: pack-pledge-acknowledgments-citations.txt

More info about the Honor Pledge

Retrieved from "http://classes.engineering.wustl.edu/cse231/core/index.php?title=Pack&oldid=4871"