How to Define an Efficient, Optimal or Suboptimal Parallel Algorithm?

Question

I am going through the book of Parallel Programming and a parallel algorithm is often classified as Efficient, Optimal or Suboptimal. I googled these terms but I didn't found a clear definition for them.

Define $T(n)$ as the running time of the sequential algorithm, $t(n)$ as the running time of the parallel one, $p(n)$ as the number of processing units. Hence work $w(n)=p(n)t(n)$, speedup factor $S(p)=\frac{T(n)}{t(n)}$, efficiency $E=\frac{T(n)}{p(n)t(n)}\times 100\%$.

The parallel algorithm is efficient if:

1. $t(n)=O(\log^c n)$ for some constant $c>0$; and
2. work $w(n)=T(n)O(\log^c n)$

The parallel algorithm is optimal if:

1. $t(n)=O(\log^c n)$ for some constant $c>0$; and
2. work $w(n)=O(T(n))$

Are the definitions of efficient and optimal correct? And what about suboptimal?

I am literally a noob to parallel programming and I googled a lot without a clue. Any help would be greatly appreciated. Thanks in advance.

Answer 1

The word "correct" is misplaced, what you should be asking is whether those definitions are meaningful / express the notion of "efficient" that you (or the author) had in mind.

The notion of efficient might vary depending on the context, so there is no "correct" definition. For example, in sequential computing, polynomial time is usually considered efficient. One of the reasons to use polynomial time is because polynomials have nice properties that cause our definition to well-behave, e.g. an efficient algorithm which uses another efficient algorithm as a subroutine is still efficient (this is because polynomials are closed under composition).

With this in mind, I'll try to give a few reasons as to why these definitions might be useful or reflect what you imagine that an efficient parallel algorithm will be.

First, it obviously holds that $w(n)=\Omega(T(n))$, since a sequential algorithm can simulate the parallel one by doing the work of all processors one by one, which takes $p(n)t(n)=w(n)$ time. Here I assumed that $T(n)$ is a lower bound on the time required for a sequencial algorithm to preform the given task. This explains your notion of optimallity, one cannot do better then $w(n)=O(T(n))$.

As for efficient, requiring the running time for each processor to be $O(\log^c n)$ results in exponential speedup over a sequencial algorithm, since $T(n)=\Omega(n)$ (the sequencial algorithm must at least read the entire input), and thus $T(n)=\Omega\left(2^{[t(n)]^{\frac{1}{c}}}\right)$.

The additional requirement of $w(n)=T(n)O(\log^c n)$ means that the overall number of operation does not increase too much (you pay in processing power for better computation time). So in this case, the overall number of operations for the sequencial/parallel algorithm is equivalent up to polylogarithmic factors.