Buffered Coscheduling: A New Methodology for Multitasking Parallel Jobs on Distributed Systems

Buffered coscheduling is a scheduling methodology for time-sharing communicating processes in parallel and dis-tributed systems. The methodology has two primary fea-tures: communication buffering and strobing. With commu-nication buffering, communication generated by each pro-cessor is buffered and performed at the end of regular inter-vals to amortize communication and scheduling overhead. This infrastructure is then leveraged by a strobing mecha-nism to perform a total exchange of information at the end of each interval, thus providing global information to more efficiently schedule communicating processes. This paper describes how buffered coscheduling can optimize resource utilization by analyzing workloads with varying computational granularities, load imbalances, and communication patterns. The experimental results, per-formed using a detailed simulation model, show that buffered coscheduling is very effective on fast SANs such as Myrinet as well as slower switch-based LANs