Scheduling Δ-critical tasks in mixed-parallel applications on a national grid

Mixed-parallel applications can take advantage of large-scale computing platforms but scheduling them efficiently on such platforms is challenging. When relying on classic list-scheduling algorithms, the issue of independent and selfish task allocation determination may arise. Indeed the allocation of the most critical task may lead to poor allocations for subsequent tasks. In this paper we propose a new mixed-parallel scheduling heuristic that takes into account that several tasks may have almost the same level of criticality during the allocation process. We then perform a comparison of this heuristic with other algorithms in simulation over a wide range of application and on platform conditions. We find that our heuristic achieves better performance in terms of schedule length, speedup and degradation from best.