Carleton University
Technical Report TR-97-01
January 1997
Performance Comparison of Processor Scheduling Strategies in a Distributed-Memory Multicomputer System
Abstract
Processor scheduling policies on systems that run multiple applications simultaneously can be broadly divided into space-sharing and time-sharing policies. Space-sharing policies partition the system processors and each partition is allocated exclusively to a job. In time-sharing policies, processors are temporally shared by jobs (e.g., in a round robin fashion). Space-sharing and time-sharing policies have their advantages and disadvantages. It has also been suggested that a hybrid policy that combines space-sharing and time-sharing is beneficial in improving the overall performance.Processor scheduling has received considerable attention in the context of shared-memory multiprocessor systems but has not received as much attention in distributed-memory multicomputer systems. Furthermore, most previous research in this area has either used a simulation model or an analytical model in evaluating the performance of various policies. Very often these models neglect several practical aspects of the system and workload.
Our goal is to implement processor scheduling policies on a real system and evaluate their performance. We have used a Transputer-based system to implement two policies — one space-sharing policy and one time-sharing policy — in order to study the relative performance trade-offs involved. We have also implemented a hybrid space-sharing and time-sharing policy. We report the performance sensitivity of these policies to various system and workload parameters. These include three types of applications, four types of interconnection networks, two kinds of software architecture. An aspect, which is not present in most previous studies, is that our study reports the impact of such practical issues as the contention for communication links, network topology, contention for memory, memory size limitation, and software architecture on the performance of the scheduling policies.