|
|
|
| | (Informal) Grain Description |
| Program Construct | Typical # Instr | | Basic block ("instr-level parallelism") | 510 | | Procedure | 20100 | | Small task ("process-level parallelism") | 1001,000 | | Intermediate task | 1,000100,000 | | Large task | 100,000 or more |
|
|
|
|
|
|
multiprocessor concurrency and instruction-level concurrency (discussed in the previous chapter) is the amount of overhead expected to be associated with each task. Overhead affects speedup. If uniprocessor program P1 does operation O1, then the parallel version of P1 does operations Op, where Op³ O1. |
|
|
|
|
|
|
|
|
For each task Ti, there is an associated number of overhead operations oi, so that if Ti takes Oi operations without overhead, then: |
|
|
|
|
|
|
|
|
where is the total work done by Pp, including overhead. Note that the task overhead grows with p. |
|
|
|
|
|
|
|
|
In order to achieve speedup over a uniprocessor, a multiprocessor system must achieve the maximum degree of parallelism among executing subtasks or control nodes. On the other hand, if we increase the amount of parallelism by using finer-and finer-grain task sizes, we necessarily increase the amount of overhead. This defines the well known "U" shaped curve for grain size (Figure 8.2). |
|
|
|
|
|
|
|
|
Figure 8.2
The effects of grain size. |
|
|
|
|
|
