Multi-objective Bayesian optimization algorithm for real-time task scheduling on heterogeneous multiprocessors

摘要

In this paper, we have proposed a Bayesian optimization based novel approach for multi-objective task scheduling in real-time heterogeneous multiprocessor systems. Task scheduling problem in multi-processor real-time systems is a NP-hard problem. In such systems, scheduling of tasks becomes a huge challenge for the scheduler designers; especially when tasks are inter-dependent and have deadline constraints. Interdependent or precedence-constrained tasks are often represented as directed acyclic graphs. Most of the real life applications require state of the art planning and scheduling schemes for safer and efficient operations. Thus, we propose the algorithm `moBOA-RTS' (multi-objective Bayesian optimization algorithm for real time scheduling) to find an optimal schedule satisfying all the constraints within reasonable time. Here, learning of task graph is made through Bayesian networks. At first, tasks are allocated to different processors and then LDF (latest deadline first) based priority is used to determine the task execution on individual processors. The proposed approach can be applied on many processor real-time systems, where both the scenarios viz. homogenous and heterogeneous processing environments are prevalent. Experimental analysis shows that our approach produces optimal decisions for feasible scheduling that ensures the compliance of all real time and precedence related constraints.