30 Questions
What is the purpose of speculative decomposition?
To handle programs that may take different branches depending on preceding computations.
How does speculative decomposition relate to a switch statement in C?
It is similar to evaluating branches of a switch statement in parallel before the input for the switch is available.
What is the potential advantage of speculative decomposition in terms of speedup?
It can result in super- or sub-linear speedups due to changing the amount of work done by parallel formulation.
When is speculative decomposition used?
When a program may take different computationally significant branches depending on preceding computations.
How does speculative decomposition enable parallelism in computation?
By allowing tasks to start computing the next stage while one task resolves the current computation.
How is speculative decomposition beneficial in terms of task efficiency?
It enables tasks to work on multiple branches of computation in parallel.
What usually results in dependencies in a task-dependency graph?
The fact that the output of one task is the input for another
What is represented by the nodes in a task-interaction graph?
Tasks
How can the nodes and edges of a task-interaction graph be assigned weights?
Proportional to the amount of computation a task performs and the amount of interaction that occurs along an edge
What is the typical nature of edges in a task interaction graph?
Undirected
How can directed edges be used in a task-interaction graph?
To indicate the direction of flow of data if it is unidirectional
What is the relationship between the edge-sets of a task-interaction graph and a task-dependency graph?
The edge-set of a task-interaction graph is usually a superset of the edge-set of the task-dependency graph
How can the problem of computing the frequency of a set of item sets in a transaction database be decomposed?
Based on a partitioning of input data
What does each task do in the 4-way decomposition for computing itemset frequencies?
Each task computes a local set of frequencies
How are the p partial results combined to yield the final result in the sum of a sequence of N numbers using p processes?
The p partial results are added up
What are the outputs of Tasks 1 and 3 added together for in the 4-way decomposition for computing itemset frequencies?
The outputs of Tasks 1 and 3 are added together
What does each task in the 4-way decomposition for computing itemset frequencies receive?
Each task receives a different combination of the transaction set and frequencies
What is the purpose of partitioning the input data into subsets of nearly equal sizes in the sum of a sequence of N numbers using p processes?
To allow each task to compute the sum of numbers in one of the subsets
What is the owner-computes rule?
The owner-computes rule states that each partition performs all the computations involving data that it owns.
How can partitioning intermediate data lead to higher concurrency?
Partitioning intermediate data can lead to higher concurrency by allowing tasks to work on different parts of the data simultaneously.
When is exploratory decomposition used?
Exploratory decomposition is used to decompose problems whose underlying computations correspond to a search of a space for solutions.
Give an example of a problem where exploratory decomposition can be applied.
A 15 puzzle (a tile puzzle) is a simple application of exploratory decomposition.
What restructuring may be required when using intermediate data partitioning in algorithms?
Some restructuring of the original algorithm may be required to use intermediate data partitioning to induce a decomposition.
How does the owner-computes rule differ based on partitioning input data and partitioning output data?
When partitioning input data, the owner-computes rule means that a task performs all the computations that can be done using the data assigned to it. When partitioning output data, the rule means that a task computes all the data in the partition assigned to it.
What is the main difference between speculative decomposition and traditional decomposition techniques?
Speculative decomposition focuses on executing the most promising branch in parallel, while traditional decomposition evaluates all branches and discards the unnecessary ones.
Why is a purely recursive decomposition not efficient in quicksort?
Purely recursive decomposition limits concurrency in quicksort, as it may result in more tasks than the available processes.
How does hybrid decomposition improve the efficiency of algorithms?
Hybrid decomposition combines different decomposition techniques for different algorithm stages, optimizing concurrency and minimizing wasted computation.
Explain the concept of rolling back computation in speculative decomposition.
Rolling back computation in speculative decomposition involves reverting to the correct branch of the switch when the anticipated outcome does not match the actual result.
Why is speculative decomposition particularly useful when one outcome of a switch is more likely than others?
Speculative decomposition is beneficial in this scenario as it focuses on the most probable branch, reducing unnecessary computation.
How does the parallel run time differ from the serial run time in the context of speculative decomposition?
The parallel run time is shorter by the time taken to evaluate the condition for the next task, which is utilized for useful computation in parallel.
Test your knowledge on exploratory decomposition, including examples and techniques like speculative decomposition. Explore how decomposition techniques can impact parallel formulation work and speedups.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
