Presentation accepted for ASHPC’21

The presentation has been accepted to the main-track of the Austrian-Slovenian HPC Meeting (ASHPC’21). Meeting will be organized in a hybrid format on 31 May – 2 June, 2021 at the Institute of Information Science in Maribor, Slovenia.

Title: Automated Workflows Scheduling via Two-Phase Event-based MILP Heuristic for MRCPSP Problem

Authors: Vladislav Kashansky, Gleb Radchenko, Radu Prodan, Anatoliy Zabrovskiy and Prateek Agrawal

Abstract: In today’s reality massive amounts of data-intensive tasks are managed by utilizing a large number of heterogeneous computing and storage elements interconnected through high-speed communication networks. However, one issue that still requires research effort is to enable effcient workflows scheduling in such complex environments.
As the scale of the system grows and the workloads become more heterogeneous in the inner structure and the arrival patterns, scheduling problem becomes exponentially harder, requiring problem-specifc heuristics. Many techniques evolved to tackle this problem, including, but not limited to Heterogeneous Earliest Finish Time (HEFT), The Dynamic Scaling Consolidation Scheduling (DSCS), Partitioned Balanced Time Scheduling (PBTS), Deadline Constrained Critical Path (DCCP) and Partition Problem-based Dynamic Provisioning Scheduling (PPDPS). In this talk, we will discuss the two-phase heuristic for makespan-optimized assignment of tasks and computing machines on large-scale computing systems, consisting of matching phase with subsequent event-based MILP method for schedule generation. We evaluated the scalability of the heuristic using the Constraint Integer Programing (SCIP) solver with various configurations based on data sets, provided by the MACS framework. Preliminary results show that the model provides near-optimal assignments and schedules for workflows composed of up to 100 tasks with complex task I/O interactions and demonstrates variable sensitivity with respect to the scale of workflows and resource limitation policies imposed.

Keywords: HPC Schedule Generation, MRCPSP Problem, Workflows Scheduling, Two-Phase Heuristic

Acknowledgement: This work has received funding from the EC-funded project H2020 FETHPC ASPIDE (Agreement #801091)