Fork-Join Parallelism with Data Structures Flashcards
It utilizes multiple cores inside the computer to tackle tasks simultaneously, making processes much quicker.
Parallel Processing
Parallel processing utilizes multiple _ inside the computer to tackle tasks simultaneously, making processes much quicker.
cores
_ is a programming model that allows tasks to be split into subtasks (forking) and later combined (joining) after execution.
Fork-Join Parallelism
The _ splits the task into smaller subtasks and these tasks are executed concurrently.
Fork
After the execution of the subtasks, the task may _ all the results into one result.
join
After the _, one flow turns into two separate flows.
fork
It’s particularly useful in scenarios where a problem can be broken down into subproblems that can be solved independently.
The fork-join framework employs a _ strategy, making it ideal for parallel processing.
divide and conquer
Divide-and-Conquer Algorithm
void DivideAndConquer ( Problem P) {
—if( P is base case ) {
——Solve P;
—} else {
——Divide P into K subproblems;
——Fork to conquer each subproblem in parallel;
——Join;
——Combine subsolutions into final solution;
—}
}
Noted
The function DivideAndConquer takes problem P as input
If the problem P is a _ , the function directly solves it and returns the solution.
base case
A small, easily solvable instance.
Base Case
If the problem is not a base case, it is _ into K subproblems.
divided
These subproblems are then solved in parallel using the Fork operation, creating new tasks for each subproblem.
The _ operation waits for all subproblems to finish.
Join
Finally, the solutions of the subproblems are combined to form the solution to the original problem.
The fork/join framework supports a style of parallel programming that solves problems by “Divide and conquer”, in the following manner as shown below:
1. Splitting a task into sub-tasks.
2. Solving sub-tasks in parallel
* Sub-tasks can run in parallel on different cores.
* Sub-tasks can also run concurrently in different threads on a single core.
3. Waiting for them to complete
* join() waits for a sub-task to finish
4. Merging the results.
* A task uses calls to join() to merge the sub-task results together.
Noted
For good speedup, most of the work must occur deep in the _, where parallelism is _.
nesting, high
Three-level, two-way nesting = eight parallel flows at the innermost level
FORK-JOIN CREWS
Three (3) key components to achieve parallel processing:
1.Fork-Join Pool: The Conductor of Threads
2. ForkJoinTasks
3. Worker Threads
It manages a pool of worker threads, and assigns them tasks from a queue, just like the pool keeps workers busy.
Fork-Join Pool: The Conductor of Threads
A thread pool that manages the execution of ForkJoin Tasks.
ForkJoinPool
When a task is submitted to the pool, the forkjoinpool decides whether to execute it directly or split it into subtasks, distributing them among available _.
worker threads
An abstract class that defines a task that runs within a ForkJoinPool.
ForkJoinTask<v>
(ForkJoinTasks)</v>
There are two (2) main types of tasks:
- RecursiveTask: ForkJoinTask’s subclass for tasks that return values
- RecursiveAction: ForkJoinTask’s subclass for tasks that don’t return values.
ForkJoinTask’s subclass for tasks that return values.
RecursiveTask
Similar to RecursiveAction, but a RecursiveTask returns a result whose type is specified by the type parameter v.
ForkJoinTask’s subclass for tasks that don’t return values.
RecursiveAction
_ means that the task can be split into subtasks of itself by a divide-and-conquer strategy.
Recursive
These are the workhorses that execute the tasks.
Worker Threads
