An experimental study of scheduling algorithms for many-task applications

• Published in: The Journal of supercomputing 2019-12, Vol.75 (12), p.7857-7871
• Main Authors: Sukhoroslov, Oleg, Nazarenko, Alexey, Aleksandrov, Roman
• Format: Article
• Language: English
• Subjects: Algorithms; Compilers; Computer networks; Computer Science; Computer simulation; Dependence; Discrete event systems; Distributed processing; Experiments; Interpreters; Mathematical models; Model accuracy; Processor Architectures; Programming Languages; Scheduling; Simulation; Task scheduling
• ISSN: 0920-8542; 1573-0484
• DOI: 10.1007/s11227-018-2553-9

The paper studies the performance of algorithms for scheduling of many-task applications in distributed computing systems. Two important classes of such applications are considered: bags-of-tasks and workflows. The comparison of algorithms is performed on the basis of discrete-event simulation for various application cases and system configurations. The developed simulation framework based on SimGrid toolkit provides the necessary tools for implementation of scheduling algorithms, generation of synthetic systems and applications, execution of simulation experiments and analysis of results. This allowed to perform a large number of experiments in a reasonable amount of time and to ensure reproducible results. The conducted experiments demonstrate the dependence of the performance of studied algorithms on various application and system characteristics. While confirming the performance advantage of advanced static algorithms, the presented results reveal some interesting insights. In particular, the accuracy of the used network model helped to demonstrate the limitations of simple analytical models for scheduling of data-intensive parallel applications with static algorithms.