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.
SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/