A comparative analysis of group scheduling and critical path scheduling algoritHms
Shau-Ping Lo · 1988
The scheduling algorithm plays a vital part in determining a multiprocessor computer system's performances. Various heuristic scheduling algorithms have been proposed to determine the minimum scheduling time needed for multiprocess computations having precedence constraints among processes. Among these, the algorithm HLFET (Highest Level First with Estimated Time) is generally considered the best. However, the use of HLFET assumes no interprocess communication. Alternatively, the group scheduling algorithm is applicable to multiprocess computations having interprocess communications but no precedence constraints. Neither algorithms has taken advantage of the knowledge of application environment for multiprocess computations. This study compares the effectiveness of the HLFET and the modified group scheduling algorithms on computations having both precedence constraints and interprocess communications in terms of throughput, processor utilization rate and process response time. The dependencies of these algorithms on various computation parameters are investigated through simulation experiments. The simulation results can be summarized as follows: (1) The simulation experiments illustrate a scheduling anomaly for multiprocessor systems and help explain why group scheduling, particularly after the introduction of a restart mechanism, is more robust than HLFET scheduling. (2) The notion of a threshold number of processors for multiprocess computations is introduced. Below the threshold, the performance both of group and of HLFET algorithms is highly sensitive to variations in computation parameters, i.e., of the degree and pattern of process interaction. Above the threshold, the performance of the group scheduling is always better than that of HLFET scheduling. (3) The performance of group scheduling is more stable whenever the number of communicating processes varies from computation to computation. (4) The normalized swap-in/swap-out time and the normalized pause-wait time have insignificant impact on the relative performance of algorithms with different application parameters. Finally, an analytical procedure is developed to compute a lower bound of the differences in scheduling overhead among the simulated algorithms when the number of processors is large. This procedure has been used to validate some of the results of the simulation experiments.