Abstract:
Scheduling parallel tasks is one of the fundamental challenges in the field of high-performance computing, distributed systems, and cloud technologies. This problem belongs to the NP-hard class, which excludes the possibility of obtaining an accurate optimal solution for large input data in polynomial time. Therefore, researchers pay special attention to approximate, heuristic and metaheuristic methods that provide acceptable quality solutions in a reasonable time. The article provides an overview of existing approaches to planning: from classical heuristic algorithms (HEFT, CPOP, PEFT, DSC) and metaheuristics (genetic algorithms, ant colonies, swarm intelligence) to dynamic methods (work-stealing, gang scheduling), industrial planners (Borg, Omega, Mesos, Kubernetes) and the latest solutions based on machine learning and reinforcement learning (Decima, RL approaches). The issues of orchestration — lifecycle management of applications and containers in cloud environments are considered. The connection of theoretical models with real industrial systems such as Google Borg, Apache Mesos and Kubernetes, which have become industry standards, is emphasized. Attention is paid to test benchmarks, traces from real data centers (Google Borg, Microsoft Azure), as well as open problems and prospects for further research.
Fulltext:
PDF file (369 kB)