TY - JOUR

T1 - Multi-agent Reinforcement Learning based Adaptive Heterogeneous DAG Scheduling

AU - Петросян, Ованес Леонович

AU - Жадан, Анастасия Юрьевна

AU - Аллахвердян, Александр Львович

AU - Кондратов, Иван Владимирович

AU - Михеев, Викентий Сергеевич

AU - Romanovskii, Aleksei

AU - Kharin, Vitaliy

PY - 2023/10/3

Y1 - 2023/10/3

N2 - Static scheduling of computational workflow represented by a directed acyclic graph (DAG) is an important problem in many areas of computer science. The main idea and novelty of the proposed algorithm is an adaptive heuristic or graph metric which uses a different heuristic rule at each scheduling step depending on local workflow. It is also important to note that multi-agent reinforcement learning is used to determine scheduling policy based on adaptive metrics. In order to prove the efficiency of the approach a comparison with the state-of-the-art DAG scheduling algorithms is provided: DONF, CPOP, HCPT, HPS and PETS. Based on the simulation results the proposed algorithm shows the improvement of up to 30% on specific graph topologies, and average performance gain of 5.32% compared to the best scheduling algorithm DONF(suitable for large-scale scheduling) on large number of random DAGs. Another important result is that using the proposed algorithm it was possible to cover 30.01% of the proximity interval from the best scheduling algorithm to the global optimal solution. This indicates that the idea of an adaptive metric for DAG scheduling is important and requires further research and development.

AB - Static scheduling of computational workflow represented by a directed acyclic graph (DAG) is an important problem in many areas of computer science. The main idea and novelty of the proposed algorithm is an adaptive heuristic or graph metric which uses a different heuristic rule at each scheduling step depending on local workflow. It is also important to note that multi-agent reinforcement learning is used to determine scheduling policy based on adaptive metrics. In order to prove the efficiency of the approach a comparison with the state-of-the-art DAG scheduling algorithms is provided: DONF, CPOP, HCPT, HPS and PETS. Based on the simulation results the proposed algorithm shows the improvement of up to 30% on specific graph topologies, and average performance gain of 5.32% compared to the best scheduling algorithm DONF(suitable for large-scale scheduling) on large number of random DAGs. Another important result is that using the proposed algorithm it was possible to cover 30.01% of the proximity interval from the best scheduling algorithm to the global optimal solution. This indicates that the idea of an adaptive metric for DAG scheduling is important and requires further research and development.

UR - https://www.mendeley.com/catalogue/640b49ca-1ff8-341a-880d-65673b8edf74/

U2 - 10.1145/3610300

DO - 10.1145/3610300

M3 - Article

VL - 14

JO - ACM Transactions on Intelligent Systems and Technology

JF - ACM Transactions on Intelligent Systems and Technology

SN - 2157-6904

IS - 5

M1 - 87

ER -