Parallel Algorithm Design-Basic Terminologies
• Task Dependency Graph
- Consider the computations performed in processing the following query: MODEL="Civic" AND
YEAR="2001" AND
(COLOR="Green" OR COLOR="White")
Parallel Algorithm Design-Basic Terminologies
• Granularity
- The number and size of tasks into which a problem is decomposed determines the
granularity of the decomposition.
- A decomposition into a large number of small tasks is called fine-grained and
- A decomposition into a small number of large tasks is called coarse-grained.
Parallel Algorithm Design-Basic Terminologies
• Granularity
- Consider an example “Dense matrix-vector multiplication”
- Decomposition of dense matrix-vector multiplication into n tasks, where n is the
number of rows in the matrix. The portions of the matrix and the input and output
vectors accessed by Task 1 are highlighted. It is an example of fine-grained because
each of a large number of tasks performs a single dot-product.
Parallel Algorithm Design-Basic Terminologies
• Granularity
- Decomposition of dense matrix-vector multiplication into four tasks. The portions of
the matrix and the input and output vectors accessed by Task 1 are highlighted.
- It is an example of coarse-grained decomposition of the same problem into four tasks,
where each tasks computes n/4 of the entries of the output vector of length n.
Parallel Algorithm Design-Basic Terminologies
• Maximum Degree of concurrency.
- The maximum number of tasks that can be executed simultaneously in a parallel
program at any given time is known as its maximum degree of concurrency.
- In most cases, the maximum degree of concurrency is less than the total number of
tasks due to dependencies among the tasks.
- Rule of thumb: for task dependency graph that are trees, the maximum degree of
concurrency is always equal to the number of leaves in the tree
Parallel Algorithm Design-Basic Terminologies
• Maximum Degree of concurrency.
Parallel Algorithm Design-Basic Terminologies
• Degree of concurrency.
- For example, maximum degree of concurrency in the task-graph
Parallel Algorithm Design-Basic Terminologies
• Average Degree of concurrency
- A relatively better measure for the performance of a parallel program.
- A more useful indicator of a parallel program's performance is the average degree of
concurrency, which is the average number of tasks that can run concurrently over the
entire duration of execution of the program.
- Both the maximum and the average degrees of concurrency usually increase as the
granularity of tasks becomes smaller (finer).
Average degree of concurrency = total amount of work / critical path length
Parallel Algorithm Design-Basic Terminologies
• Average Degree of concurrency
- For example, the decomposition of matrix-
vector multiplication shown in Figure has a
fairly small granularity and a large degree of
concurrency.
-The decomposition for the same problem
shown in Figure has a larger granularity and a
smaller degree of concurrency.
Parallel Algorithm Design-Basic Terminologies
• Average Degree of concurrency
- The degree of concurrency also depends on the shape of the task-dependency graph
and the same granularity, in general, does not guarantee the same degree of
concurrency.
- For example, consider the two task graphs below. The number inside each node
represents the amount of work required to complete the task corresponding to that
node.
Parallel Algorithm Design-Basic Terminologies
• Average Degree of concurrency
- The average degree of concurrency of the task graph in Figure (a) is 2.33 and that of
the task graph in Figure (b) is 1.88, although both task-dependency graphs are based
on the same decomposition.
Parallel Algorithm Design-Basic Terminologies
• Critical Path & Critical Path Length
- A feature of a task-dependency graph that determines the average degree
of concurrency for a given granularity is its critical path. (Longest path)
- In a task-dependency graph, let us refer to the nodes with no incoming
edges by start nodes and the nodes with no outgoing edges by finish
nodes.
Parallel Algorithm Design-Basic Terminologies
• Critical Path & Critical Path Length
- The sum of the weights of nodes along this path is known as the critical
path length, where the weight of a node is the size or the amount of work
associated with the corresponding task.
- The ratio of the total amount of work to the critical-path length is the
average degree of concurrency.
- Therefore, a shorter critical path favors a higher degree of concurrency.
Parallel Algorithm Design-Basic Terminologies
• Critical Path & Critical Path Length
- For example, the critical path length is 27 in the task-dependency graph
shown in Figure (a) and is 34 in the task-dependency graph shown in
Figure (B)
Parallel Algorithm Design-Basic Terminologies
• Critical Path & Critical Path Length
- Since the total amount of work required to solve the problems using the
two decompositions is 63 and 64, respectively, the average degree of
concurrency of the two task-dependency graphs is 2.33 (63/27) and 1.88
(64/34), respectively
Parallel Algorithm Design-Basic Terminologies
• Processes and Mapping
Parallel Algorithm Design-Basic Terminologies
• Processes Vs Processor
- Processes are logical computing agents that perform tasks.
- Processors are the hardware units that physically perform computations
- Treating processes and processors separately is also useful when designing parallel
programs for hardware that supports multiple programming paradigms.
Parallel Algorithm Design-Decomposition Techniques
• To solve a problem in parallel is to split the computations to be performed
into a set of tasks for concurrent execution defined by the task-dependency
graph.
• These techniques are broadly classified as
- Recursive decomposition
- Data-decomposition,
- Exploratory decomposition, and
- Speculative decomposition.
Parallel Algorithm Design-Decomposition Techniques
• The recursive- and data decomposition techniques are relatively general
purpose as they can be used to decompose a wide variety of problems.
• On the other hand, speculative- and exploratory-decomposition techniques
are more of a special purpose nature because they apply to specific classes of
problems.
Parallel Algorithm Design-Decomposition Techniques
• Recursive-decomposition
- Recursive decomposition is a method for inducing concurrency in problems that can
be solved using the divide-and-conquer strategy.
- In this technique, problem is solved by first dividing it into a set of independent
subproblems.
- Each one of these subproblems is solved by recursively applying a similar division
into smaller subproblems followed by a combination of their results.
- The divide-and-conquer strategy results in natural concurrency, as different
subproblems can be solved concurrently.
Parallel Algorithm Design-Decomposition Techniques
• Recursive-decomposition (pivot Element)
-.
Parallel Algorithm Design-Decomposition Techniques
• Recursive-decomposition.
- A serial program for finding the minimum in an array of numbers A
of length n.
- It is easy to see that this serial algorithm exhibits no concurrency.
Parallel Algorithm Design-Decomposition Techniques
• Recursive-decomposition.
- The task-dependency graph for finding the minimum number in the sequence {4, 9,
1, 7, 8, 11, 2, 12}. Each node in the tree represents the task of finding the minimum
of a pair of numbers.
- It is easy to see that this serial algorithm exhibits no concurrency.
Parallel Algorithm Design-Decomposition Techniques
• Recursive-decomposition.
- A recursive program for finding the minimum in an array of numbers A of length n.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition.
- Data decomposition is a powerful and commonly used method for deriving
concurrency in algorithms that operate on large data structures.
- In this method, the decomposition of computations is done in two steps.
- In the first step, the data on which the computations are performed is partitioned,
and in the second step, this data partitioning is used to induce a partitioning of the
computations into tasks.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition.
- The partitioning of data can be performed in many possible ways
Partitioning Output Data
Partitioning Input Data
Partitioning both Input and Output Data
Partitioning Intermediate Data
The Owner-Computes Rule
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Output Data
- In many computations, each element of the output can be computed independently of
others as a function of the input.
- In such computations, a partitioning of the output data automatically induces a
decomposition of the problems into tasks, where each task is assigned the work of
computing a portion of the output.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Output Data
- In Figure (a) Partitioning of input and output matrices into 2 x 2 submatrices.
- In Figure (b) A decomposition of matrix multiplication into four tasks based on the
partitioning of the matrices in (a).
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Output Data
- In Two examples of decomposition of matrix multiplication into eight tasks
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Output Data
- Example # 2 : Computing frequencies of item sets in a transaction database
The database shown in Figure (1)
consists of 10 transactions, and we
are interested in computing the
frequency of the eight itemsets shown
in the second column in Figure.
The actual frequencies of these
itemsets in the database, which are
the output of the frequency-computing
program, are shown in the third
column.
For instance, itemset {D, K} appears
twice, once in the second and once in
the ninth transaction
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Output Data
- shows how the computation of frequencies of the itemsets can be
decomposed into two tasks by partitioning the output into two parts and
having each task compute its half of the frequencies.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Input Data
- Partitioning of output data can be performed only if each output can be naturally
computed as a function of the input.
- In many algorithms, it is not possible or desirable to partition the output data.
- For example, while finding the minimum, maximum, or the sum of a set of numbers,
the output is a single unknown value. In a sorting algorithm, the individual elements of
the output cannot be efficiently determined in isolation.
- In such cases, it is sometimes possible to partition the input data, and then use this
partitioning to induce concurrency.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Input Data
- In such cases, it is sometimes possible to partition the input data, and then use this
partitioning to induce concurrency.
- A task is created for each partition of the input data and this task performs as much
computation as possible using these local data.
- Note that the solutions to tasks induced by input partitions may not directly solve the
original problem. In such cases, a follow-up computation is needed to combine the
results. For example, while finding the sum of a sequence of N numbers using p
processes (N > p), we can partition the input into p subsets of nearly equal sizes. Each
task then computes the sum of the numbers in one of the subsets. Finally, the p partial
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Input Data (Example)
- The problem of computing the frequency of a set of itemsets in a transaction database
described earlier, can also be decomposed based on a partitioning of input data.
- Figure (a) shows a decomposition based on a partitioning of the input set of
transactions.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Input and output Data
- Partition the output data, partitioning of input data can offer additional concurrency.
- For example, consider the 4-way decomposition shown in Figure (b) for computing
itemset frequencies. Here, both the transaction set and the frequencies are divided
into two parts and a different one of the four possible combinations is assigned to each
of the four tasks. Each task then computes a local set of frequencies.
- Finally, the outputs of Tasks 1 and 3 are added together, as are the outputs of Tasks 2
and 4.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Input and output Data (Example)
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Intermediate Data
- Algorithms are often structured as multi-stage computations such that the output of
one stage is the input to the subsequent stage.
- A decomposition of such an algorithm can be derived by partitioning the input or the
output data of an intermediate stage of the algorithm.
- Partitioning intermediate data can sometimes lead to higher concurrency than
partitioning input or output data.
- Often, the intermediate data are not generated explicitly in the serial algorithm for
solving the problem and some restructuring of the original algorithm may be required
to use intermediate data partitioning to induce a decomposition.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Intermediate Data (Example)
- Multiplication of matrices A and
B with partitioning of the three-
dimensional intermediate
matrix D.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Intermediate Data (Example)
-A decomposition of matrix
multiplication based on
partitioning the intermediate
three-dimensional matrix.
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - Partitioning Intermediate Data (Example)
- The task-dependency graph of
the decomposition shown
Parallel Algorithm Design-Decomposition Techniques
• Data-decomposition - The Owner-Computes Rule –
- A decomposition based on partitioning output or input data is also widely referred to
as the owner-computes rule.
- The idea behind this rule is that each partition performs all the computations
involving data that it owns. Depending on the nature of the data or the type of data-
partitioning, the owner-computes rule may mean different things.
- For instance, when we assign partitions of the input data to tasks, then the owner-
computes rule means that a task performs all the computations that can be done
using these data.
- On the other hand, if we partition the output data, then the owner-computes rule
means that a task computes all the data in the partition assigned to it
Parallel Algorithm Design-Decomposition Techniques
• Exploratory Decomposition
- used to decompose problems whose underlying computations correspond to a search
of a space for solutions.
- In exploratory decomposition, we partition the search space into smaller parts, and
search each one of these parts concurrently, until the desired solutions are found.
Parallel Algorithm Design-Decomposition Techniques
• Exploratory Decomposition
- A 15-puzzle problem instance showing the initial configuration (a), the final
configuration (d), and a sequence of moves leading from the initial to the final
configuration.
Parallel Algorithm Design-Decomposition Techniques
• Exploratory Decomposition
- The 15-puzzle is typically solved using tree-search techniques.
- One method for solving this problem in parallel is as follows.
- First, a few levels of configurations starting from the initial configuration are generated
serially until the search tree has a sufficient number of leaf nodes (i.e., configurations
of the 15-puzzle).
- Now each node is assigned to a task to explore further until at least one of them finds a
solution.
- As soon as one of the concurrent tasks finds a solution it can inform the others to
terminate their searches.
Parallel Algorithm Design-Decomposition Techniques
• Exploratory Decomposition
-
- The states generated by an instance of
Task-2
the 15-puzzle problem.
-Task-1
Parallel Algorithm Design-Decomposition Techniques
• Exploratory Decomposition
- The states generated by an instance of
the 15-puzzle problem.
-
Task-4
-
Task-3
Parallel Algorithm Design-Decomposition Techniques
• Speculative Decomposition
- Used when a program may take one of many possible computationally significant
branches depending on the output of other computations that precede it.
- In this situation, while one task is performing the computation whose output is used in
deciding the next computation, other tasks can concurrently start the computations of
the next stage.
Parallel Algorithm Design-Decomposition Techniques
• Speculative Decomposition
- This scenario is similar to evaluating one or more of the branches of a switch statement
in C in parallel before the input for the switch is available.
- While one task is performing the computation that will eventually resolve the switch,
other tasks could pick up the multiple branches of the switch in parallel.
- When the input for the switch has finally been computed, the computation
corresponding to the correct branch would be used while that corresponding to the
other branches would be discarded.
- The parallel run time is smaller than the serial run time by the amount of time required
to evaluate the condition on which the next task depends because this time is utilized
Parallel Algorithm Design-Decomposition Techniques
• Speculative Decomposition
- However, this parallel formulation of a switch guarantees at least some wasteful
- computation.
- In order to minimize the wasted computation, a slightly different formulation of
speculative decomposition could be used, especially in situations where one of the
outcomes of the switch is more likely than the others.
- In this case, only the most promising branch is taken up a task in parallel with the
preceding computation. In case the outcome of the switch is different from what was
anticipated, the computation is rolled back and the correct branch of the switch is
taken.
Parallel Algorithm Design-Decomposition Techniques
• Hybrid Decomposition
- Use multiple decomposition techniques together
- For Example, While finding the minimum of a large set of n numbers, a purely
recursive decomposition may result in far more tasks than the number of processes, P,
available.
- An efficient decomposition would partition the input into P roughly equal parts and
have each task compute the minimum of the sequence assigned to it.
- The final result can be obtained by finding the minimum of the P intermediate results
by using the recursive decomposition shown
Parallel Algorithm Design-Decomposition Techniques
• Hybrid Decomposition
- Hybrid decomposition for finding the minimum of an array of size 16 using four tasks
(3, 7, 2,9,11,4,5,8,7,10,6,13,1,19,3,9)