Divide-and-conquer is probably the best-known parallel programming paradigm. The problem to be solved is decomposed into smaller problems that are solved in parallel before being recombined to produce the result. Our example is taken from a parallel linear equation solver that we wrote as a realistic medium-scale parallel program [Loidl et al., 1995], whose overall structure is described in Section *.
The computation performed in the solve-stage of the computation is essentially a determinant computation which can be specified as follows:
sum l_par `demanding` parList rnf l_par
where
l_par = map determine1 [jLo..jHi]
determine1 j = (if pivot > 0 then
sign*pivot*det' `demanding` strategyD
else
0) `sparking` rnf sign
where
sign = if (even (j-jLo)) then 1 else -1
pivot = (head mat) !! (j-1)
mat' = SqMatrixC ((iLo,jLo),(iHi-1,jHi-1))
(map (newLine j) (tail mat))
det' = determinant mat'
strategyD =
parSqMatrix (parList rwhnf) mat' `seq`
(rnf det' `par` ())
In this example almost all available parallelism is exploited, and for
comparison, Appendix * contains sequential and
directly parallel versions of this function. At first sight, it may
not be obvious that this is a divide-and-conquer program. The crucial
observation is that a determinant of a matrix (A) of size n is
computed in terms of the determinants of n matrices (A') of size
n-1.
The first strategy, parList rnf l_par specifies that the determinant of each of the matrices of size n-1 should be calculated in parallel. There are two strategies in determine1. The first, `sparking` rnf sign specifies that the sign of the determinant should be calculated in parallel with the conditional. Only if the pivot is non-zero is the second strategy, strategyD used. It specifies that the sub-matrix (mat') is to be constructed in parallel before its determinant is computed in parallel with the result. The strategyD is invoked with demanding to ensure that it is evaluated, if sparking had been used, the final `par` () could be omitted, but the strategy might never be executed. Note that some data-oriented strategies such as parList and parSqMatrix are used within the overall control-oriented structure.