Adaptive Data-Aware Utility-Based Scheduling in Resource-Constrained Systems

by David Vengerov, Lykomidis Mastroleon, Declan Murphy, and Nick Bambos.

April 24, 2007 - Scheduling in High Performance Computing (HPC) systems is becoming an increasingly important and difficult task. Most of the HPC jobs need to access some data stored on local disk or remote storage, and some jobs need to access very large amounts of data, especially in applications such as high-energy physics, natural language processing, astronomy, and bioinformatics. The amount of data processed by scientific applications has been increasing exponentially since 1990, at an even faster rate than predicted by the Moore's law. Thus, efficient data-aware scheduling will become a critical issue in scientific computing in the very near future.

This technical report addresses the problem of dynamic scheduling of data-intensive multiprocessor jobs. Each job requires some number of CPUs and some amount of data that needs to be downloaded into a local storage space before starting the job. The completion of each job brings some benefit (utility) to the system, and the goal is to find the optimal scheduling policy that maximizes the average utility per unit of time obtained from all completed jobs. A co-evolutionary solution framework is proposed, where the utility-based policies for managing local storage and for scheduling jobs onto the available CPUs mutually affect each other's environments, with both policies being adaptively tuned using the Reinforcement Learning process.

The presented solution framework can apply (with suitable modifications to the state variables) to improving performance of any computing system that uses a local cache to speed up execution of some jobs. More generally, the distributed co-evolutionary aspect of this framework makes it applicable to a greater class of job shop scheduling problems, where a scheduler is used at each stage of the process to perform some processing on the jobs, which implicitly affects the ordering in which the jobs become available for the next stage.

More Links