Proceedings 18th Annual ACM International Conference on Supercomputing (ICS’04), June 26-July 1, 2004, Malo, France.
David Petrou, Gregory R. Ganger, Garth A. Gibson*
Deptartment of Electrical & Computer Engineering
*School of Computer Science
Carnegie Mellon University
http://www..pdl.cmu.edu/batchactive/
Large-scale computing often consists of many speculative tasks to test hypotheses, search for insights, and review potentially finished products. E.g., speculative tasks are issued by bioinformaticists comparing DNA sequences and computer graphics artists adjusting scene properties. We promote a way of working that exploits the inherent speculation in application-level search made more common by the cost-effectiveness of grid and cluster computing. Researchers and end-users disclose sets of speculative tasks that search an application space, request specific results as needed, and cancel unfinished tasks if early results suggest no need to continue. Doing so matches natural usage patterns, making users more effective, and also enables a new class of schedulers.
In simulation, we show how batchactive schedulers reduce user-observed response times relative to conventional models in which tasks are requested one at a time (interactively) or in batches without specifying which tasks are speculative. Over a range of situations, user-observed response time is about 50% better on average and at least two times better for 20% of our simulations. Moreover, we show how user costs can be reduced under an incentive cost model of charging only for tasks whose results are requested.
KEYWORDS: speculative, optimistic, cluster, grid scheduling
FULL PAPER: pdf