Difference between revisions of "Threads and Executors"

From CSE231 Wiki
Jump to navigation Jump to search
 
(17 intermediate revisions by the same user 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=
Line 87: Line 89:
  
 
==Executors==
 
==Executors==
−
<youtube>8qh9LMhvNXI</youtube> <!-- box link: [https://wustl.box.com/s/2pqv6vsbirt6zi4304ycrh7jfgkb0dhi Executor submit and Future get]-->
+
<youtube>8qh9LMhvNXI</youtube>  
−
 
+
<youtube>tuAkLb99sLE</youtube>  
−
<youtube>tuAkLb99sLE</youtube> <!-- box link: [https://wustl.box.com/s/17q7xupx1tagdnnfg057teme4lbq4w6r Executor invokeAll]-->
 
  
 
===Code To Use===
 
===Code To Use===
Line 107: Line 108:
  
 
As always, the [[Reference_Page#Executors|wiki's reference page]] can be of help.
 
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 118: 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 [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()] from [[Nucleobase_Counting]]}}
+
{{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/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.
 
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 132: 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===
−
{{CodeToImplement|XQuicksort|sequentialQuicksort<br>sequentialQuicksortKernel<br>parallelQuicksort<br>parallelQuicksortKernel|tnx.lab.executor}}
 
−
 
 
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 153: Line 157:
  
 
{{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.}}
−
 
−
====The Core Questions====
 
−
*What are the tasks?
 
−
*What is the data?
 
−
*Is the data mutable?
 
−
*If so, how is it shared?
 
  
 
====Code To Use====
 
====Code To Use====
Line 167: Line 165:
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/quick/PivotLocation.html#getRightSidesLowerInclusive-- getRightSidesLowerInclusive()]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/quick/PivotLocation.html#getRightSidesLowerInclusive-- getRightSidesLowerInclusive()]
  
−
====sequential====
+
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====
−
The provided sequentialQuicksort method hopes to get you on the right track.
+
{{CodeToImplement|XParallelQuicksorter|kernel<br/>sortRange|tnx.lab.executor}}
−
<nowiki>public static void sequentialQuicksort(int[] array) {
 
−
sequentialQuicksortKernel(array, 0, array.length);
 
−
}</nowiki>
 
−
-->
 
  
−
{{Sequential|void sequentialQuicksort(int[] data, Partitioner partitioner)}}
+
{{Parallel|private void kernel(Queue<Future<?>> futures, T[] data, Comparator<T> comparator, int min, int maxExclusive)}}
  
−
{{Sequential|void sequentialQuicksortKernel(int[] data, int min, int maxExclusive, Partitioner partitioner)}}
+
{{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>. }}
  
−
====parallel====
+
{{Sequential|public void sortRange(T[] data, Comparator<T> comparator, int min, int maxExclusive)}}
−
{{Parallel|void parallelQuicksort(ExecutorService executor, int[] data, int threshold, Partitioner partitioner)}}
 
  
 
{{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 | 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]. }}
Line 187: Line 189:
 
{{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. }}
 
{{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. }}
  
−
{{Parallel|void parallelQuicksortKernel(ExecutorService executor, int[] data, int min, int maxExclusive, Queue<Future<?>> futures, int threshold, Partitioner partitioner)}}
+
{{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==
 
==(Optional) Parallel Partition Challenge==
Line 236: Line 240:
  
 
=Pledge, Acknowledgments, Citations=
 
=Pledge, Acknowledgments, Citations=
−
As always, fill out the Pledge, Acknowledgments, and Citations file: <code>lab5-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"