Transcript Parallel algorithms for expression evaluation

Parallel algorithms for
expression evaluation
Simultaneous substitution method
(SimSub)
Simultaneous Substitutions
Method (SimSub)
x = Expression(y) and y = Expression1
a variable y can be substituted by its
expression or by its value if it is known (if
Expression1 is a constant)
assume we have




a sequence of expressions defining variables,
each expression is of a constant size
variables are numbered and
i-th expression depends only on variables with
numbers smaller than i e.g. x1=4 x2=x1+5
x3=x1+x2*7 x4=x2*x3
One parallel step: for each expression
substitute its variables by their expression if it is
safe;
safe means that corresponding expression has
at most one variable
Example: summing the numbers 2, 1, 3, 2, 1, 3, 2, 1 we can write a
sequential program
x1 = 2; x2 = x1+1; x3 = x2+3; x4 = x3+2; x5 = x4+1; x6 = x5+3; x7 = x6+2
after parallel step 1
x1 = 2; x2 = 3; x3 = x1+4; x4 = x2+5; x5 = x3+3; x6 = x4+4; x7 = x5+5
after parallel step 2
x1 = 2; x2 = 3; x3 = 6; x4 = 8; x5 = x1+7; x6 = x2+9; x7 = x3+8
after parallel step 2
x1 = 2; x2 = 3; x3 = 6; x4 = 8; x5 = 9; x6 = 12; x7 = 14
output = sum = x7
In this way we can sum 1024 numbers in 10 rounds
Tree-contraction
========================================
Parallel algorithms related to expression evaluation
correspond to parallel algorithmic technique called
tree-contraction
===============================================
Tree-contraction is used in parallel expression evaluation
Since the structure of a expression is a tree there are
different tree-contraction techniques
Basic operations are:
- redirecting edges of the tree
- removing nodes marking (pebbling) nodes
- creating additional edges
the final aim is to guarantee that logarithmic number of
contractions is sufficient
Tree-contraction related to
SimSub algorithm
Example
Substitutions method works in O(log n) time. In each
iteration the active tree is reduced by 1/3 at least.
The active tree consists of nodes relevant to the output computation,
The root is the output variable (the last one).
Fn is the smallest
tree which needs n
iterations in tree
contraction related
to SimSub algorithm
How the SimSub algorithm
works for general graphs ?
sometimes very poor
 (e.g. when computing Fibonacci numbers)
generally with n processors we need
n-1 iterations
-only one processor really works
each time, so the same can be done with a
single processor
SimSub will terminate after
O(log (tree-size(graph)) iterations
for the dependency graph of Fibonacci numbers
tree-size (number of paths) is exponential.
There is alternative parallel method SimSub’, see
dynamic dependency graphs. programming
problems, when we can deal effectively with such
types of
Other tree contraction method:
parallel pebble game (PPG)
Parallel pebble game (PPG) works for full
binary trees, full means each father has
exactly 2 sons