Maximizing Workflow Throughput for Streaming Applications in Distributed Environments

• Main Authors: Yi Gu, Qishi Wu
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm design and analysis; Complexity theory; Computational modeling; Computer networks; Network topology; Stability analysis; Steady-state
• ISSN: 1095-2055; 2637-9430
• DOI: 10.1109/ICCCN.2010.5560146

Large-scale computation-intensive applications in various science fields feature complex DAG-structured workflows comprised of distributed computing modules with intricate intermodule dependencies. Mapping such workflows in heterogeneous network environments and maximizing their throughput are crucial to the success of large-scale scientific applications that process streaming datasets. We construct analytical cost models and formulate workflow mapping as an optimization problem for maximum frame rate. The difficulty of this problem essentially arises from the topological matching nature in the spatial domain, which is further compounded by the resource sharing complicacy in the temporal dimension if multiple modules are deployed on the same node. We conduct a rigorous workflow stability analysis and design a workflow mapping scheme based on a topological layer-oriented dynamic programming solution to identify and minimize the global bottleneck. The performance superiority of the proposed mapping scheme is illustrated by extensive simulation-based comparisons with existing algorithms.