A Hybrid Mapping and Scheduling Algorithm for Distributed Workflow Applications in a Heterogeneous Computing Environment

摘要

Computing intensive scientific workflows structured as a directed acyclic graph (DAG) are widely applied to various distributed science and engineering applications to enable efficient knowledge discovery by automated data processing. Effective mapping and scheduling the workflow modules to the underlying distributed computing environment with heterogeneous resources for optimal network performance has remained as a challenge and attracted research efforts with many simulations and real experiments carried out in the grid and cloud infrastructures. Due to the computing intractability of this type of optimization problem, heuristic algorithms are commonly proposed to achieve the minimum end-to-end delay (EED) or other objectives such as maximum reliability and stability. In this paper, a Hybrid mapping algorithm combining Recursive Critical Path search and layer-based Priority techniques (HRCPP) is designed and developed to achieve the minimum EED. Four representative mapping and scheduling algorithms for minimum EED are compared with HRCPP. Our simulation results illustrate that HRCPP consistently achieves the smallest EED with a low algorithm running time observed from many different scales of simulated test cases.