On clustering DAGs for task-hungry computing platforms

Many modern computing platforms are "task-hungry": Their performance is enhanced by always having as many tasks available for execution as possible. IC-scheduling, a master-worker framework for executing static computations that have intertask dependencies (modeled as dags), was developed with precisely the goal of rendering a computation-dag's tasks eligible for execution at the maximum possible rate. The current paper addresses the problem of enhancing IC-scheduling so that it can accommodate the varying computational resources of different workers, by clustering a computation-dag's tasks, while still producing eligible (now, clustered) tasks at the maximum possible rate. The task-clustering strategies presented exploit the structure of the computation being performed, ranging from a strategy that works for any dag, to ones that build increasingly on the explicit structure of the dagbeing scheduled.