A reinforcement learning based job scheduling algorithm for heterogeneous computing environment. (April 2023)

• Record Type: Journal Article
• Authors: Song, Yutao; Li, Chen; Tian, Lihua; Song, Hui
• Is Part Of: Computers & electrical engineering. Volume 107(2023)
• Publication Date: 2023-04
• Subjects: DAG scheduling -- Heterogeneous computing environment -- Graph convolution network -- Reinforcement learning -- Heuristics; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2023.108653
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: Efficient job scheduling for heterogeneous computing environments has attracted widespread attention, jobs are usually modeled as directed acyclic graphs(DAG). Optimizing scheduling can improve system throughput. We propose a two-stage scheduling algorithm, which calculates task selection and processor allocation respectively. In task selection stage, we utilize a bidirectional graph convolution network to learn DAG structural features, and a fully-connected network to generate proper scheduling scheme. In the processor allocation stage, we propose a heuristic based on optimistic cost table(OCT) and task duplication, which trade-off scheduling allocation better. Experiments of various scheduling scenarios have been conducted, and the results show that the proposed algorithm has better scheduling performance than the compared heterogeneous DAG scheduling algorithms. Graphical abstract: Highlights: Heuristic algorithms face performance bottlenecks in complex scheduling scenarios with multiple concurrent jobs. We construct a neural network agent trained by reinforcement learning to handle scheduling. We propose a bidirectional graph convolution network to learn the global structure information of the job graph. We improve the global gains of task allocation by estimating the cost of unassigned task. The proposed algorithm's effciency surpasses mainstream method in heterogenous multi-job environment.