|
|
|
|
|
|
|
1. It indicates to the compiler those critical regions where a second pass at concurrency detection can perhaps best be used. |
|
|
|
|
|
|
|
|
2. It provides an initial (or static) scheduling of tasks to processors. |
|
|
|
|
|
|
|
|
As the overall goal is maximum speedup, the maximum degree of parallelism must be achieved, but with minimum overhead [252]. Data movement, whether of global or local data, must be minimized in order to maximize the overall processor utilization. Issues such as determination of the critical path structure and maximizing parallelism become very difficult problems in complex program structures. |
|
|
|
|
|
|
|
|
Scheduling can be done either statically (at compile time) or dynamically (at run time). Usually, it is performed at both times. Static scheduling information can be derived on the basis of the probable critical paths. This alone is insufficient to ensure optimum speedup or even fault tolerance. Suppose, for example, one of the processors scheduled statically was unavailable at run time, having suffered a failure. If only static scheduling had been done, the program would be unable to execute if assignment to all n processors had been made. It is also oftentimes the case that program initiation does not begin with n predesignated idle processors. Rather, it begins with a smaller number as previously executing tasks complete their work. Thus, the processor availability is difficult to predict and may vary from run to run. While run-time scheduling has obvious advantages, handling changing systems environments, as well as highly variable program structures, it also has some disadvantagesprimarily its run-time overhead. As Ngai [217] observes, all major issues in run-time scheduling center on "how to ensure performance gains and how to reduce overhead losses." |
|
|
|
|
|
|
|
|
Run-time scheduling can be performed in a number of different ways. The scheduler itself may run on a particular processor, or it may run on any processor. It can be centralized (performed by only one processor) or distributed (performed by several processors). It is clearly desirable that the scheduling not be designated to a particular processor, but rather that it be initiated by any processor and then the scheduling process itself be distributed across all available processors. This is summarized in Table 8.2. |
|
|
|
|
|
|
|
|
Typical run-time information includes information about the dynamic state of the program and the state of the system. The program state may include details provided by the compiler, such as information about the control structure and identification of critical paths or dependencies. Dynamic information includes information about resource availability and work load distribution. Program information must be generated by the program itself, and then gathered by a run-time routine to centralize this information. |
|
|
|
|
|
|
|
|
The major run-time overheads in run-time scheduling include: |
|
|
|
|
|
|
|
|
1. Information gathering. |
|
|
|
|
|