One of today’s challenges for achieving high performance on grid applications is that of scheduling, which is the decision process by which application components (computation, communication, data) are assigned to grid resources (CPUs, network, storage). Scheduling has been studied by many researchers in the context of grid applications and grid platforms, and many variants of the problem in parallel, distributed, and grid environments are known to be NP-hard. Heuristics are therefore used extensively, typically run over the entire grid universe. Since few applications can productively use the entire grid (i.e. millions of resources), this scheduling implicitly selects a subset of the grid resources (i.e. the dozens or hundreds that are assigned application components). However, even with polynomial complexity, these methods run on grids with millions of resources can account for a significant fraction of the application’s execution time (especially when network connectivity is taken into account by the heuristic). Moreover, it may not be possible to gather all the resource information needed by a scheduling algorithm in a scalable manner. In short, traditional heuristic scheduling on the full grid is not scalable.

Our Virtual Grid (VG) abstraction provides a novel and powerful way to approach application scheduling by decoupling the scheduling activity from resource discovery, resource selection, and resource binding. The general VGrADS approach lets the user/application specify its resource needs to the Virtual Grid Execution System (vgES) and, using efficient Find-and-Bind techniques, quickly and accurately generates a VG. At that point, the scheduling heuristic can be executed just over the resources within the VG, which is exponentially less costly than looking at the whole resource universe. Our claim is that simple scheduling algorithms are sufficient to achieve good workflow performance, if they operate across an intelligently pruned resource universe implemented through VGs. Alternately, this two-phase approach opens the door to investigating the use of more costly but more effective heuristics on the pruned resource set. The Execution System and Programming Tools groups have collaborated on this investigation; the scheduling page under Programming Tools gives some specific results.

Decoupling scheduling from resource discovery is a natural idea that has been validated in several research projects (including our own prior work). In addition to decoupling resource selection from scheduling, the VG abstraction also decouples resource binding from scheduling since resources in a VG are already bound to the application when the VG is instantiated. This makes it possible to have the vgES deal with the diversity of local resource managers and resource management policies, as well as with unreachable resources, so that application scheduling can be done with simple resource access and availability models.  This is radically different from state-of-the-art application scheduling and is another major capability for enabling effective grid application scheduling in large-scale systems.