On clustering DAGs for task-hungry computing platforms
Open Access
- 1 January 2011
- journal article
- Published by Walter de Gruyter GmbH in Open Computer Science
- Vol. 1 (1)
Abstract
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.Keywords
This publication has 12 references indexed in Scilit:
- Extending IC-scheduling via the Sweep AlgorithmJournal of Parallel and Distributed Computing, 2010
- On scheduling dags to maximize area2009
- Advances in IC-Scheduling Theory: Scheduling Expansive and Reductive Dags and Scheduling Dags via DualityIEEE Transactions on Parallel and Distributed Systems, 2007
- A Tool for Prioritizing DAGMan Jobs and its EvaluationJournal of Grid Computing, 2007
- Applying IC-Scheduling Theory to Familiar Classes of Computations2007
- Toward a theory for scheduling dags in Internet-based computingIEEE Transactions on Computers, 2006
- Guidelines for Scheduling Some Common Computation-Dags for Internet-Based ComputingIEEE Transactions on Computers, 2005
- On scheduling mesh-structured computations for Internet-based computingIEEE Transactions on Computers, 2004
- A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessorsJournal of Parallel and Distributed Computing, 1992
- A linear filtering approach to the computation of discrete Fourier transformIEEE Transactions on Audio and Electroacoustics, 1970