EVALUATION OF DESIGN CHOICES FOR GANG SCHEDULING USING DISTRIBUTED HIERARCHICAL CONTROL

Gang scheduling-the scheduling of a number of related threads to execu te simultaneously on distinct processors-appears to meet the requireme nts of interactive, multiuser, general-purpose parallel systems. Distr ibuted hierarchical control (DHC) has been proposed as an efficient me chanism for coping with the dynamic processor partitioning necessary t o support gang scheduling on massively parallel machines. Zn this pape r, we compare and evaluate different algorithms that can be used withi n the DHC framework. Regrettably, gang scheduling can leave processors idle if the sizes of the gangs do not match the number of available p rocessors. We show that in DHC this effect can be reduced by reclaimin g the leftover processors when the gang size is smaller than the alloc ated block of processors, and by adjusting the scheduling time quantum to control the adverse effect of badly matched gangs. Consequently, t he on-line mapping and scheduling algorithms developed for DHC are opt imal in the sense that asymptotically they achieve performance commens urate with off-line algorithms. (C) 1996 Academic Press, Inc.