Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Advanced in a Dag-Scheduling Theory for Internet-Based Computing

SpeakerGennaro Cordasco

Earlier work has developed the underpinnings of a theory of scheduling computations having intertask dependencies - modeled via dags - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate. This goal aims:

  • to utilize remote clients' computational resources well, by always having work to allocate to an available client;
  • to lessen the likelihood of the "gridlock" that ensues when a computation stalls for lack of eligible tasks.

The theory crafts a schedule for a given dag G by "parsing" G (if possible) into connected bipartite building-block dags (CBBBs, for short) that one can "compose" to form G and then analyzing the scheduling dependencies among these CBBBs. We extend the theory by developing an algorithmic tool that allows one to expand the theory's repertoire of building blocks, both via new classes of CBBBs, and by allowing one to add classes of bipartite building-block dags that are not necessarily connected.