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

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

David Vengerov, Lykomidis Mastroleon, Declan Murphy, Nick Bambos

23 April 2007

This paper 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 onto 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 methodology 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 methodology. Our simulation results demonstrate the feasibility of this approach and show that it performs better than the best heuristic scheduling policy we could find for this domain.


Venue : N/A