|
|
|
|
|
|
|
Figure 8.13
Realized mean speedup (Sp) for 24 Fortran
programs vs. max number of processors
used in a program execution (data from Lee
[182]). |
|
|
|
|
|
|
|
|
Thus, so long as there is sufficient work that occurs at relatively low degrees of parallelism, overall processor speedup will be limited to something less than p/In p. Lee compares the p/In p bound to typical speedups for a variety of programs, as in Figure 8.13. Lee's bound and data might seem to represent a significant limitation for multiprocessor partitioning, but others such as Gustafson [114] generally argue that as machines get faster and larger, users scale up their program size so that the general lapsed time for any program remains constant. As program size grows, one would envision that the logical parallelism inherent in the program might greatly exceed the physical parallelism of the system, thus allowing significantly more time to be spent at maximum degrees of parallelism, and hence invalidating Lee's equal-work hypothesis. |
|
|
|
|
|
|
|
|
While there may be little consensus on the long-term effect of partitioning on at least scientific programs, there is less controversy about the effect of synchronization and its subsequent effects on memory, bus, and cache traffic and its effects on system performance. |
|
|
|
|
|
|
|
|
8.5.1 Grain Size and Overhead |
|
|
|
|
|
|
|
|
The larger issue lurking here is how to pick an efficient grain size. The grain size is simply the number of instructions executed by an average size task on a single processor in a multiprocessor ensemble. If we make the grain size large, we reduce the amount of available parallelism. Even if we accept the argument that there is scaling of applicationsas processing ensembles get larger, so do applicationsit is still true that the larger the grain size, the less the parallelism. But as we reduce the grain size, the overhead becomes a significant factor in the computation. For effective computation, the grain size must be much larger than this overhead. Typically, the overhead consists of three items: |
|
|
|
|
|
