Processor Allocation in Multiprogrammed Distributed memory Parallel Computer Systems

In this paper, we analyze three general classes of space-sharing scheduling policies under a workload representative of large-scale scientific computing. These policies differ in the manner in which processors are partitioned among the jobs as well as the way in which jobs are prioritized for execution on the partitions. We propose new adaptive and dynamic policies that differ from previously proposed policies in that, in their scheduling decisions, they can make use of user-supplied information about the resource requirements of submitted jobs. We examine the performance characteristics of these policies from both the system and user perspectives. Our results indicate that existing static schemes do not perform well under varying workloads, and that to provide good performance for such workloads the system scheduling policy must distinguish between jobs with large differences in execution times. We show that a judiciously parameterized dynamic space-sharing policy can outperform adaptive policies from both the system and user perspectives. Moreover, obtaining good performance under adaptive policies requires {a priori} knowledge of the job mix submitted to the system. Dynamic policies do not require prior information about the workload and are therefore preferable in unpredictable environments. (ScalParSys)