Fork/Join - Divide & Conquer Flashcards
What is the concept of divide and conquer?
Split a porblem into smaller subproblems, solve the task recursively for each of these and combine the results to get the final result.
1st step is always to divide the problem into smaller subproblems
What is used to visualize the performance of a divide & conquer algorithm?
Task Graphs
What is the best framework for divide & conquer algorithms and what is the java library?
Fork/Join Framework and the library is java.util.concurrent
How do we use the library?
what do we extend?
what do we override?
What do we call?
- Instead of extending Thread, we extend RecursiveTask (with return value) or RecursiveAction (without return value)
- Instead of overriding run, we override compute
- Instead of calling start, we call fork
- Instead of a topmost call to run, we create a ForkJoinPool and call invoke
We want to return a result what do we need to extend in the Fork / Join Framework?
We need to extend RecursiveTask<>
<> in these we put the datatype to be returned
Implement the following example in code. See picture
See picture
When we need to return something we extend RecursiveTask<>
What data Type can be put into the < > symbols?
Only wrapped data types of primitives. For example Integer.
How do you find the minimum number of processors that are necessary to execute the task graph is the picture. And how many are there.
1) Critical path uses 1 processors
2) Go through the time intervals and figure out how many tasks are not being worked on at any given time
3) Use additional processors to do this but make sure you reuse the ones already added
What is the maximum overall speedup that can be achieved by parallelism on a task graph how do you calculate it?
Sp = T1 / Tp
Tp here is the minimum number of processors in this case. Find out what the minimum number is.
See the picture below. How do we fill the blanks when awaiting a number to be returned
What aren’t we allowed to forget before applying the forking to code?
The Base Case see picture
What does .fork() do?
In practice, this means that the framework first “forks”, recursively breaking the task into smaller independent subtasks until they are simple enough to be executed asynchronously.
What does .join() do?
After that, the “join” part begins, in which results of all subtasks are recursively joined into a single result, or in the case of a task which returns void, the program simply waits until every subtask is executed.
What is the basic structure of the fork/join problem? Use words
if (my portion of the work is small enough)
do the work directly
else
split my work into two pieces
invoke the two pieces and wait for the results
