Efficient workflow scheduling is a key problem in large-scale computing systems, as it directly impacts performance, resource utilization, and resilience. This work considers checkpointing strategies for the scheduling of workflows composed of moldable tasks that are subject to silent errors. We build upon three state-of-the-art scheduling and mapping algorithms for moldable task graphs in an error-free environment (Linprog, PropMap, and CPA13), and we extend them in several directions to mitigate the impact of silent errors. We design new allocation and mapping strategies that prevent both under-checkpointing and over-checkpointing of tasks. We run an extensive set of simulations with several task speedup profiles, where our new algorithm CkptRight achieves important gains over CkptCrossover, the baseline extension of the error-free algorithms, and over two natural competitor strategies, CkptAll (checkpoint all tasks) and CkptNone (checkpoint no task). CkptRight achieves a success rate of over 99% over all simulation scenarios, while CkptCrossover and CkptAll have a rate around 94%, and CkptNone less than 41%. In addition, we achieve an average gain of 23% over CkptCrossover and CkptAll whenever both do not time out. The accuracy of the simulations is confirmed by the comparison with experiments conducted on a multicore platform. All these results demonstrate the robustness and efficiency of CkptRight.
en
Research Areas:
Computer Science Foundations: 50% Modeling and Simulation: 50%
