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:

• Scheduling with Implicit Information in Distributed Systems
  Andrea C. Arpaci-Dusseau, David E. Culler, Alan Mainwaring.
  To appear in Sigmetrics'98 Conference on the Measurement and Modeling of Computer Systems,
  Available as: Abstract, Compressed Postscript, Postscript and Slides
  

• Effective Distributed Scheduling of Parallel Workloads
  Andrea C. Dusseau, Remzi H. Arpaci, David E. Culler.
  In Sigmetrics'96 Conference on the Measurement and Modeling of Computer Systems, Philadelphia, PA, May 1996.
  Available as: Abstract, Compressed Postscript, Postscript and Slides

• Simulation Data
  Data from simulation experiments in Sigmetrics'96 paper.

• Extending Proportional-Share Scheduling to a Network of Workstations
  Andrea C. Arpaci-Dusseau, David E. Culler.
  In International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'97) , Las Vegas, Nevada, June 1997.
  Available as: Abstract and PostScript
  

Background:

• Communication-Driven Scheduling: Incorporating Parallel Jobs into the UNIX Environment
  Talk given by Andrea C. Dusseau at U.C. Berkley Castle Retreat, July, 1995.
  Available as: Slides

• Re-examining Scheduling and Communication in Parallel Programs
  Andrea C. Dusseau, Remzi H. Arpaci, David E. Culler.
  Computer Science Technical Report: UCB//CSD-95-881
  Available as: Postscript

• The Interaction of Parallel and Sequential Workloads on a Network of Workstations
  Remzi H. Arpaci, Andrea C. Dusseau, Amin M. Vahdat, Lok T. Liu, Thomas E. Anderson, David A. Patterson.
  In SIGMETRICS '95 , 1995.
  Available as: Abstract, PostScript, and Slides

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