|
|
|
|
|
|
|
Suppose a program p is converted into a parallel form, pp. This conversion consists of partitioning pp into a set of tasks, Ti. pp (as partitioned): |
|
|
|
|
|
|
|
|
Figure 8.1
Partitioning and scheduling. |
|
|
|
|
|
|
|
|
Partitioning is the process of dividing a program into tasks, each of which can be assigned to an individual processor for execution at run time. These tasks can be represented as nodes in a control graph. The arcs in the graph specify the order in which execution of the sub-tasks must occur. The partitioning process occurs at compile time, well before program execution. The goal of the partitioning process is to uncover the maximum amount of parallelism possible without going beyond certain obvious machine limitations. For example, searching for parallelism well in excess of p, the number of independent processors available in the system, is usually unprofitable. |
|
|
|
|
|
|
|
|
The program partitioning is usually performed with some a priori notion of program overhead [252]. Program overhead (o) is the added time a task takes to be loaded into a processor prior to beginning execution. The larger the size of the minimum task defined by the partitioning program, the smaller the effect of program overhead. Table 8.1 gives an instruction count for some various program grain sizes. The essential difference between |
|
|
|
|
|
