4. Parallel Computing 14. Introduction

14.5  Expression Evaluation

Parallelism can be exhibited in many kinds of expression evaluations. The UNIX®

command-line expressions are indeed a form of this. But how about with ordinary

arithmetic expressions, such as

(a + b) * ((c - d) / (e + f)))

Here too there is the implicit possibility of parallelism, but at a finer level of granularity.

The sum a + b can be done in parallel with the expression (c - d) / (e + f). This expression

itself has implicit parallelism. Synchronization is required in the sense that the result of a

given sub-expression can't be computed before the principal components have been

computed. Interestingly, this form of parallelism shows up if we inspect the dag (directed

acyclic graph) representation of the expression. When there are two nodes with neither

having a path to the other, the nodes could be done concurrently in principle.

*

+

+

-

/

f

e

d

c

b

a