Difference between revisions of "Ranges"

From CSE231 Wiki
Jump to navigation Jump to search
Line 10: Line 10:
  
 
This studio is about creating an easier way to split data so that it can be worked on in parallel. The splitting of the data is still done sequentially. That means at no point in this studio should you be using fork() or join().
 
This studio is about creating an easier way to split data so that it can be worked on in parallel. The splitting of the data is still done sequentially. That means at no point in this studio should you be using fork() or join().
 
=Code To Investigate=
 
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html class IndexedRange]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html#%3Cinit%3E(int,int,int) constructor].
 
 
<pre>public IndexedRange(int sliceIndexId, int minInclusive, int maxExclusive)</pre>
 
 
This class has everything you need for [[Nucleobase_Counting#Coarsening_N-Way_Split|n-way split]] problems, specifically: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html#getSliceIndexId() getSliceIndexId()], [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html#getMinInclusive() getMinInclusive()], and [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/core/IndexedRange.html#getMaxExclusive() getMaxExclusive()].
 
  
 
=Code to Implement=
 
=Code to Implement=

Revision as of 07:33, 21 January 2022

credit for this assignment: Finn Voichick and Dennis Cosgrove

Motivation

Coarsening, or n-way split as we tend to call it in this course, comes up a fair amount. In this studio, we will create a Range class and a slice utility method, that allows us to split up our data n-times (depending on what value we pass in) in a consistent organized fashion. This makes sure that each thread is balanced in the work that it does, minimizing the Critical Path Length.

Since we will be utilizing this class throughout the semester in different studios and assignments, it is important that data is split up in a specific way. The tests should help make sure your solution is strictly adhering to the specification.

Mistakes To Avoid

Attention niels epting.svg Warning: Do NOT Parallelize

This studio is about creating an easier way to split data so that it can be worked on in parallel. The splitting of the data is still done sequentially. That means at no point in this studio should you be using fork() or join().

Code to Implement

class Range

class: Range.java Java.png
methods: constructor
min
maxExclusive
package: range.exercise
source folder: student/src/main/java

constructor

min

maxExclusive

class Ranges

class: Ranges.java Java.png
methods: createNSlices
package: range.exercise
source folder: student/src/main/java

slice

method: public static List<IndexedRange> createNSlices(int minInclusive, int maxExclusive, int numSlices) Sequential.svg (sequential implementation only)

Given a range [minInclusive, maxExclusive) and a number of slices to make, return a List of IndexedRanges. Understanding what a IndexedRange is and how it is used is important when writing this solution.

The goal is to have each slice's range be the entire array when put together, with no overlap. Some examples are giving below. Working through more examples can be a helpful way of figuring out what code to write if you get stuck.

Circle-information.svg Tip: In a slice, the minimum is inclusive and the maximum is exclusive. This means for two slices next to each other, slice1.getMaxExclusive() is equal to slice2.getMinInclusive().

Strict Specification

We are overly strict about the specification of how the data must be sliced up. This is to allow to accurately compare results intermediate results throughout the semester.

Example: array.length=8; numSlices=4

A A B B C C D D
Slice ID Min Inclusive Max Exclusive
0 0 2
1 2 4
2 4 6
3 6 8


Example: array.length=7; numSlices=4

Distribute the remainder 1 each to the lower end slices (the first few slices or the lower index slices).

A A B B C C D
Slice ID Min Inclusive Max Exclusive
0 0 2
1 2 4
2 4 6
3 6 7
Attention niels epting.svg Warning:Do NOT slice up the data by giving all of the remainder to one slice

A |B |C |D |D |D |D

Giving all the remainder to one slice defeats the purpose of balancing the workload!

Convenience Methods

In order to support primitive arrays (e.g. byte[], int[], et cetera) and non-primitive arrays (e.g. Object[]) we provide all of the public methods, each which simply call the single method requiring implementation:

	public static <C> List<IndexedRange> createNSlices(C[] data, int numSlices) {
		return createNSlices(0, data.length, numSlices);
	}

	public static List<IndexedRange> createNSlices(byte[] data, int numSlices) {
		return createNSlices(0, data.length, numSlices);
	}

	public static List<IndexedRange> createNSlices(char[] data, int numSlices) {
		return createNSlices(0, data.length, numSlices);
	}

	public static List<IndexedRange> createNSlices(short[] data, int numSlices) {
		return createNSlices(0, data.length, numSlices);
	}

	public static List<IndexedRange> createNSlices(int[] data, int numSlices) {
		return createNSlices(0, data.length, numSlices);
	}

	public static List<IndexedRange> createNSlices(long[] data, int numSlices) {
		return createNSlices(0, data.length, numSlices);
	}

	public static List<IndexedRange> createNSlices(float[] data, int numSlices) {
		return createNSlices(0, data.length, numSlices);
	}

	public static List<IndexedRange> createNSlices(double[] data, int numSlices) {
		return createNSlices(0, data.length, numSlices);
	}

Testing Your Solution

Correctness

class: SlicesTestSuite.java Junit.png
package: slice.studio
source folder: testing/src/test/java

Pledge, Acknowledgments, Citations

file: studio-slices-pledge-acknowledgments-citations.txt

More info about the Honor Pledge