Threads and Executors

Where To Start

Habanero Java Library (HJlib) is the product of the Habanero Extreme Scale Software Research Laboratory. It builds on the X10 programming language.

HJlib provides some parallel features via static methods, most notably async and finish which handle a lot of the details of starting and joining tasks. We in CSE231 have thinly wrapped these methods for stylistic reasons as well as to afford more easily testing student code.

In this assignment we will remove the training wheels for a moment to get some experience with some core Java parallel features Threads and Executors.

Tutorial

Java 8 Concurrency Tutorial: Threads and Executors

Join All Warm Up

source: https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html

"Iterators are weakly consistent, returning elements reflecting the state of the queue at some point at or since the creation of the iterator."

JoinAllTestSuite

ThreadsEventually joinAllInQueueViaPoll

Threads

class SimpleThreadFactory

Video

Thread Start and Join

implement Thread newThread(Runnable target)

Create and return a new thread with the target Runnable parameter you are passed.

Do *NOT* start this thread.

Certainly, do *NOT* run this thread.

Do not pass Go. Do not collect $200.

To repeat: just create a new Thread with the target Runnable and return it.

TAgeSum

implement int sumUpperLowerSplit(int[] ages, ThreadFactory threadFactory)

You will need use the passed in ThreadFactory to create a new thread or two (at your preference), start any threads you create, and join them.

Think about where you need to start and join any Threads to ensure both correctness and an appropriate amount of parallelism.

Executors

Javadocs

ExecutorService

submit

invokeAll

Future

get

Videos

Executor submit and Future get

Executor invokeAll

XNucleobaseCount

note countSequential

public static int countSequential(byte[] chromosome, Nucleobase nucleobase) {
	return countRangeSequential(chromosome, nucleobase, 0, chromosome.length);
}

implement int countNWaySplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int numTasks)

Use SliceUtils

XQuicksort

Quicksort is an oldie but a goodie. First developed in 1959 and published in 1961 it is still the go to sorting algorithm today. The JDK8 implementation of Arrays.sort(array) is a DualPivotQuicksort.

Quicksort is also amenable to parallelism. Once the partitioning is done, both sides of the pivot can be sorted completely independently in parallel. This lends itself very nicely to Habanero as you can freely async as you divide and conquer, then join all of the tasks by wrapping it all in a single call to finish.

In this assignment you will mimic this behavior by submitting tasks to an executor, tracking the returned futures in in a ConcurrentLinkedQueue, then invoking get on all of those futures to mimic the single finish.

NOTE: ConcurrentLinkQueue's iterators are weakly consistent. Do the join all warm up to gain experience with handling this issue.

Videos

RiceX Lecture on Quicksort

note sequentialQuicksort

Unlike in Prof. Sarkar's videos which use inclusive maximums, in CSE 231 we use exclusive maximums to avoid having to subtract 1 all of the time. The provided sequentialQuicksort method hopes to get you on the right track.

public static void sequentialQuicksort(int[] array) {
	sequentialQuicksortKernel(array, 0, array.length);
}

Beyond 231

While perhaps a bit more complicated, and beyond the scope of this class, the partitioning step can also be done in parallel with scan.

Pledge, Acknowledgments, Citations

hw3-pledge-acknowledgments-citations.txt