Implicit Cocheduling

Implicit Coscheduling


Implicit Coscheduling is a new time-sharing approach for scheduling parallel applications. Implicit coscheduling uses communication and synchronization occurring naturally within the application to coordinate scheduling across workstations. There are two events that must be observed and acted upon for processes to implicitly coschedule themselves:

  1. If a process sends a message and then waits longer than the round-trip time of the network plus the time to switch to the destination process, then the sender can infer that the other processes in this job are probably not currently scheduled. Consequently, this process should relinquish the processor by going to sleep.
  2. If a process receives a message, it can infer that other processes in this application are currently scheduled. consequently, this process should also be scheduled (in some circumstances). The previous simulations found that waking up processes waiting for message responses was sufficient; it was not necessary to schedule processes waiting in the ready queue.

Our implementation and simulation work has shown that implicit cocheduling schedules both coarse- and fine-grain bulk-synchronous parallel applications with nearly the same performance as an idealistic version of explicit coscheduling.

Implicit coscheduling is particularly appropriate for NOWs because it has many of the advantages of explicit coscheduling, without the disadvantages. For example, unlike traditional coscheduling, the implicit version is completely distributed, requiring no global coordination; it has potential for working well with a mix of parallel and interactive jobs and parallel jobs performing I/O; and, finally, it does not require that communicating processes are statically identified.


For More Information:

Background:

Check out our scheduling bibliography! You will find references to other papers addressing scheduling.


This page maintained by dusseau@cs.berkeley.edu