On Clustering Tasks in IC-Optimal Dags

Strategies are developed for "fattening" the tasks of computation-dags so as to accommodate the heterogeneity of remote clients in Internet-based computing (IC). Earlier work has developed the underpinnings of IC-scheduling theory, an algorithmic framework for scheduling computations having intertask dependencies for IC. The theory\´s schedules strive to render tasks eligible for execution at the maximum possible rate, so as to: (a) utilize remoteclients\´ computational resources well, by enhancing the likelihood of having work to allocate to an available client; (b) lessen the likelihood of a computation\´s stalling for lack of tasks that are eligible for allocation. The current study begins to enhance IC-scheduling theory so that it can accommodate the varying computational resources of remote clients. The techniques developed here render a dag multi-granular by clustering its tasks. Several clustering strategies are developed: one works for any dag but produces only a limited variety of "fattened" tasks; others exploit the detailed structure of the dag being scheduled but allow a broad range of "fattened" tasks.