Performance Analysis and Optimization of Distributed Workflows in Heterogeneous Network Environments

摘要

Large-scale e-science features complex DAG-structured workflows comprised of computing modules with intricate inter-module dependencies. Mapping such workflows in heterogeneous network environments and optimizing their end-to-end performance are crucial to the success of scientific collaborations that require fast system response and smooth data flow. We construct analytical cost models and formulate workflow mapping as optimization problems for minimum end-to-end delay and maximum frame rate. The difficulty of these problems essentially arises from the topological matching nature in the spatial domain, which is further compounded by the resource sharing complicacy in the temporal dimension. For unitary processing applications, we develop a workflow mapping algorithm based on a recursive critical path optimization procedure to minimize the latency; while for streaming applications, we conduct a rigorous workflow stability analysis and develop a layer-oriented dynamic programming solution based on topological sorting to identify and minimize the global bottleneck time. The accuracy of the proposed exact delay calculation algorithm is verified in comparison with an approximate solution, a dynamic distributed system simulation program, and a real network deployment, and the performance superiority of the proposed mapping approaches are illustrated by extensive simulation-based comparisons with existing algorithms and verified by large-scale experiments on real-life scientific workflows through effective system implementation and deployment in real networks.