4
$\begingroup$

On a parallel machine with $n$ processors we can compute the sum (or product, or the result of any associative operation) on $n$ numbers in $\log n$ steps. In the first step combine neighbors to get $n/2$ numbers left, then combine them so that $n/4$ numbers are left and so on until a single number, the result, is left which happens after $\lceil \log n \rceil$ steps. With this is it obvious that we can compute the matrix product of two $n \times n$ matrices $A = (A_{ij}), B = (B_{ij})$ with $n^3$ processors in $\log n + 1$ steps, in a first step compute all the $n^3$ products of the entries $A_{ik} \cdot B_{kj}$ for $i,j,k \in \{1,\ldots, n\}$. Then with $n^2$ processors compute the $n^2$ sums of the $n$ numbers $A_{i1}\cdot B_{1j} + \ldots + A_{ik}\cdot B_{kj}$. Hence we get by with $1 + \log n$ parallel steps.

Now the following argument is from C. Papadimitriou, Computational Complexity, page 361, to show that we get time $2\log n$ using just $n^2 / \log n$ processors (the argument used is called Brent's principle according to the book).

We compute the $n^3$ products not in a single step as before, but rather in $\log n$ ''shifts'' using $\lceil n^3 / \log \rceil$ processors at each shift. We use shifts of the same $\lceil n^3 / \log n \rceil$ processors to compute the first $\log \log n$ parallel addition steps, where more than $\frac{n^3}{\log n}$ processors would be ordinary needed. The total number of parallel steps is now no more than $2\log n$, with $\frac{n^3}{\log n}$ processors [...].

(those arguments could also be found on these slides).

But I get more parallel steps as $2\log n$.

1) First we compute the $n^3$ products $A_{ik}\cdot B_{kj}$ with $\log n$ shifts, hence we need $\log n$ parallel steps for this.

2) If we combine the results as written in the introduction, then in the $k$-th step we have $n/2^k$ numbers to combine. Hence if $2^k < \log n$ we do not have enough processors to do this in a single step, hence we have to ''shift'' again, this time $\lceil \log n / 2^k \rceil$ times. If $2^k \ge \log n$ we can use a single parallel step as we have enough processors at hand.

Combining the above reasoning we get the following equation (I omit the rounding) for the number of parallel steps: $$ \log n + \sum_{k=1}^{\log \log n} \frac{\log n}{2^k} + \log n - \log \log n. $$ The first summand commes from the shift over the $n^3$ numbers, the second summand for the shifts needed if in the combination/summation of the product we still have to many numbers for our processors, and the last for the number of steps if we do have enough processors. This equals \begin{align*} & \log n + \log n \left( 1 - \frac{1}{2^{\log \log n}} \right) + \log n - \log \log n \\ & = \log n + \log n - 1 + \log n - \log \log n \\ & = 3 \log n - \log \log n - 1 \end{align*} The last is in general more than $2\log n$, so what am I missing. Why does they argue they get by with $2\log n$ steps. Do I miss anything here?

$\endgroup$
2
$\begingroup$

Yes, you are correct while all textbooks and lecture notes you and I have found so far are wrong in claiming "doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in at most $2\log n$ steps by Brent's principle"

There is hardly anything valuable to add to your meticulous calculation. Anyway, here is an example that specializes your calculation.

An example

Let $n=16$. We have two $16\times16$ matrices, $(A_{ij})$ and $(B_{ij})$ with $\left\lceil \dfrac{n^3}{\log_2n}\right\rceil=\left\lceil\dfrac{16^3}{\log_2 16}\right\rceil=1024$ processors.

It takes 4 parallel steps to compute all the $n^3=4096$ products of the entries $P_{ijk}=A_{ik} \cdot B_{kj}$ for $i,j,k \in \{1,2,\cdots,16\}$ with $1024$ processors.

How to compute $n^2=256$ sums of the $n=16$ numbers $P_{i1j}+ \ldots + P_{i16j}$ for $i,j\in\{1,2,\cdots,16\}$?

We first compute $256\times 8=2024$ sums of two neighbors $S_{ikj}=P_{i(2k-1)j}+P_{i(2k)j}$ for $i,j\in\{1,2,\cdots,16\}$, $k\in\{1,2,\cdots, 8\}$. It takes 2 parallel steps for 1024 processors, where $2$ is $\dfrac{\dfrac{n^3}2}{\dfrac{n^3}{\log_2n}}=\dfrac{\log_2n}2>1$.

There are $256 \times 4 = 1024$, $256 \times 2 = 512$, $256 \times 1 = 256$ sums of two numbers to calculate, respectively. Each of them will take one parallel step because of the serial dependency. We need $3 =\log_2n-1$ parallel steps.

So we need $4 + 2 + 3 = 9$ parallel steps in total, which is bigger than $\lceil 2\log_2 n\rceil = 8$.

Corrected statement

Multiplication of two $n\times n$ matrices can be done in no more than $3\log_2 n+1$ parallel steps with $\lceil n^3 / \log_2 n \rceil$ processors by Brent's principle.

Brent's principle

Here is one version of Brent's principle that applies to current situation.

(Brent’s principle): An algorithm involving $t$ time steps and performing a total of $m$ operations can be executed by $p$ processors in no more than $t + \lceil(m – t) / p\rceil$ time steps in PRAM.

In particular, we have $m=n^3+ n^2(n-1)$ operations and $t=1+\lceil \log_2n\rceil$ time steps for matrix multiplication. If we have $p=\lceil n^3 / \log_2 n \rceil$ processors, the upper limit of parallel steps given by Brent's principle, $t + \lceil(m – t) / p\rceil$ is $3\lceil\log_2 n\rceil-1$ or $3\lceil\log_2 n\rceil$ or $3\lceil\log_2 n\rceil+1$.

$\endgroup$
  • $\begingroup$ Thanks. In our last paragraph if I plug in all the numbers I get $$t + (m-t)/p =1 + \log n + \frac{(n^3 + n^2(n-1) - (1 + \log n))\log n}{n^3}.$$ I do not see why $3\log n - 1$ would be an upper bound for it? $\endgroup$ – StefanH Mar 7 at 12:29
  • $\begingroup$ For all $n\ge2$, there exists $\delta\in\{-1,0.1\}$ such that $t + \lceil(m – t) / p\rceil=3\lceil\log_2 n\rceil+\delta$. Its proof is rather tedious and unenlightening, although the magnitude is easy to see. $\endgroup$ – Apass.Jack Mar 7 at 14:34
  • 1
    $\begingroup$ Ah okay, its not $\delta = -1$ for all $n$ if I got it right. $\endgroup$ – StefanH Mar 7 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.