Processor scheduling on multiprogrammed, distributed memory parallel computers

Multicomputers, consisting of many processing nodes connected through a high speed interconnection network, have become an important and common platform for a large body of scientific computations. These parallel systems have traditionally executed programs in batch mode, or have at most space-shared the processors among multiple programs using a static partitioning policy. This, however, can result in relatively low system utilization and throughput for important classes of scientific applications. In this paper we consider 'a class of scheduling policies that attempt to increase processor utilization and system throughput by timesharing a partition of processors among multiple programs. We compare the system performance under this multiprogramming policy with that of static partitioning for a variety of workloads via both analytic and simulation modeling. Our results show that timesharing a partition can provide significant improvements in performance, particularly at moderate to heavy loads. The performance gains of the multiprogrammed policy depend upon the inherent efficiency of the parallel programs that comprise the workload, decreasing with increasing program efficiency. Our analysis also provides the regions over which one scheduling policy outperforms the other, as a function of system load.