Super-linear parallelism or speedup in parallel matrix multiplication algorithms

Question

I'm reading this slides from a MIT course on parallel software performance. They introduced the concepts of Work $T_1$, Span $T_\infty$ and Parallelism (ratio $T_1/T_\infty$). What is called ''Parallelism'' here can be interpreted, according to the same authors, as the maximum possible speedup that can be achieved on any number of processors [CLRS, chapter on parallel algorithms].

Assuming an ideal machine, ignoring overheads, speedup $S_p$ (ratio $T_1/T_p$) for any number of procesors $p$ is at most linear. Rare super-lineal effects can't be observed in this idealized model. This is directly expressed by the "Work Law": $ \frac{T_1}{T_p} \leq p$. Sometimes Parallelism is denoted by $S_\infty$.

Now, given any number of processors, i suppose we can all agree Parallelism should be at most linear, because Parallelism is just in particular the maximum achievable with enough processors. However, in slides 33, 57 and 64, all the matrix parallel proposals have obscene amount of parallelism. For example, in slide 33, we have $T_1=n^3$, $T_\infty=\log^2 n$, and therefore $S_\infty=\frac{n^3}{\log^2 n}$. This is way above $n$.

Also, suppose any $n$, if i give you $p=n$ processors, doesn't this mean also that $S_p=\frac{p^3}{\log^2 p} > p $?, which should not be possible. I feel this contradict the authors interpretation of what is or means $S_\infty$.

At first i thought the reason is because the authors are not really using input size, i.e. $n^2$, to do the analysis but parameter $n$ instead. We could say, $N=n^2$ so $n=\sqrt{N}$, and then we actually have in terms of input size: $S_\infty=\frac{(\sqrt{N})^3}{\log^2 (\sqrt{N})}$, but this is also super-linear.

So, now it seems i learned that ideal speedup $S_\infty$ (aka Parallelism) is not upper bounded like $S_p$. But somehow i feel it is just like a tricky thing coming from conflating the size of the input and the actual amount of work to do.

The question is, this matrix parallel algorithms have super-linear speedup or not?. If not, then i guess i'm misunderstanding something, but what exactly?.

Answer 1

Let's start from the definitions, in order to clarify things.

The work of a computation executed by $p$ processors is the total number of operations performed. Ignoring the parallel overhead, the work is equal to $T_1$ which is the time used to run the computation on a single processor.

Think about this: the work is “the total number of basic operations in the problem”, not a parameter of the input size. To understand why, here is an example related to your post. For a matrix problem involving $n \times n$ matrices the problem size could be $n$. But, defining the problem size like this allows the problem size itself to be interpreted differently for different problems: indeed, doubling the input size results in a eight-fold increase in serial execution time for matrix multiplication, but only a four-fold increase for matrix addition. As a consequence, the work for $n \times n$ matrix multiplication is $\Theta(n^3)$ and $\Theta(n^2)$ for addition of two $n \times n$ matrices.

The running time of a computation on $p$ processors is denoted by $T_p$. Since a finite number $p$ of processors cannot be faster than an infinite number of processors, it follows that $T_p \geq T_\infty$.

Next, the cost of the computation is $p T_p$; it is the total time spent by all of the processors. Of course, the cost is always at least the work: since $p$ processors can perform at most $p$ operations in parallel, it follows that $p T_p \geq T_1$.

The span (also known as depth or critical path length) of the computation is the length of the longest series of operations that have to be performed sequentially owing to dependencies. The span is denoted by $T_\infty$ and is defined as the time spent computing using an idealized machine with an infinite number of processors. Your goal as a designer of parallel algorithms actually is to minimize the span,since it determines the shortest possible parallel execution time.

The parallelism represents the maximum possible speedup on any number of processor. It is defined as the ratio $\frac{T_1}{T_\infty}$.

Finally, the speedup on $p$ processors is the ratio $\frac{T_1}{T_p}$. Of course, it is not possible to achieve $T_P > \frac{T_1}{p}$: that would mean that we did not all of the work of the parallel computation. Moreover, it's also impossible to achieve $T_P > T_\infty$, we do not have an infinite number of processors really available. The best we can aim for, asymptotically, is $T_p = O(\frac{T_1}{p} + T_\infty)$.

