Threads and Executors

Motivation

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.

Background

Tutorial

Java 8 Concurrency Tutorial: Threads and Executors

Javadocs

interface Partitioner

partitionRange(data,min,maxExclusive)

class PivotLocation

getLeftSidesUpperExclusive()

getRightSidesLowerInclusive()

Code to Implement

(Optional But Recommended) 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

Completing this optional warm up will help you when you implement #XQuicksort.

Threads

Javadocs

interface ThreadFactory

newThread

class Thread

constructor

start

join

class SimpleThreadFactory

class:	SimpleThreadFactory.java
methods:	newThread
package:	tnx.lab.thread
source folder:	student/src/main/java

Video:Thread Start and Join

method: Thread newThread(Runnable target) (sequential implementation only)

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

class:	TAgeSum.java
methods:	sumUpperLowerSplit
package:	tnx.lab.thread
source folder:	student/src/main/java

method: int sumUpperLowerSplit(int[] ages, ThreadFactory threadFactory) (parallel implementation required)

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

VIDEO: Executor submit and Future get

VIDEO: Executor invokeAll

Javadocs

interface ExecutorService

submit

invokeAll

interface Future

get

Mistake To Avoid: Do NOT call shutdown

Each method you write will be passed an executor. You need not (and should NOT) invoke shutdown(). That is the responsibility of whoever created the executor. For example, a JUnit test would do this if it was appropriate (i.e. it created an executor and was not using the common pool).

XNucleobaseCount

This part of the assignment should be very familiar as it is to a large degree implementing the Nucleobase Counting assignment with Executors instead of Habanero. It also adds a divide and conquer implementation of nucleobase counting.

class:	XNucleobaseCount.java
methods:	countLowerUpperSplit countNWaySplit countDivideAndConquer countDivideAndConquerKernel
package:	tnx.lab.executor
source folder:	student/src/main/java

Tip:Use countRangeSequential() from Nucleobase_Counting

lower upper split

method: int countLowerUpperSplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase) (parallel implementation required)

n-way split

method: int countNWaySplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int numTasks) (parallel implementation required)

Please feel free to use the provided SliceUtils createNSlices(byte[] data, int numSlices). Then use the Java for each loop to iterate over the slices to create your tasks.

divide-and-conquer

method: int countDivideAndConquer(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int threshold) (parallel implementation required)

This method should just get things going by invoking the countDivideAndConquerKernel on the entire chromosome array.

method: int countDivideAndConquerKernel(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int min, int maxExclusive, int threshold) (parallel implementation required)

NOTE: When you get down below the threshold and convert from parallel to sequential execution, do NOT feel compelled to build a sequential divide and conquer. Just invoke countRangeSequential on the remaining range. It is not like divide and conquer gives you a performance benefit in counting like it would for sorting.

XQuicksort

class:	XQuicksort.java
methods:	sequentialQuicksort sequentialQuicksortKernel parallelQuicksort parallelQuicksortKernel
package:	tnx.lab.executor
source folder:	student/src/main/java

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 the X10 family of languages 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.

RiceX Lecture on Quicksort

Warning:Unlike in Sarkar's and McDowell’s videos which use inclusive maximums, CSE 231 consistently uses exclusive maximums to avoid having to subtract 1 all of the time.

sequential

method: void sequentialQuicksort(int[] data, Partitioner partitioner) (sequential implementation only)

method: void sequentialQuicksortKernel(int[] data, int min, int maxExclusive, Partitioner partitioner) (sequential implementation only)

parallel

method: void parallelQuicksort(ExecutorService executor, int[] data, int threshold, Partitioner partitioner) (parallel implementation required)

Make sure to use a thread safe data structure like ConcurrentLinkedQueue and NOT an unsafe data structure like LinkedList.

method: void parallelQuicksortKernel(ExecutorService executor, int[] data, int min, int maxExclusive, Queue<Future<?>> futures, int threshold, Partitioner partitioner) (parallel implementation required)

(Optional) Parallel Partition Challenge

the partitioning step can also be done in parallel with scan.

class:	ParallelPartitioner.java
methods:	partitionRange
package:	sort.fun.quick
source folder:	student/src/main/java

method: PivotLocation partitionRange(int[] data, int min, int maxExclusive) (parallel implementation required)

Testing Your Solution

Correctness

class:	ThreadsAndExecutorsTestSuite.java
package:	tnx.lab
source folder:	testing/src/test/java

Sub test suites have been created so you can test portions of the lab separately.

Performance

class:	NucleobaseCountTiming.java
package:	tnx.lab.executor
source folder:	src/main/java

class:	QuicksortTiming.java
package:	tnx.lab.executor
source folder:	src/main/java

Rubric

As always, please make sure to cite your work appropriately.

Total points: 100

SimpleThreadFactory subtotal: 5

• Correct newThread (5)

TAgeSum subtotal: 10

• Correct sumUpperLowerSplit (10)

XNucleobaseCount subtotal: 40

• Correct count2WaySplit (10)
• Correct countNWaySplit (15)
• Correct countDivideAndConquer and countDivideAndConquerKernel (15)

XQuicksort subtotal: 35

• Correct sequentialQuicksort and sequentialQuicksortKernel (10)
• Correct parallelQuicksort and parallelQuicksortKernel (25)

Whole project:

• Clarity and efficiency (10)

Pledge, Acknowledgments, Citations

As always, fill out the Pledge, Acknowledgments, and Citations file: lab3-pledge-acknowledgments-citations.txt