Setup

The P$-$MATRIX$-$MULTIPLY$-$RECURSIVE

procedure from chapter $26\mathrm{.}2$ must allocate a temporary matrix D

of size n$\backslash$times n

$,$ which can adversely affect the constants hidden by the $\backslash$Theta

$-$notation. The procedure has high parallelism, however: $\backslash$Theta $($n$3/$log$2$n$)$

$.$ For example, ignoring the constants in the $\backslash$Theta

$-$notation, the parallelism for multiplying $1000\backslash$times $1000$

matrices comes to approximately $10003/102=107$

$,$ since log$100010$

$.$ Most parallel computers have far fewer than $10$ million processors.

Part A

Parallelize MATRIX$-$MULTIPLY$-$RECURSIVE

from chapter $4\mathrm{.}1$ without using temporary matrices so that it retains it $\backslash$Theta $($n$3)$

work.

TIP

Spawn the recursive calls, but insert a sync in a judicious location to avoid races.

Part B

Give and solve recurrences for the work and span of your implementation.

Part C

Analyze the parallelism of your implementation. Ignoring the constants in the $\backslash$Theta

$-$notation, estimate the parallelism on $1000\backslash$times $1000$

matrices. Compare with the parallelism of P$-$MATRIX$-$MULTIPLY$-$RECURSIVE

$,$ and discuss whether the trade$-$off would be worthwhile.