STATIC AND DYNAMIC PROCESSOR SCHEDULING DISCIPLINES IN HETEROGENEOUS PARALLEL ARCHITECTURES

Most parallel jobs cannot be fully parallelized. In a homogeneous para llel machine-one in which all processors are identical-the serial frac tion of the computation has to be executed at the speed of any of the identical processors, limiting the speedup that can be obtained due to parallelism. In a heterogeneous architecture, the sequential bottlene ck can be greatly reduced by running the sequential part of the job or even the critical tasks in a faster processor. This paper uses Markov chain based models to analyze the performance of static and dynamic p rocessor assignment policies for heterogeneous architectures. Parallel jobs are assumed to be described by acyclic directed task graphs. A n ew static processor assignment policy, called Largest Task First Minim um Finish Time (LTFMFT), is introduced. The analysis shows that this p olicy is very sensitive to the degree of heterogeneity of the architec ture, and that it outperforms all other policies analyzed. Three dynam ic assignment disciplines are compared and it is shown that, in hetero geneous environments, the disciplines that perform better are those th at consider the structure of the task graph, and not only the service demands of the individual tasks. The performance of heterogeneous arch itectures is compared with cost-equivalent homogeneous ones taking int o account different scheduling policies. Finally, static and dynamic p rocessor assignment disciplines are compared in terms of performance. (C) 1995 Academic Press, Inc.