Principles of Parallel
Algorithm Design
Chapter # 3
Ananth Grama
Preliminaries: Decomposition,
Tasks, and
Dependency Graphs
The first step in developing a parallel algorithm is
to decompose the problem into tasks that can be
executed concurrently
A given problem may be docomposed into tasks in
many different ways.
Tasks may be of same, different, or even
interminate sizes.
A decomposition can be illustrated in the form of
a directed graph with nodes corresponding to
tasks and edges indicating that the result of one
task is required for processing the next. Such a
graph is called a task dependency graph.
Sandwich Making Example
Discussed in Class
Example: Multiplying a
Dense Matrix with a
Vector
Computation of each element of output vector y is independent of other
elements. Based on this, a dense matrix-vector product can be decomposed
into n tasks. The figure highlights the portion of the matrix and vector accessed
by Task 1.
Observations: While tasks share data (namely, the vector b ), they do
not have any control dependencies - i.e., no task needs to wait for the
(partial) completion of any other. All tasks are of the same size in terms
of number of operations. Is this the maximum number of tasks we could
decompose this problem into?
Task Dependency graph of
a Dense Matrix
Discussed in class
Example: Database Query
Processing
Consider the execution of the query:
MODEL = ``CIVIC'' AND YEAR = 2001 AND
(COLOR = ``GREEN'' OR COLOR = ``WHITE)
on the following database:
ID# Model Year Color Dealer Price
4523 Civic 2002 Blue MN $18,000
3476 Corolla 1999 White IL $15,000
7623 Camry 2001 Green NY $21,000
9834 Prius 2001 Green CA $18,000
6734 Civic 2001 White OR $17,000
5342 Altima 2001 Green FL $19,000
3845 Maxima 2001 Blue NY $22,000
8354 Accord 2000 Green VT $18,000
4395 Civic 2001 Red CA $17,000
7352 Civic 2002 Red WA $18,000
Example: Database Query
Processing
The execution of the query can be divided into subtasks in various
ways. Each task can be thought of as generating an intermediate
table of entries that satisfy a particular clause.
Decomposing the given query into a number of tasks. Edges in this
graph denote that the output of one task is needed to accomplish
the next.
Example: Database Query
Processing
Note that the same problem can be decomposed into subtasks in
other
ways as well.
An alternate decomposition of the given problem into subtasks, along
with their data dependencies. Different task decompositions may lead to
significant differences with respect to their eventual parallel
performance.
Granularity of Task
Decompositions
The number of tasks into which a problem is decomposed
determines its granularity.
Decomposition into a large number of tasks results in fine-grained
decomposition and that into a small number of tasks results in a
coarse grained decomposition.
A coarse grained counterpart to the dense matrix-vector product
example. Each task in this example corresponds to the computation of three
elements of the result vector.
Degree of Concurrency
The number of tasks that can be executed in parallel is
the degree of concurrency of a decomposition.
Since the number of tasks that can be executed in parallel
may change over program execution, the maximum
degree of concurrency is the maximum number of such
tasks at any point during execution. What is the maximum
degree of concurrency of the database query examples?
The average degree of concurrency is the average
number of tasks that can be processed in parallel over the
execution of the program. Assuming that each tasks in the
database example takes identical processing time, what is
the average degree of concurrency in each
decomposition?
The degree of concurrency increases as the
decomposition becomes finer in granularity and vice
versa.
Critical Path Length
A directed path in the task dependency graph
represents a sequence of tasks that must be
processed one after the other.
The longest such path determines the shortest
time in which the program can be executed in
parallel.
The length of the longest path in a task
dependency graph is called the critical path
length.
Critical Path Length
Consider the task dependency graphs of the two database query
decompositions:
What are the critical path lengths for the two task dependency graphs?
If each task takes 10 time units, what is the shortest parallel execution time
for each decomposition? How many processors are needed in each case to
achieve this minimum parallel execution time? What is the maximum
degree of concurrency?
Critical Path Length
(Example from Book)
Limits on Parallel
Performance
It would appear that the parallel time can be
made arbitrarily small by making the
decomposition finer in granularity.
There is an inherent bound on how fine the
granularity of a computation can be. For example,
in the case of multiplying a dense matrix with a
vector, there can be no more than (n2) concurrent
tasks.
Concurrent tasks may also have to exchange data
with other tasks. This results in communication
overhead. The tradeoff between the granularity of
a decomposition and associated overheads often
determines performance bounds.
Limits on Parallel
Performance
It would appear that the parallel time can be
made arbitrarily small by making the
decomposition finer in granularity.
There is an inherent bound on how fine the
granularity of a computation can be. For example,
in the case of multiplying a dense matrix with a
vector, there can be no more than (n2) concurrent
tasks.
Concurrent tasks may also have to exchange data
with other tasks. This results in communication
overhead. The tradeoff between the granularity of
a decomposition and associated overheads often
determines performance bounds.
Task Interaction Graphs
Subtasks generally exchange data with others in a
decomposition. For example, even in the trivial
decomposition of the dense matrix-vector
product, if the vector is not replicated across all
tasks, they will have to communicate elements of
the vector.
The graph of tasks (nodes) and their
interactions/data exchange (edges) is referred to
as a task interaction graph.
Note that task interaction graphs represent data
dependencies, whereas task dependency graphs
represent control dependencies.
Task Interaction Graphs :
Example
Examples of matrix with vector.
Task Interaction Graphs: An
Example
Consider the problem of multiplying a sparse
matrix A with a vector b. The following observations
can be made:
• As before, the computation of each element of the result vector can
be viewed as an independent task.
• Unlike a dense matrix-vector product though, only non-zero
elements of matrix A participate in the computation.
• If, for memory optimality, we also partition b across tasks, then one
can see that the task interaction graph of the computation is
identical to the graph of the matrix A (the graph for which A
represents the adjacency structure).
Task Interaction Graphs,
Granularity, and
Communication
In general, if the granularity of a
decomposition is finer, the associated overhead
(as a ratio of useful work assocaited with a task)
increases.
Example: Consider the sparse matrix-vector
product example from previous foil. Assume that
each node takes unit time to process and each
interaction (edge) causes an overhead of a unit
time.
Viewing node 0 as an independent task
involves a useful computation of one time unit
and overhead (communication) of three time
units.
Now, if we consider nodes 0, 4, and 5 as
one task, then the task has useful computation
totaling to three time units and communication
corresponding to four time units (four edges).
Processes and Mapping
In general, the number of tasks in a decomposition
exceeds the number of processing elements available.
For this reason, a parallel algorithm must also provide a
mapping of tasks to processes.
Note: We refer to the mapping as being from tasks to
processes, as opposed to processors. This is because
typical programming APIs, as we shall see, do not allow
easy binding of tasks to physical processors. Rather, we
aggregate tasks into processes and rely on the system
to map these processes to physical processors. We use
processes, not in the UNIX sense of a process, rather,
simply as a collection of tasks and associated data.
Processes and Mapping
Appropriate mapping of tasks to processes is
critical to the parallel performance of an
algorithm.
Mappings are determined by both the task
dependency and task interaction graphs.
Task dependency graphs can be used to ensure
that work is equally spread across all processes at
any point (minimum idling and optimal load
balance).
Task interaction graphs can be used to make sure
that processes need minimum interaction with
other processes (minimum communication).
Processes and Mapping
An appropriate mapping must minimize parallel
execution time by:
Mapping independent tasks to different processes.
Assigning tasks on critical path to processes as
soon as they become available.
Minimizing interaction between processes by
mapping tasks with dense interactions to the
same process.
Note: These criteria often conflict eith each other.
For example, a decomposition into one task (or no
decomposition at all) minimizes interaction but
does not result in a speedup at all! Can you think
of other such conflicting cases?
Processes and Mapping: Example
Mapping tasks in the database query decomposition to
processes. These mappings were arrived at by viewing the
dependency graph in terms of levels (no two nodes in a level have
dependencies). Tasks within a single level are then assigned to
different processes.
Decomposition Techniques
So how does one decompose a task into various
subtasks?
While there is no single recipe that works for all
problems, we present a set of commonly used
techniques that apply to broad classes of
problems. These include:
• recursive decomposition
• data decomposition
• exploratory decomposition
• speculative decomposition
Recursive Decomposition
Generally suited to problems that are solved using
the divide-and-conquer strategy.
A given problem is first decomposed into a set of
sub-problems.
These sub-problems are recursively decomposed
further until a desired granularity is reached.
Recursive Decomposition:
Example
A classic example of a divide-and-conquer algorithm on which we
can apply recursive decomposition is Quicksort.
In this example, once the list has been partitioned around the
pivot, each sublist can be processed concurrently (i.e., each sublist
represents an independent subtask). This can be repeated
recursively.
Recursive Decomposition:
Example
The problem of finding the minimum number in a given list (or
indeed any other associative operation such as sum, AND, etc.)
can be fashioned as a divide-and-conquer algorithm. The following
algorithm illustrates this.
We first start with a simple serial loop for computing the
minimum entry in a given list:
1. procedure SERIAL_MIN (A, n)
2. begin
3. min = A[0];
4. for i := 1 to n − 1 do
5. if (A[i] < min) min := A[i];
6. endfor;
7. return min;
8. end SERIAL_MIN
Recursive Decomposition:
Example
We can rewrite the loop as follows:
1. procedure RECURSIVE_MIN (A, n)
2. begin
3. if ( n = 1 ) then
4. min := A [0] ;
5. else
6. lmin := RECURSIVE_MIN ( A, n/2 );
7. rmin := RECURSIVE_MIN ( &(A[n/2]), n - n/2 );
8. if (lmin < rmin) then
9. min := lmin;
10. else
11. min := rmin;
12. endelse;
13. endelse;
14. return min;
15. end RECURSIVE_MIN
Recursive Decomposition:
Example
The code in the previous foil can be decomposed
naturally using a recursive decomposition strategy.
We illustrate this with the following example of
finding the minimum number in the set {4, 9, 1, 7,
8, 11, 2, 12}. The task dependency graph
associated with this computation is as follows:
Data Decomposition
Identify the data on which computations are
performed.
Partition this data across various tasks.
This partitioning induces a decomposition of the
problem.
Data can be partitioned in various ways - this
critically impacts performance of a parallel
algorithm.
Data Decomposition:
Output Data
Decomposition
Often, each element of the output can be
computed independently of others (but simply as
a function of the input).
A partition of the output across tasks decomposes
the problem naturally.
Output Data Decomposition:
Example
Consider the problem of multiplying two n x n matrices A and B to
yield matrix C. The output matrix C can be partitioned into four
tasks as follows:
Task 1:
Task 2:
Task 3:
Task 4:
Output Data Decomposition:
Example
A partitioning of output data does not result in a unique
decomposition into tasks. For example, for the same problem as in
previus foil, with identical output data distribution, we can derive
the following two (other) decompositions:
Decomposition I Decomposition II
Task 1: C1,1 = A1,1 B1,1 Task 1: C1,1 = A1,1 B1,1
Task 2: C1,1 = C1,1 + A1,2 B2,1 Task 2: C1,1 = C1,1 + A1,2 B2,1
Task 3: C1,2 = A1,1 B1,2 Task 3: C1,2 = A1,2 B2,2
Task 4: C1,2 = C1,2 + A1,2 B2,2 Task 4: C1,2 = C1,2 + A1,1 B1,2
Task 5: C2,1 = A2,1 B1,1 Task 5: C2,1 = A2,2 B2,1
Task 6: C2,1 = C2,1 + A2,2 B2,1 Task 6: C2,1 = C2,1 + A2,1 B1,1
Task 7: C2,2 = A2,1 B1,2 Task 7: C2,2 = A2,1 B1,2
Task 8: C2,2 = C2,2 + A2,2 B2,2 Task 8: C2,2 = C2,2 + A2,2 B2,2
Output Data Decomposition:
Example
Consider the problem of counting the instances of given itemsets
in a database of transactions. In this case, the output (itemset
frequencies) can be partitioned across tasks.
Output Data
Decomposition: Example
From the previous example, the following
observations can be made:
If the database of transactions is replicated across
the processes, each task can be independently
accomplished with no communication.
If the database is partitioned across processes as
well (for reasons of memory utilization), each task
first computes partial counts. These counts are
then aggregated at the appropriate task.
Input Data Partitioning
Generally applicable if each output can be
naturally computed as a function of the input.
In many cases, this is the only natural
decomposition because the output is not clearly
known a-priori (e.g., the problem of finding the
minimum in a list, sorting a given list, etc.).
A task is associated with each input data partition.
The task performs as much of the computation
with its part of the data. Subsequent processing
combines these partial results.
Input Data Partitioning: Example
In the database counting example, the input (i.e., the transaction
set) can be partitioned. This induces a task decomposition in
which each task generates partial counts for all itemsets. These
are combined subsequently for aggregate counts.
Partitioning Input and Output Data
Often input and output data decomposition can be combined for a
higher degree of concurrency. For the itemset counting example,
the transaction set (input) and itemset counts (output) can both be
decomposed as follows:
Intermediate Data
Partitioning
Computation can often be viewed as a sequence
of transformation from the input to the output
data.
In these cases, it is often beneficial to use one of
the intermediate stages as a basis for
decomposition.
Intermediate Data Partitioning:
Example
Let us revisit the example of dense matrix multiplication. We first
show how we can visualize this computation in terms of
intermediate matrices D.
Intermediate Data Partitioning:
Example
A decomposition of intermediate data structure leads to the
following decomposition into 8 + 4 tasks:
Stage I
Stage II
Task 01: D1,1,1= A1,1 B1,1 Task 02: D2,1,1= A1,2 B2,1
Task 03: D1,1,2= A1,1 B1,2 Task 04: D2,1,2= A1,2 B2,2
Task 05: D1,2,1= A2,1 B1,1 Task 06: D2,2,1= A2,2 B2,1
Task 07: D1,2,2= A2,1 B1,2 Task 08: D2,2,2= A2,2 B2,2
Task 09: C1,1 = D1,1,1 + D2,1,1 Task 10: C1,2 = D1,1,2 + D2,1,2
Task 11: C2,1 = D1,2,1 + D2,2,1 Task 12: C2,,2 = D1,2,2 + D2,2,2
Intermediate Data Partitioning:
Example
The task dependency graph for the decomposition (shown in
previous foil) into 12 tasks is as follows:
The Owner Computes Rule
The Owner Computes Rule generally states that
the process assined a particular data item is
responsible for all computation associated with it.
In the case of input data decomposition, the
owner computes rule imples that all computations
that use the input data are performed by the
process.
In the case of output data decomposition, the
owner computes rule implies that the output is
computed by the process to which the output data
is assigned.
Data Decomposition:
Example 2 -Frequent Itemset
Example 2 : discussion
Step 1: Data in the database
Step 2: Calculate the support/frequency of all
items
Step 3: Discard the items with minimum support
less than 2
Step 4: Combine two items
Step 5: Calculate the support/frequency of all
items
Step 6: Discard the items with minimum support
less than 2
Step 6.5: Combine three items and
calculate their support.
Step 7: Discard the items with minimum support
less than 2
Result:
Exploratory
Decomposition
In many cases, the decomposition of the problem
goes hand-in-hand with its execution.
These problems typically involve the exploration
(search) of a state space of solutions.
Problems in this class include a variety of discrete
optimization problems (0/1 integer programming,
QAP, etc.), theorem proving, game playing, etc.
Exploratory Decomposition:
Example
A simple application of exploratory decomposition is in the
solution to a 15 puzzle (a tile puzzle). We show a sequence of
three moves that transform a given initial state (a) to desired final
state (d).
Of-course, the problem of computing the solution, in general, is
much more difficult than in this simple example.
Exploratory Decomposition:
Example
The state space can be explored by generating various successor
states of the current state and to view them as independent tasks.
Speculative
Decomposition
In some applications, dependencies between tasks are
not known a-priori.
For such applications, it is impossible to identify
independent tasks.
There are generally two approaches to dealing with such
applications: conservative approaches, which identify
independent tasks only when they are guaranteed to not
have dependencies, and, optimistic approaches, which
schedule tasks even when they may potentially be
erroneous.
Conservative approaches may yield little concurrency
and optimistic approaches may require roll-back
mechanism in the case of an error.
Speculative Decomposition:
Example
A classic example of speculative decomposition is
in discrete event simulation.
The central data structure in a discrete event
simulation is a time-ordered event list.
Events are extracted precisely in time order,
processed, and if required, resulting events are
inserted back into the event list.
Consider your day today as a discrete event
system - you get up, get ready, drive to work,
work, eat lunch, work some more, drive back, eat
dinner, and sleep.
Each of these events may be processed
independently, however, in driving to work, you
might meet with an unfortunate accident and not
get to work at all.
Therefore, an optimistic scheduling of other
Speculative Decomposition:
Example
Another example is the simulation of a network of nodes (for
instance, an assembly line or a computer network through which
packets pass). The task is to simulate the behavior of this network
for various inputs and node delay parameters (note that networks
may become unstable for certain values of service rates, queue
sizes, etc.).
Parallel Algorithm Models
An algorithm model is a way of structuring
a parallel algorithm by selecting a decomposition
and mapping technique and applying the
appropriate strategy to minimize interactions.
Data Parallel Model: Tasks are statically (or semi-
statically) mapped to processes and each task
performs similar operations on different data.
Task Graph Model: Starting from a task
dependency graph, the interrelationships among
the tasks are utilized to promote locality or to
reduce interaction costs.
Parallel Algorithm Models
(continued)
Master-Slave Model: One or more processes
generate work and allocate it to worker processes.
This allocation may be static or dynamic.
Pipeline / Producer-Comsumer Model: A stream of
data is passed through a succession of processes,
each of which perform some task on it.
Hybrid Models: A hybrid model may be composed
either of multiple models applied hierarchically or
multiple models applied sequentially to different
phases of a parallel algorithm.