|
|
|
|
|
|
|
Figure 8.6
Program dynamicity. |
|
|
|
|
|
|
|
|
number of ready tasks to each processor's execution queue. It has generally little run-time overhead, and since it requires little information, it is amenable to fully dynamic computations. |
|
|
|
|
|
|
|
|
2. Load balancing. Scheduling using load balancing relies on estimates of the amount of computation needed within each concurrent subtask. This more evenly distributes the workload among available processors. The technique incurs only a little more run-time overhead than is used in systems load balancing. |
|
|
|
|
|
|
|
|
3. Clustering. If we now assume that both a task's computational load and the amount of interprocess communication between process pairs is available, some tasks may be more optimally clustered together before assignment to available processors. The objective here is to both minimize interprocess communication and maintain load balance across the processors. Since pairwise communication process information must be developed, the run-time overhead with large numbers of tasks and processors can be quite high. |
|
|
|
|
|
|
|
|
4. Scheduling with compiler assistance. Block-level dynamic program information is gathered at run-time, and used in conjunction with interprocess communication and information on the computational requirements of each task to determine the schedule of concurrent tasks. |
|
|
|
|
|
|
|
|
5. Static scheduling/custom scheduling. If the program is relatively static, the exact interprocess communication and computational requirements can be determined at compile time, and an optimum schedule can be represented in a directed acyclic graph (DAG-type list structure). |
|
|
|
 |
|
|
|
|
Figures 8.7 and 8.8 from Ngai [217] indicate the speedup of several of these techniques for two scientific applications. Heuristic clustering |
|
|
|
|
|
