SPECIAL SDI SEMINAR - THESIS DEFENSE

DATE: Thursday, December 16, 2004
TIME: 11:30 am (note special time)
PLACE: HH D-210

SPEAKER:
David Petrou
CMU

TITLE:
Cluster Scheduling for Explicitly-Speculative Tasks

ABSTRACT:
Large-scale computing often consists of many speculative tasks to test hypotheses, search for insights, review potentially finished products. For example, speculative tasks are issued by bioinformaticists comparing DNA sequences, computer graphics artists rendering scenes, and computer researchers studying caching. This behavior—exploratory searches and parameter studies, made more common by the
cost-effectiveness of cluster computing—on existing schedulers without speculative task support results in a mismatch of goals and suboptimal scheduling. Users wish to reduce their time waiting for needed task output and the amount they will be charged for unneeded speculation, making it unclear to the user how many speculative tasks they should submit.

This thesis introduces `batchactive' scheduling (combining batch and interactive characteristics) that exploits the inherent speculation in common application scenarios. With a batchactive scheduler, users submit explicitly-labeled batches of speculative tasks exploring ambitious lines of inquiry, and users interactively request task outputs when these outputs are found to be needed. After receiving and considering an output for some time, a user decides whether to request more outputs, cancel tasks, or disclose new speculative tasks. Over a broad range of realistic simulated user behavior and task characteristics, I show that under a batchactive scheduler visible response time is improved by at least a factor of two for 20% of the simulations. I identify the role of think time in speculative scheduling, characterize the scenarios in which batchactive scheduling provides significant benefits, and remove an obstacle to speculation with an incentive pricing mechanism.

For Further Seminar Info Contact:
or visit http://www.pdl.cmu.edu/SDI/