It is worth recalling here immediately that the idealized machine equipped with an infinite number of processors is just a useful abstraction. Of course, we do not have parallel supercomputers with an infinite number of processors (or cores of executions). The main insight here is that one should try to use the maximum possible number of processors that a parallel algorithm can gainfully use, but not more. Indeed, there is an optimal number of processors for each parallel computation, and trying to add additional processors not does not help, and, instead, results in worst performances. The optimal number of processors depends on the span. In turn, minimizing the span may not be easy: even assuming an infinite number of processors, there are temporal dependences that can not be avoided in some parallel computations, and these dependences will harm the performances since some of the processors will have to wait. This is because, informally speaking, time-like variables and related computations can not be parallelized (only space-like variables and computations can).

Now think about an embarrasingly parallel computation, i.e., a sequential computation which is made of a number $x$ of units to be computed, and each of the units can be computed in parallel by a different processor without requiring any kind of interaction. The span for this parallel computation actually is $O(1)$ so that the corresponding parallelism equals the work $T_1$. This is the best we can hope for, and is actually realized for embarrasingly parallel computation. For general parallel computations, instead we have $T_\infty \leq T_p \leq T_1$ and the speedup is usually not so great. Brent's theorem states that

$T_p \leq T_\infty + \frac{T_1-T_\infty}{p}$ or, alternatively,

$\frac{T_1}{p} \leq T_p \leq \frac{T_1}{p} + T_\infty$.

In practice, the maximum number of processors that can be gainfully used depends on the specific parallel computation, in particular on its work: one can at most assign a unit of work to a processor. If we use more, the remaining processors will be idle (they will not have anything to do) and the performances will therefore decrease. This is a theoretical upper bound, matched by embarrassingly parallel computation.

In your matrix multiplication example, you are therefore incorrect when you state that the problem size is $n$ or $n^2$. As shown, it is actually $n^3$, since this is the number of scalar multiplications required to compute the $n^2$ entries of the matrix product (assuming the ordinary sequential matrix multiplication algorithm). And yes, by using $n^3$ processors one can compute the matrix product as in the DNS (Dekel, Nassimi and Aahni) Algorithm in time $T_p = O(\lg n)$ (this results can be even made cost-optimal by using $O(n^3/\lg n)$ processors). Of course, this is only of theoretical importance and useless in practice, owing to the huge number of processor required: even multiplying two "small" matrices of order $n = 1000000$ is impossible, the number one supercomputer on the top500 list has not that many cores of execution. In practice, we solve the problem by scaling down the processors, i.e., by using $p << n^3$ processors. Anyway, by using the DNS algorithm you obtain an even better parallelism, namely $S_\infty = \frac{n^3}{\lg n}$.

At the end, hopefully it should be clear that in your example there is no superlinear speedup phenomenon: it is forbidden by the theory and the analysis does not contradict the theory, since the ratio $S_\infty = \frac{n^3}{\lg^2 n}$ does not involve $p$ and refers to an infinite number of processors. The problem is that you can not simply put $p = n$ and simultaneously maintain the same meaning of the ratio. To preserve the exact meaning, you must use the true problem size, i.e., you need to put $p = n^3$. But then, the ratio becomes $\frac{p}{\lg ^{2} \sqrt[3]{p}}=O\left(\frac{p}{\lg ^{2} p}\right)$ which, definitely, is not superlinear.

Answer 2

The speedup cannot be superlinear in the number of processors (because a single processor can always simulate $p$ of them with no loss of efficiency). As said by @Dmitry, $S_\infty$ corresponds to an infinity of processors so there is no contradiction.

Now you are trying to generalize

$$S_\infty=\frac{n^3}{\log^2n}$$ to $$S_p=\frac{p^3}{\log^2p}$$ when $p=n$. But this does not work because $p=n\ne\infty$.

Answer 3

When you multiply two n x n matrices using the naive algorithm, your problem size is not n, but n^2. The number of operations is not n, but n^3.

Unless someone is more clever than I am, an infinite number of processors could calculate the product in time O (log n), since you need to add sums of n numbers and you do that by adding n/2 pairs, then n/4 sums, and so on. So the maximum speedup is n^3 / log n. The speedup is always less than the number of operations, but that number is not n. (An interesting problem: How many processors do you need to calculate the product in 2 log n steps or 3 log n steps? Should be closer to n^3 / log n than to n^3).

PS. A typical hardware multiplier on a modern processor will get the maximum speedup, doing n^2 operations in O (log n), using O(n^2) tiny processors, but limited to n ≤ 64.

PS. Sometimes the algorithm with the highest speedup for an infinite number of processors will do substantially more operations, but arranged cleverly. This might not be the best algorithm for small numbers of processors. I might have an algorithm A calculating a result with p processors using n^2 operations with a speedup of p, and an algorithm B using n^3 operations with a speedup of p^2.5. A will be faster if p < n^1.5.