View source for K Mer Balance Assignment

=Motivation=
Balancing the work load is not always straightforward.  A sample chromosome from the NIH has enough inconclusive reads that it is split into 50 sub-sequences.  The lengths of these sub-sequences vary wildly, from ~1,000 to ~10,000,00.

[[File:Chromosome sub sequence lengths.png|600px]]

[https://docs.google.com/spreadsheets/d/1d2qqxXZ_Mhp6DL9HxkhRrHq61GQoRzpf-Sf-4ZitsGo/ spreadsheet]

While creating a task for each of the 50 sub-sequences would be in our target range of 2X to 10X the the number of processors for an 8 processor machine, the workload balance would be terrible.  Over 40 of the sequences are tiny, and only 3 are of lengths of any real significance.  Thus, most of the processors would be sitting around idle while the last 3 processors finished up the 3 longest sub-sequences... then only 2 would be working, and finally the last one would finish up.  Once could, one supposes, use the Ranges exercise from before to slice up each of the sub-sequences, but we only really want to slice up the long sub-sequences and leave the short ones unsliced.

=Code To Investigate=
interface KMerBalancer provides a default implementation of createReasonableSlices(sequences, k) which you will use in each of your parallel k-mer counters.  You will note, that createReasonableSlices invokes two methods you will implement: calculateReasonableThreshold and createSlices.

{{CollapsibleCode|createReasonableSlices|
<syntaxhighlight lang="java">
default List<ByteArrayRange> createReasonableSlices(List<byte[]> sequences, int k) {
	int reasonableThreshold = calculateReasonableThreshold(sequences, k);
	return createSlices(sequences, k, (rangeLength) -> {
		return rangeLength > reasonableThreshold;
	});
}
</syntaxhighlight>}}

=Code To Implement=
==DefaultByteArrayRange==
As in our previous exercise where we implemented the class [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/range/exercise/Range.html Range], we will need to keep track of the min and maxExclusive.  Since we will also need to track the byte array which the range is associated with, we will need to handle originalCompleteSequence.

{{CodeToImplement|DefaultByteArrayRange|constructor<br/>originalCompleteSequence<br/>min<br/>maxExclusive|kmer.balance.exercise}}

===constructor and instance variables===
{{SequentialConstructor|public DefaultByteArrayRange(byte[] originalCompleteSequence, int min, int maxExclusive)}}

Store each of the parameters in private final instance variables.

{{Alert|As the name suggests, we are to hang onto the originalCompleteSequence.  Do not copy it or create a sub-array.  Just hang onto the reference in an instance variable. }}

===originalCompleteSequence===
{{Sequential|public byte[] originalCompleteSequence()}}

Return the originalCompleteSequence passed to the constructor.

===min===
{{Sequential|public int min()}}

Return the min passed to the constructor.

===maxExclusive===
{{Sequential|int maxExclusive()}}

Return the maxExclusive passed to the constructor.

==DefaultKMerBalancer==

DefaultKMerBalancer exists to balance the workload of a list of dna sub-sequences.  We have balanced workload before by breaking up data into as equally sized slices in the [[Ranges]] assignment.  We used the sliced up Ranges in everything from the [[Coarsening_Nucleobase_Count_Assignment|Coarsening Nucleobase Count]] to [[Matrix_MapReduce_Framework_Assignment|Matrix MapReduce]].

K-mer counting presents an additional challenge of having to deal with sub-sequences of radically different lengths.

{{CodeToImplement|DefaultKMerBalancer|sliceKernel<br/>createSlices<br/>calculateReasonableThreshold|kmer.balance.exercise}}

{{ tip | Get DefaultKMerBalancer working and then use it to balance all of your parallel KMerCounter implementations. }}

===createSlices===

{{Sequential|public static List<Slice<byte[]>> createSlices(List<byte[]> sequences, int k, IntPredicate slicePredicate)}}

{{warning | be sure to slice the offset (a.k.a. startingIndex) space}}

for N=10 and K=3, you should be slicing like this:

[[File:ThresholdSlices.svg|320px]]

{{CollapsibleYouTube|ThresholdSlices|<youtube>m56ee5spxiw</youtube>}}

===sliceKernel===
{{Sequential|private static void sliceKernel(List<ByteArrayRange> slices, byte[] sequence, int min, int max,
			IntPredicate slicePredicate)}}

Here we will employ a divide-and-conquer like strategy to fill the slices list with ByteArrayRanges that are all not too long.  We leverage the provided slicePredicate to test whether or not a range length from min to max is long enough to warrant dividing further.
<!--

This class is designed to take in a list of bytes and convert it into a list of slices. The slice class should be familiar to you from earlier in the semester, but feel free to refer back to the documentation on [[Slices]] for a quick recap. You should perform this task recursively and there are two methods you will need to implement. The createSlices method should just call the kernel (the "helper" method), and the kernel performs the recursion.

In the createSlices method, you should call the recursive kernel for each sequence that is longer than k in the list of sequences. When defining the min and max values, keep the information mentioned in the "Background" section in mind. As for the kernel, it should add a new slice to the collection of slices once the slice length dips below the provided threshold, but it should otherwise split itself into two smaller slices using recursion.

In our previous uses of Slices we leveraged sliceIndexId (and not originalData) since it was a n-way split/coarsening scenario.  Here we are recursively splitting each item in a collection of sub-sequences so originalData will be used (and sliceIndexId is unnecessary and can be specified as invalid (-1))..
-->

===threshold calculation===
{{Sequential|public static int calculateReasonableThreshold(List<byte[]> sequences, int k)}}

Define the threshold of slice length used to define an appropriate slicePredicate. 

Question to ask yourself: given a list of sequences which are to be k-mer counted, how would you calculate a reasonable threshold?

In addition to an estimation of the work required to count the specified sequences, knowing the number of [https://docs.oracle.com/javase/7/docs/api/java/lang/Runtime.html#availableProcessors() available processors] will also be necessary.

{{CollapsibleCode|availableProcessors|
<syntaxhighlight lang="java">
int processorCount = Runtime.getRuntime().availableProcessors();
</syntaxhighlight>
}}

=Testing Your Solution=
{{TestSuite|__BalanceTestSuite|kmer.balance.exercise}}

=Pledge, Acknowledgments, Citations=
{{Pledge|kmer-balance}}