|
|
|
|
|
|
|
Figure 8.10
Efficiency (Ep) as a function of task overhead
is a fraction of Tp, the task time. |
|
|
|
|
|
|
|
|
Ep measures the effectiveness of the p-parallel multiprocessor ensemble, contrasted to a uniprocessor, which otherwise has the same capabilities as one of the parallel processors. In theory at least, Ep < 1. This is so since it ought to be possible for the single processorin the worst uniprocessor caseto simply take the parallel processor algorithm and emulate it by executing p times. Cases where speedup is greater than p or efficiency is greater than 1 can arise in practice, however, and are referred to as superlinear speedup. These cases are usually the result of: |
|
|
|
|
|
|
|
|
1. Failure to use the best uniprocessor algorithm in evaluating the uniprocessor case. In fact, most cases of superlinear speedup are the result of simply scaling the parallel processor algorithm down to p = 1. |
|
|
|
|
|
|
|
|
2. More interesting examples of superlinear speedup arise from anomalies in the memory system. We can generally ensure that Ep < 1, and superlinear speedup does not occur if we insist that the memory system for both the uniprocessor and the parallel processor ensemble be the same. |
|
|
|
|
|
|
|
|
If we allow the memory system to scale, that is, to be p times larger for the parallel processor system than for the uniprocessor system, then it is easy to imagine cases where the larger memory system captures working set information not available to the smaller-memoried uniprocessor. The larger memory then provides a considerable (i.e., Sp > p) overall performance advantage. For the rest of our discussion, we limit our attention to cases where Ep < 1. |
|
|
|
|
|
|
|
|
In addition to partitioning and algorithmic limitations, synchronization represents an overhead which both limits speedup and decreases multiprocessor efficiency. For any particular system, if we regard the synchronization overhead as being relatively fixed per task, it is easy to see that the grain size or Tp is limited in order to achieve a given level of efficiency. Figure 8.10 illustrates the relationship between Ep and the synchronization overhead in the absence of partitioning or other types of multiprocessor performance limitations. |
|
|
|
|
|
|
|
|
Some time ago, Amdahl introduced the notion of serial time (Ts) in a parallel processor system [14]. Ts is simply the amount of time that only a single |
|
|
|
|
|
