Difference between revisions of "Threads and Executors"
Jump to navigation
Jump to search
| (29 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| + | This assignment has been updated: [[Thread_and_Executor_Service_Assignment|Thread and ExecutorService]] | ||
| + | <!-- | ||
credit for this assignment: [[User:Finn|Finn Voichick]] and [[User:cosgroved|Dennis Cosgrove]] | credit for this assignment: [[User:Finn|Finn Voichick]] and [[User:cosgroved|Dennis Cosgrove]] | ||
=Motivation= | =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/ | + | 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]. |
Finish has particularly nice semantics: keeping track of and joining all of its descendant tasks. | Finish has particularly nice semantics: keeping track of and joining all of its descendant tasks. | ||
| Line 59: | Line 61: | ||
:[https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#start-- start] | :[https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#start-- start] | ||
:[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] | ||
| + | |||
| + | As always, the [[Reference_Page#Threads|wiki's reference page]] can be of help. | ||
===SimpleThreadFactory=== | ===SimpleThreadFactory=== | ||
| Line 85: | Line 89: | ||
==Executors== | ==Executors== | ||
| − | <youtube>8qh9LMhvNXI</youtube | + | <youtube>8qh9LMhvNXI</youtube> |
| − | + | <youtube>tuAkLb99sLE</youtube> | |
| − | <youtube>tuAkLb99sLE</youtube | ||
===Code To Use=== | ===Code To Use=== | ||
| Line 97: | Line 100: | ||
:[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/ | + | [http://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/count/assignment/NucleobaseCounting.html NucleobaseCounting] |
| − | : [http://www.cse.wustl.edu/~cosgroved/courses/cse231/ | + | : [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)] |
| + | |||
| + | [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(data, numSlices)</nowiki>]. | ||
| − | |||
| − | |||
| − | + | As always, the [[Reference_Page#Executors|wiki's reference page]] can be of help. | |
===Mistake To Avoid: Do NOT call shutdown=== | ===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=== | ||
| Line 113: | Line 116: | ||
{{CodeToImplement|XNucleobaseCount|countLowerUpperSplit<br>countNWaySplit<br>countDivideAndConquer<br>countDivideAndConquerKernel|tnx.lab.executor}} | {{CodeToImplement|XNucleobaseCount|countLowerUpperSplit<br>countNWaySplit<br>countDivideAndConquer<br>countDivideAndConquerKernel|tnx.lab.executor}} | ||
| − | {{Tip|Use [ | + | {{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]]}} |
====lower upper split==== | ====lower upper split==== | ||
{{Parallel|int countLowerUpperSplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase)}} | {{Parallel|int countLowerUpperSplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase)}} | ||
| + | |||
| + | 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==== | ====n-way split==== | ||
{{Parallel|int countNWaySplit(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int numTasks)}} | {{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/ | + | 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. |
| + | |||
| + | 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]. | ||
====divide-and-conquer==== | ====divide-and-conquer==== | ||
| Line 127: | Line 135: | ||
{{Parallel|int countDivideAndConquerKernel(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int min, int maxExclusive, int threshold)}} | {{Parallel|int countDivideAndConquerKernel(ExecutorService executor, byte[] chromosome, Nucleobase nucleobase, int min, int maxExclusive, int threshold)}} | ||
| + | |||
| + | 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. | 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. | ||
| Line 149: | Line 158: | ||
{{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.}} | {{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 | <code> | + | {{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>. | ||
| − | + | For details on how to complete this challenge, check out: [[Quicksort_Parallel_Partitioner]] | |
=Testing Your Solution= | =Testing Your Solution= | ||
| Line 201: | Line 207: | ||
{{TestSuite|NucleobaseExecutorTestSuite|tnx.lab.executor}} | {{TestSuite|NucleobaseExecutorTestSuite|tnx.lab.executor}} | ||
{{TestSuite|QuicksortExecutorTestSuite|tnx.lab.executor}} | {{TestSuite|QuicksortExecutorTestSuite|tnx.lab.executor}} | ||
| + | ====Less Time Consuming Suite==== | ||
| + | {{TestSuite|QuicksortExecutorNonWeaklyConsistentIteratorTestSuite|tnx.lab.executor}} | ||
==Performance== | ==Performance== | ||
| Line 232: | Line 240: | ||
=Pledge, Acknowledgments, Citations= | =Pledge, Acknowledgments, Citations= | ||
| − | + | {{Pledge|lab-threads-and-executors}} | |
| + | --> | ||
Latest revision as of 19:40, 22 February 2022
This assignment has been updated: Thread and ExecutorService
