An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments

Gang scheduling is a resource management scheme for parallel and distributed systems that combines time-sharing with space-sharing to ensure short response times for interactive tasks and high overall system throughput. In this paper, we present and analyze a queueing theoretic model for a general gang scheduling scheme that forms the basis of a multiprogramming environment currently being developed for IBM's SP2 parallel system and for clusters of workstations. Our model and analysis can be used to tune our scheduler in order to maximize its performance on each hardware platform. 1 Introduction Researchers and users of parallel and distributed systems have long realized that effective resource management is essential for achieving high performance in a multiprogrammed environment. Unfortunately, current multicomputing systems either dedicate all of their resources to one task, in which case they are not multiprogrammed, or they use simple resource scheduling mechanisms that provide n..