Scheduling on multiprogrammed, distributed memory parallel computers
Sanjeev K. Setia · 1993
Multicomputers, consisting of a large number of processors interconnected by a high-speed network, are rapidly becoming an important platform for a large body of scientific computations. While the raison d'etre of multicomputers is to provide high performance to individual applications, cost and efficiency considerations make it necessary to share these systems among multiple applications. Multicomputers have traditionally space-shared the system processors among multiple programs using a static partitioning policy. In this dissertation, we present alternative strategies for scheduling multiple programs on multicomputers and show that they result in improved system throughput and utilization in comparison to existing policies. We first show that, for good performance, the system scheduling policy must modify its processor allocation decisions in response to changes in the system load. Further, the performance of an adaptive scheduling policy depends upon the ability of the system scheduler to distinguish between jobs with large differences in execution times when making processor allocation decisions. Based on these insights, we propose a simple (and practical) adaptive space-sharing policy, that is applicable to general-purpose systems, and show that the performance of the policy is superior to that of static policies. We also consider a dynamic space-sharing policy, under which a program's partition size can change during its execution. Our results indicate that, despite its relatively high cost, dynamic space-sharing results in improved performance for workloads with long-running programs. We describe an application-directed scheme for the dynamic reconfiguration entailed by dynamic space-sharing and present experimental results for the overhead of this scheme on the CM5. Next, we consider the performance of scheduling policies that time-share a partition of processors among multiple programs. We illustrate the conditions under which time-sharing results in improved system performance over space-sharing and examine performance tradeoffs between two different approaches to time-sharing--gang-scheduling and independent time-slicing. Our results show that while gang-scheduling is essential for programs that synchronize relatively frequently, independent time-slicing leads to improved performance for medium and coarse grained programs, particularly at moderate to heavy system loads.