Difference between revisions of "Threads and Executors"

From CSE231 Wiki
Jump to navigation Jump to search
 
(109 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
=Where To Start=
+
This assignment has been updated: [[Thread_and_Executor_Service_Assignment|Thread and ExecutorService]]
−
Habanero Java Library (HJlib) is the product of the [https://wiki.rice.edu/confluence/display/HABANERO/Habanero+Extreme+Scale+Software+Research+Project Habanero Extreme Scale Software Research Laboratory]. It builds on the [http://x10-lang.org/ X10 programming language].
+
<!--
 +
credit for this assignment: [[User:Finn|Finn Voichick]] and [[User:cosgroved|Dennis Cosgrove]]
 +
=Motivation=
 +
The [http://x10-lang.org/ X10 family of programming languages], including [https://wiki.rice.edu/confluence/display/HABANERO/Habanero+Extreme+Scale+Software+Research+Project Habanero] and our own modest [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/edu/wustl/cse231s/v5/V5.html V5], provide a less cumbersome way to write parallel programs with [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/edu/wustl/cse231s/v5/V5.html#async-edu.wustl.cse231s.v5.api.CheckedRunnable- async] and [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/edu/wustl/cse231s/v5/V5.html#finish-edu.wustl.cse231s.v5.api.CheckedRunnable- finish].
  
−
HJlib provides some parallel features via static methods, most notably [https://www.cs.rice.edu/~vs3/hjlib/doc/edu/rice/hj/Module1.html#async-edu.rice.hj.api.HjSuspendable- async] and [https://www.cs.rice.edu/~vs3/hjlib/doc/edu/rice/hj/Module0.html#finish-edu.rice.hj.api.HjSuspendable- finish] which handle a lot of the details of starting and joining tasks.  We in CSE231 have [http://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/edu/wustl/cse231s/rice/habanero/Habanero.html thinly wrapped these methods] for stylistic reasons as well as to afford more easily testing student code.
+
Finish has particularly nice semantics: keeping track of and joining all of its descendant tasks. 
 +
In this lab we will remove the training wheels for a moment to get some experience with some core Java parallel features [https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html Thread] and [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html ExecutorService].
  
−
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.
+
Tracking all of the descendant tasks provides us with an opportunity to use a thread safe data structure ([https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html ConcurrentLinkedQueue]) as well as deal with the [[#.28Optional_But_Recommended.29_Join_All_Warm_Up | complications of weakly consistent iterators]].
  
−
===Tutorial===
+
=Background=
 
[http://winterbe.com/posts/2015/04/07/java8-concurrency-tutorial-thread-executor-examples/ Java 8 Concurrency Tutorial: Threads and Executors]
 
[http://winterbe.com/posts/2015/04/07/java8-concurrency-tutorial-thread-executor-examples/ Java 8 Concurrency Tutorial: Threads and Executors]
  
−
===JUnit ThreadsAndExcutorsTestSuite===
+
=Code to Implement=
 +
==(Optional But Recommended) Join All Warm Up==
 +
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html ConcurrentLinkedQueue] is a thread safe data structure.  Multiple threads can add and remove from it without fear.  The order they will be in might not be deterministic, but it won't lose anybody.  We will end up using a ConcurrentLinkedQueue to track all of the spawned Futures in the [[#XQuicksort]] section of this lab.
  
−
Mac: Command+Shift+T ThreadsAndExcutorsTestSuite
+
Sadly, [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html ConcurrentLinkedQueue's documentation] reports that:
  
−
Windows: Ctrl+Shift+T ThreadsAndExcutorsTestSuite
+
: ''"Iterators are weakly consistent, returning elements reflecting the state of the queue at some point at or since the creation of the iterator."''
  
−
=Join All Warm Up=
+
This means that if all of the items aren't in the queue when you start iterating through them, then you are not guaranteed to get updated when new items get added.
  
−
'''OPTIONAL'''
+
Therefore, using the standard iterating for loop from <code>ThreadsRightNow</code> will NOT work for <code>ThreadsEventually</code>:
  
−
source: https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html
+
<nowiki>/* package-private */ static int joinAllInQueueViaIteration(Queue<Thread> queue) throws InterruptedException {
 +
int count = 0;
 +
for (Thread thread : queue) {
 +
thread.join();
 +
count++;
 +
}
 +
return count;
 +
}</nowiki>
  
−
''"Iterators are weakly consistent, returning elements reflecting the state of the queue at some point at or since the creation of the iterator."''
+
Think about how you can make sure that all of threads are joined.
 +
<spoiler show="spoiler" hide="spoiler">Drain the queue by repeatedly polling until it is empty.  Be sure to actually join the threads.</spoiler>
  
−
JoinAllTestSuite
+
{{CodeToImplement|ThreadsEventually|joinAllInQueueViaPoll|tnx.warmup.joinall}}
  
−
ThreadsEventually joinAllInQueueViaPoll
+
{{Sequential|private static int joinAllInQueueViaPoll(Queue<Thread> queue)}}
 +
 
 +
NOTE: this method should return the number of threads joined.
  
 
Completing this optional warm up will help you when you implement [[#XQuicksort]].
 
Completing this optional warm up will help you when you implement [[#XQuicksort]].
  
−
=Threads=
+
===Testing Your Solution===
−
==Javadocs==
+
====Correctness====
 +
{{TestSuite|JoinAllTestSuite|tnx.warmup.joinall}}
 +
 
 +
==Threads==
 +
While we strive to make CSE 231 generally applicable across libraries and languages, it would be madness to have a parallel programming class in Java and not have students know how to create a Thread, start it, and join it.  In this section of the lab, you will do just that.
 +
 
 +
<youtube>P8z7dFIdcmM</youtube> box link: [https://wustl.box.com/s/pngsojhj8291qj8q78ypmzl0jd1l69sw Thread Start and Join]
 +
===Code To Use===
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadFactory.html interface ThreadFactory]
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadFactory.html interface ThreadFactory]
 
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadFactory.html#newThread-java.lang.Runnable- newThread]
 
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadFactory.html#newThread-java.lang.Runnable- newThread]
Line 39: Line 62:
 
:[https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#start-- join]
 
:[https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#start-- join]
  
−
==class SimpleThreadFactory==
+
As always, the [[Reference_Page#Threads|wiki's reference page]] can be of help.
−
===Video===
 
−
[https://wustl.box.com/s/pngsojhj8291qj8q78ypmzl0jd1l69sw Thread Start and Join]
 
  
−
===implement <code>Thread newThread(Runnable target)</code>===
+
===SimpleThreadFactory===
 +
{{CodeToImplement|SimpleThreadFactory|newThread|tnx.lab.thread}}
 +
 
 +
{{Sequential|Thread newThread(Runnable target)}}
  
 
Create and return a [https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#Thread-java.lang.Runnable- new thread with the target Runnable parameter] you are passed.
 
Create and return a [https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#Thread-java.lang.Runnable- new thread with the target Runnable parameter] you are passed.
Line 55: Line 79:
 
To repeat: just create a new Thread with the target Runnable and return it.
 
To repeat: just create a new Thread with the target Runnable and return it.
  
−
==TAgeSum==
+
===TAgeSum===
−
===implement <code>int sumUpperLowerSplit(int[] ages, ThreadFactory threadFactory)</code>===
+
{{CodeToImplement|TAgeSum|sumUpperLowerSplit|tnx.lab.thread}}
 +
 
 +
{{Parallel|int sumUpperLowerSplit(int[] ages, ThreadFactory threadFactory)}}
  
 
You will need use the passed in ThreadFactory to [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadFactory.html#newThread-java.lang.Runnable- create a new thread] or two (at your preference), [https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#start-- start] any threads you create, and [https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#join-- join] them.
 
You will need use the passed in ThreadFactory to [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadFactory.html#newThread-java.lang.Runnable- create a new thread] or two (at your preference), [https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#start-- start] any threads you create, and [https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#join-- join] them.
Line 62: Line 88:
 
Think about where you need to start and join any Threads to ensure both correctness and an appropriate amount of parallelism.
 
Think about where you need to start and join any Threads to ensure both correctness and an appropriate amount of parallelism.
  
−
=Executors=
+
==Executors==
 +
<youtube>8qh9LMhvNXI</youtube>
 +
<youtube>tuAkLb99sLE</youtube>
  
−
==Javadocs==
+
===Code To Use===
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html interface ExecutorService]
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html interface ExecutorService]
−
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#submit-java.util.concurrent.Callable- submit]
+
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#submit-java.util.concurrent.Callable- submit(task)]
−
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#invokeAll-java.util.Collection- invokeAll]
+
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#invokeAll-java.util.Collection- invokeAll(tasks)]
 +
 
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html interface Future]
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html interface Future]
−
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html#get-- get]
+
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html#get-- get()]
 +
 
 +
[http://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/count/assignment/NucleobaseCounting.html NucleobaseCounting]
 +
: [http://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/count/assignment/NucleobaseCounting.html#countRangeSequential-byte:A-edu.wustl.cse231s.bioinformatics.Nucleobase-int-int- countRangeSequential(chromosome,targetNucleobase,min,maxExclusive)]
  
−
==Videos==
+
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/studio/Slices.html Slices]
−
[https://wustl.box.com/s/2pqv6vsbirt6zi4304ycrh7jfgkb0dhi Executor submit and Future get]
+
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/studio/Slices.html#createNSlices-byte:A-int- <nowiki>createNSlices(data, numSlices)</nowiki>].
  
−
[https://wustl.box.com/s/17q7xupx1tagdnnfg057teme4lbq4w6r Executor invokeAll]
 
  
−
==Mistake To Avoid: Do NOT call shutdown==
+
As always, the [[Reference_Page#Executors|wiki's reference page]] can be of help.
 +
 
 +
===Mistake To Avoid: Do NOT call shutdown===
 
Each method you write will be passed an executor.  You need not (and should NOT) invoke [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#shutdown-- 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 [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinPool.html#commonPool-- common pool]).
 
Each method you write will be passed an executor.  You need not (and should NOT) invoke [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#shutdown-- 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 [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinPool.html#commonPool-- common pool]).
  
−
==XNucleobaseCount==
+
===XNucleobaseCount===
 
This part of the assignment should be very familiar as it is to a large degree implementing the [[Nucleobase_Counting|Nucleobase Counting assignment]] with Executors instead of Habanero.  It also adds a divide and conquer implementation of nucleobase counting.  
 
This part of the assignment should be very familiar as it is to a large degree implementing the [[Nucleobase_Counting|Nucleobase Counting assignment]] with Executors instead of Habanero.  It also adds a divide and conquer implementation of nucleobase counting.  
 +
{{CodeToImplement|XNucleobaseCount|countLowerUpperSplit<br>countNWaySplit<br>countDivideAndConquer<br>countDivideAndConquerKernel|tnx.lab.executor}}
  
−
===note countSequential===
+
{{Tip|Use [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/count/lab/NucleobaseCounting.html#countRangeSequential(byte%5B%5D,edu.wustl.cse231s.bioinformatics.Nucleobase,int,int) countRangeSequential()] from [[Nucleobase_Counting]]}}
−
<nowiki>public static int countSequential(byte[] chromosome, Nucleobase nucleobase) {
+
====lower upper split====
−
return countRangeSequential(chromosome, nucleobase, 0, chromosome.length);
+
{{Parallel|int countLowerUpperSplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase)}}
−
}</nowiki>
+
 
 +
NOTE: the tests will enforce that you use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#submit-java.util.concurrent.Callable- submit] and [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html#get-- get].
 +
 
 +
====n-way split====
 +
{{Parallel|int countNWaySplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int numTasks)}}
 +
 
 +
Please feel free to use your own [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/studio/Slices.html Slices] [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/slice/studio/Slices.html#createNSlices-byte:A-int- <nowiki>createNSlices(byte[] data, int numSlices)</nowiki>].  Then use the [https://docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html Java for each loop] to iterate over the slices to create your tasks.
  
−
===implement <code>int countRangeSequential(byte[] chromosome, Nucleobase nucleobase, int min, int max)</code>===
+
NOTE: the tests will enforce that you use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#invokeAll-java.util.Collection- invokeAll].
−
===implement <code>int count2WaySplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase)</code>===
 
−
===implement <code>int countNWaySplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int numTasks)</code>===
 
  
−
Please feel free to use the provided [https://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/edu/wustl/cse231s/slices/SliceUtils.html#createNSlices-byte:A-int- SliceUtils] [https://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/edu/wustl/cse231s/slices/SliceUtils.html#createNSlices-byte:A-int- <nowiki>createNSlices(byte[] data, int numSlices)</nowiki>].  Then use the [https://docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html Java for each loop] to iterate over the slices to create your tasks.
+
====divide-and-conquer====
 +
{{Parallel|int countDivideAndConquer(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int threshold)}}
  
−
===implement <code>int countDivideAndConquer(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int threshold)</code>===
 
 
This method should just get things going by invoking the countDivideAndConquerKernel on the entire chromosome array.
 
This method should just get things going by invoking the countDivideAndConquerKernel on the entire chromosome array.
  
−
===implement <code>int countDivideAndConquerKernel(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int min, int max, int threshold)</code>===
+
{{Parallel|int countDivideAndConquerKernel(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int min, int maxExclusive, int threshold)}}
−
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.
+
 
 +
NOTE: the tests will enforce that you use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#submit-java.util.concurrent.Callable- submit] and [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Future.html#get-- get].
 +
 
 +
 
 +
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==
+
===XQuicksort===
 
Quicksort is an oldie but a goodie.  First developed in 1959 and [https://dl.acm.org/citation.cfm?doid=366622.366644 published in 1961] it is still the go to sorting algorithm today.  The JDK8 implementation of [https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-int:A- Arrays.sort(array)] is a DualPivotQuicksort.
 
Quicksort is an oldie but a goodie.  First developed in 1959 and [https://dl.acm.org/citation.cfm?doid=366622.366644 published in 1961] it is still the go to sorting algorithm today.  The JDK8 implementation of [https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-int:A- 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 [http://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/edu/wustl/cse231s/rice/habanero/Habanero.html#async-edu.rice.hj.api.HjSuspendable- async] as you divide and conquer, then join all of the tasks by wrapping it all in a single call to [http://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/edu/wustl/cse231s/rice/habanero/Habanero.html#finish-edu.rice.hj.api.HjSuspendable- finish].   
+
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 [http://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/edu/wustl/cse231s/rice/habanero/Habanero.html#async-edu.rice.hj.api.HjSuspendable- async] as you divide and conquer, then join all of the tasks by wrapping it all in a single call to [http://www.cse.wustl.edu/~cosgroved/courses/cse231/f17/apidocs/edu/wustl/cse231s/rice/habanero/Habanero.html#finish-edu.rice.hj.api.HjSuspendable- 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.
 
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: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html ConcurrentLinkQueue]'s iterators are weakly consistent.  Do the [[#Join All Warm Up]] to gain experience with handling this issue.
+
{{Warning| [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html ConcurrentLinkQueue]'s iterators are weakly consistent.  Do the [[#.28Optional_But_Recommended.29_Join_All_Warm_Up | Join All Warm Up]] to gain experience with handling this issue. }}
  
−
===Videos===
+
<youtube>jP2998MvX9o</youtube>
−
[https://edge.edx.org/courses/RiceX/COMP322/1T2014R/courseware/a900dd0655384de3b5ef01e508ea09d7/be41f5f2b11a4445aa4be174e94f1717/16 RiceX Lecture on Quicksort]
 
  
−
===note sequentialQuicksort===
+
<youtube>iqnvIeIhGPw</youtube> [https://edge.edx.org/courses/RiceX/COMP322/1T2014R/courseware/a900dd0655384de3b5ef01e508ea09d7/be41f5f2b11a4445aa4be174e94f1717/16 RiceX Lecture on Quicksort]
−
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.
 
  
−
<nowiki>public static void sequentialQuicksort(int[] array) {
+
<youtube>SLauY6PpjW4</youtube>
−
sequentialQuicksortKernel(array, 0, array.length);
+
 
−
}</nowiki>
+
{{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.}}
 +
 
 +
====Code To Use====
 +
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/quick/Partitioner.html interface Partitioner]
 +
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/quick/Partitioner.html#partitionRange-int:A-int-int- partitionRange(data,min,maxExclusive)]
 +
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/quick/PivotLocation.html class PivotLocation]
 +
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/quick/PivotLocation.html#getLeftSidesUpperExclusive-- getLeftSidesUpperExclusive()]
 +
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/quick/PivotLocation.html#getRightSidesLowerInclusive-- getRightSidesLowerInclusive()]
 +
 
 +
Note: Investigate SequentialPartitioner.
 +
 
 +
====XSequentialQuicksorter====
 +
{{CodeToImplement|XSequentialQuicksorter|sortRange|tnx.lab.executor}}
 +
 
 +
{{Sequential|public void sortRange(T[] data, Comparator<T> comparator, int min, int maxExclusive)}}
 +
 
 +
{{Warning|Do NOT implement your own partition.  Call Partitioner partitionRange method.  It will do this work for you.}}
 +
 
 +
{{Warning|Do NOT invoke partitionRange twice.  Invoke partitionRange once and catch the return value in a variable.  Then use the two methods on the single instance of PivotLocation. }}
 +
 
 +
====XParallelQuicksorter====
 +
{{CodeToImplement|XParallelQuicksorter|kernel<br/>sortRange|tnx.lab.executor}}
 +
 
 +
{{Parallel|private void kernel(Queue<Future<?>> futures, T[] data, Comparator<T> comparator, int min, int maxExclusive)}}
 +
 
 +
{{Tip | Be sure to <code>test</code> the <code>isParallelPredicate</code> to determine if the current range length is worthy of parallel processing or if you should fall back to the <code>sequentialSorter</code>. }}
 +
 
 +
{{Sequential|public void sortRange(T[] data, Comparator<T> comparator, int min, int maxExclusive)}}
 +
 
 +
{{Tip | Make sure to use a thread safe data structure like [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html ConcurrentLinkedQueue] and NOT an unsafe data structure like [https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html LinkedList]. }}
 +
 
 +
{{Tip | <code>return null;</code> from your lambdas to invoke the [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html#submit-java.util.concurrent.Callable- overloaded Callable version of submit(task)] to deal with the checked exceptions. }}
 +
 
 +
{{Warning|Do NOT implement your own partition.  Call Partitioner partitionRange method.  It will do this work for you.}}
 +
 
 +
{{Warning|Do NOT invoke partitionRange twice.  Invoke partitionRange once and catch the return value in a variable.  Then use the two methods on the single instance of PivotLocation. }}
 +
 
 +
==(Optional) Parallel Partition Challenge==
 +
The partitioning step can also be done in [http://www.classes.cec.wustl.edu/~cse341/web/handouts/lecture07.pdf parallel with scan].  While not particularly practical, it can get the CPL down to <math>\mathcal{O}(\lg^k{}n)</math>.
  
−
===implement <code>void sequentialQuicksortKernel(int[] array, int min, int maxExclusive)</code>===
+
For details on how to complete this challenge, check out: [[Quicksort_Parallel_Partitioner]]
  
−
===implement <code>void parallelQuicksort(ExecutorService executor, int[] array, int threshold)</code>===
+
=Testing Your Solution=
−
Make sure to use a thread safe data structure like [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html ConcurrentLinkedQueue] and NOT an unsafe data structure like [https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html LinkedList].
+
==Correctness==
 +
There is a top-level test suite comprised of sub test suites which can be invoked separately when you want to focus on one part of the assignment.
 +
===top level===
 +
{{TestSuite|ThreadsAndExecutorsTestSuite|tnx.lab}}
 +
===sub===
 +
{{TestSuite|ThreadsTestSuite|tnx.lab.thread}}
 +
{{TestSuite|NucleobaseExecutorTestSuite|tnx.lab.executor}}
 +
{{TestSuite|QuicksortExecutorTestSuite|tnx.lab.executor}}
 +
====Less Time Consuming Suite====
 +
{{TestSuite|QuicksortExecutorNonWeaklyConsistentIteratorTestSuite|tnx.lab.executor}}
  
−
===implement <code>void parallelQuicksortKernel(ExecutorService executor, int[] array, int min, int maxExclusive, Queue<Future<?>> futures, int threshold)</code>===
+
==Performance==
 +
{{Performance|NucleobaseCountTiming|tnx.lab.executor}}
 +
{{Performance|QuicksortTiming|tnx.lab.executor}}
  
−
===Beyond 231===
 
−
While perhaps a bit more complicated, and beyond the scope of this class, [http://www.classes.cec.wustl.edu/~cse341/web/handouts/lecture07.pdf the partitioning step can also be done in parallel with scan].
 
  
 
=Rubric=
 
=Rubric=
Line 134: Line 221:
 
Total points: 100
 
Total points: 100
  
−
SimpleThreadFactory
+
SimpleThreadFactory subtotal: 5
−
* newThread (5)
+
* Correct newThread (5)
  
−
TAgeSum
+
TAgeSum subtotal: 10
−
* sumUpperLowerSplit (10)
+
* Correct sumUpperLowerSplit (10)
  
−
XNucleobaseCount
+
XNucleobaseCount subtotal: 40
−
* countRangeSequential (5)
+
* Correct count2WaySplit (10)
−
* count2WaySplit (10)
+
* Correct countNWaySplit (15)
−
* countNWaySplit (15)
+
* Correct countDivideAndConquer and countDivideAndConquerKernel (15)
−
* countDivideAndConquer and countDivideAndConquerKernel (15)
 
  
−
XQuicksort
+
XQuicksort subtotal: 35
−
* sequentialQuicksortKernel (5)
+
* Correct sequentialQuicksort and sequentialQuicksortKernel (10)
−
* parallelQuicksort and parallelQuicksortKernel (25)
+
* Correct parallelQuicksort and parallelQuicksortKernel (25)
  
 
Whole project:
 
Whole project:
Line 154: Line 240:
  
 
=Pledge, Acknowledgments, Citations=
 
=Pledge, Acknowledgments, Citations=
−
As always, fill out the Pledge, Acknowledgments, and Citations file: <code>hw3-pledge-acknowledgments-citations.txt</code>
+
{{Pledge|lab-threads-and-executors}}
 +
-->

Latest revision as of 19:40, 22 February 2022

This assignment has been updated: Thread and ExecutorService

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