Memory-Aware Workflow Scheduling for Shared-Disk Clusters: New Model, Heuristics, and Regression-based Selection

Scientific workflows consist of interdependent tasks whose memory requirements may exceed the available memory on the nodes of a distributed system. When a memory limit is exceeded, pages must be transferred to disk to make space for new content. For this, we investigate a shared-disk model; like real hardware, its disk transfers are significantly slower than memory. We distinguish three transfer strategies: (i) system-initiated swapping, (ii) algorithm-initiated file offloading, and (iii) algorithm-initiated preemptive writing.To execute the workflow as fast as possible (i.e., minimize its makespan), its tasks need to be scheduled effectively. To this end, we propose MeDiH, a memory-aware variant of the popular HEFT algorithm that exploits offloading and preemptive writing. We investigate five offline heuristic variants with different task-ranking methods, alongside five online counterparts designed to account for deviations between assumed and actual task and file transfer duration. Experimental results show that the best heuristic depends on various workflow parameters and deviation levels. For real-world workflows in static settings, the best heuristic improves the baseline makespans by 81.5% on average and remains a top performer under deviations. However, in other settings (for instance, with small edge weights), other variants perform significantly better. As no single method fits all cases, we propose a regression-based ML model that selects the best variant based on workflow properties. It achieves a median quality loss of only 0.36 compared to a perfect selection, demonstrating that our automatic selection is nearly loss-free.