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
The worker threads continuously check the _ for available tasks. Once they receive a task, they follow the instructions effectively completing their assigned part of the overall job.
queue
The Fork/Join Framework uses a cool trick called _.
work-stealing
Here’s the idea: imagine a worker thread finishes its task. They can peek over at another thread and see if there is any extra work to help out with. This keeps everyone working and makes sure no time is wasted.
Adds an item to the back of the queue.
Enqueue
Removes an item from the front of the queue.
Dequeue
Fork-join Real-life Examples
- WEATHER FORECASTING: Large-scale weather simulations can be divided into smaller regions, each of which can be simulated independently.
- BIG DATA PROCESSING: Large datasets can be divided into smaller chunks and processed in parallel using techniques like MapReduce.
A _ is a path that is followed during a program’s execution.
thread
The majority of programs written nowadays run as a _ thread.
single
For example, a program is not capable of reading keystrokes while making drawings. These tasks cannot be executed by the program at the same time. This problem can be solved through multitasking so that two or more tasks can be executed simultaneously.
An example of a multithreaded program that we are all familiar with is a word processor. While you are typing, multiple threads are used to
* display your document,
* asynchronously check the spelling
* grammar of your document,
* generate a PDF version of the document.
When working on a spreadsheet, a user enters data into a cell, and the following may happen:
* column widths may be adjusted
* repeating cell elements may be replicated;
* spreadsheets may be saved multiple times as the file is further developed.
These are all happening concurrently, with independent threads performing these tasks internally.
Noted
It is the smallest unit of processing that can be performed in an OS.
Thread
Thread is the smallest unit of processing that can be performed in an _.
Operating System (OS)
