Overhead analysis of preemptive gang scheduling

Abstract. A preemptive gang scheduler is developed and evaluated. The gang scheduler, called SCore-D, is implemented on top of a UNIX operating system and runs on workstation and PC clusters connected by Myrinet, a giga-bit class, high-performance network. To have high-performance communication at the user-level and a multi-user environment simultaneously, we propose network preemption to save and restore network context as well as process contexts when switching distributed processes. We also developed a high-performance, user-level communication library, PM. PM and SCore-D collaborate for the net-work preemption. When user processes are gang-scheduled, communica-tion messages are rst ushed, then the messages and pending messages in the receive and send buers are saved and restored. Unlike CM-5's All-Fall-Down mechanism, our gang-scheduling scheme is all software; no special hardware support is assumed. Also there is no limitation on network topology and partitioning. The overhead of the gang scheduler is measured on our new PC clus-ter, which consists of 64 PentiumPros connected by Myrinet. NAS par-allel benchmark programs are used for the evaluation. We found that the message ushing time and network preemption time depends on the communication patterns of the application programs. We also found that the time of saving and restoring network context occupies more than two third of gang scheduling time. Evaluation shows that the slowdown of user program execution due to the gang scheduling is less than 9%when the time slice is 100msec.