|
|
|
|
|
|
|
has made an interesting observation about the character of control-flow-limited multiprocessors. She introduces an equal-work hypothesis. Under this hypothesis, let us assume that an equal amount of work is done while one processor is active, and that this is the same as the amount of work done by two processors, and finally as the amount of work done by i processors or p processors. The control flow limits the amount of work available so that it is equally distributed across each of the processor subsets from 1 to p. That is, i Ti,p is the same for all i. Now assume that the amount of work required by the uniprocessor is the same as the amount of work required by the p processor ensemble. That is, if the number of operations for the uniprocessor execution is O1 and the number of operations for parallel execution is Op, then O1 = Op. If O1 executes in T1, then: |
|
|
|
|
|
|
|
|
since 1/pth of the work is done by each of the i subsets, and the speedup for each subset is i. Thus: |
|
|
|
|
|
|
|
|
The indicated series is simply the harmonic series. The sum of the harmonic series can be approximated as: |
|
|
|
|
|
|
|
|
Thus, we can rewrite the speedup as: |
|
|
|
|
|
|
|
|
Lee, in fact, goes on to show that the same bound is true, that the p/ log p bound also holds not only when the amount of work is equal across all processor subsets, but so long as a much more general condition is satisfied, i.e.: |
|
|
|
|
|
|
|
|
where Prob [i|p] is the probability that exactly i processors are used (out of p) at any given time. |
|
|
|
|
|
