Task scheduling using Bayesian optimization algorithm for heterogeneous computing environments

• Published in: Applied soft computing 2011-06, Vol.11 (4), p.3297-3310
• Main Authors: Yang, Jiadong, Xu, Hua, Pan, Li, Jia, Peifa, Long, Fei, Jie, Ming
• Format: Article
• Language: English
• Subjects: Bayesian optimization algorithm; Heterogeneous; Multiprocessor scheduling; Parallel computing
• ISSN: 1568-4946; 1872-9681
• DOI: 10.1016/j.asoc.2010.11.029

Efficient task scheduling, as a crucial step to achieve high performance for multiprocessor platforms, remains one of the challenge problems despite of numerous studies. This paper presents a novel scheduling algorithm based on the Bayesian optimization algorithm (BOA) for heterogeneous computing environments. In the proposed algorithm, scheduling is divided into two phases. First, according to the task graph of multiprocessor scheduling problems, Bayesian networks are initialized and learned to capture the dependencies between different tasks. And the promising solutions assigning tasks to different processors are generated by sampling the Bayesian network. Second, the execution sequence of tasks on the same processor is set by the heuristic-based priority used in the list scheduling approach. The proposed algorithm is evaluated and compared with the related approaches by means of the empirical studies on random task graphs and benchmark applications. The experimental results show that the proposed algorithm is able to deliver more efficient schedules. Further experiments indicate that the proposed algorithm maintains almost the same performance with different parameter settings.