Scheduling under conditions of uncertainty: a bayesian approach

Abstract

The efficient execution of irregular parallel applications on shared distributed systems requires novel approaches to scheduling, since both the application requirements and the system resources exhibit an unpredictable behavior. This paper proposes Bayesian decision networks as the paradigm to handle the uncertainty a scheduler has about the environment's current and future states. Experiments performed with a parallel ray tracer show promising performance improvements over a deterministic approach of identical complexity. These improvements grow as the level of system sharing and the application's workload irregularity increase, suggesting that the effectiveness of decision network based schedulers grows with the complexity of the environment being managed.