Now, given a dag and
a weight estimated execution time, how can I tell if the dag is good or bad?
Let's derive an answer.
First, we'll identify a metric of goodness, and
then we will optimize the metric.
Let's use speedup as our metric.
Speedup is defined as the best sequential time divided by
the parallel time.
In terms of symbols, I'll use T* to denote the best sequential time, and
of course we'll use Tp(n) to denote the parallel time, as before.
Now, a quick comment about the numerator and the denominator of speedup.
The denominator will, in general, depend on the work, the span, the problem size,
and the number of processors.
The numerator will depend essentially on the work
done by the best sequential algorithm.
So for notational consistency, since I'm using work in the case of the parallel
algorithm, I'll use another work symbol for the sequential algorithm.
The best sequential time will essentially always be equal to the best
sequential work.
Now, you might be wondering, why am I saying best sequential time?
What's special about best?
The answer, is I'm a good professor, and I want to make it hard to cheat!
After all, you can always make speedup artificially large by choosing
a terrible baseline.
If any of you are into marketing, you know what I'm talking about.
Now if I give you a PRAM with P processors then ideally,
you'd like the parallel algorithm to be P times faster
than the best sequential algorithm.
This condition is called ideal speedup or
sometimes linear speedup, linear scaling, or ideal scaling.
But basically, they all say you want the speedup to be linear in p.
Here I'm using big theta notation because you usually won't care about
the constant factors, at least not at this pencil and
paper algorithm design stage.
Now essentially,
what this says is if p doubles, then you want Sp to also double.
Of course, that's an ideal, we might not always achieve it.
Let's write speedup in terms of best sequential work and parallel time.
Now, in the general case we can use Brent's Theorem to get an upper bound on
time and therefore a lower bound on speedup.
So let's go ahead and plug in Brent's Theorem.
For notational ease, I've dropped this paren of n in the right hand side.
Just remember that there's a dependence on n there.
Let's do a little bit of algebra on the right hand side to get it into a form
that we can analyze more easily.
Okay, written in this form,
you can now immediately see what has to be true in order to get ideal scaling.
First notice the numerator, which has the number of processors in it.
So relative to this goal, I will pay a penalty,
which is determined by the denominator.
In other words, if I want to get linear scaling,
I need the denominator to be a constant.
So what would it take for this to be true of the denominator?
Let's look at each term in turn.
For this term to be constant, the work of the parallel algorithm has to match
the work of the best sequential algorithm.
This principle is something we call work-optimality.
It's a necessary condition to ensure ideal scaling.
Intuitively, it prevents another form of cheating.
It says that if you get a very parallel algorithm by dramatically increasing
the work relative to the best sequential algorithm,
then that's actually bad for speedup.
Now let's look at the other term in the denominator.
For this term to be constant,
it essentially says that p should be proportional to W* over D.
So this is similar to the idea of the average available parallelism.
And the main difference is that you have a W* here instead of just W.
Now there's another way to write this.
This other way to write it is to say that W* divided by P has to be
big omega(D).
Let's think about this for a second.
W* over P is basically the work per processor.
This expression says that the work per processor has to grow, and
in particular it has to grow proportional to the span.
And the span, remember, depends on the problem size, n.
So in other words,
this says that the work per processor has to grow as some function of n.
In the parallel computing literature, this is called weak scalability.
So basically what it says is as you increase the concurrency of the machine,
then if you want to get good scaling,
you might need to increase the problem size.
Okay, that was a little messy.
Let's try to recap the algorithm design goals you just derived.
So starting form speedup we set linear scaling as our goal.
Now, to achieve linear scaling,
you derived two fundamental principles of good parallel algorithm design.
The first is work-optimality, which says that the work of the parallel algorithm
should match the work of the best sequential algorithm.
And the second principle is weak-scalability.
In one interpretation, it basically says that the work per processor should
grow as a function of n, and that function is determined by the span