Alternatives to coscheduling a network of workstations

Efficient scheduling of processes on processors of a Network of Workstation s (NOW) is essential for good system performance. However, the design of su ch schedulers is challenging because of the complex interaction between sev eral system and workload parameters. Coscheduling, though desirable, is imp ractical for such a loosely coupled environment. Two operations, waiting fo r a message and arrival of a message, can be used to take remedial actions that can guide the behavior of the system toward coscheduling using local i nformation. We present a taxonomy of three possibilities for each of these two operations. leading to a design space of 3x3 scheduling mechanisms. Thi s paper presents an extensive implementation and evaluation exercise in stu dying these mechanisms. Adhering to the philosophy that scheduling and comm unication are intertwined and should be studied in conjunction, a complete communication substrate for UltraSPARC workstations, connected by Myrinet a nd running Solaris 2.5.1, has been developed. This platform provides the en tire Message Passing Interface (MPI) to readily run off-the-shelf MPI appli cations by employing protected low-latency user-level messaging. Several ap plications can concurrently use this interface. This platform has been used to design. implement, and uniformly evaluate nine scheduling strategies wi th a mixture of concurrent real applications with varying communication int ensities. This includes five new schemes (Periodic Boost, Periodic Boost wi th Spin Block, Spin Yield, Periodic Boost with Spin Yield, Dynamic Coschedu ling with Spin Yield) that are presented in this paper. In addition to our evaluations of the pms and cons of each mechanism in terms of throughput, r esponse time, CPU utilization, and Fairness, it is shown that Periodic Boos t is a promising approach for scheduling processes on a NOW. (C) 1999 Acade mic Press.