为提高计算效率,将复杂的大规模任务分解为简单任务并建模为工作流,交由并行分布式计算集群来完成,已成为云中心处理持续增长的计算和网络任务的重要手段。然而,分布式计算的任务间数据传输所带来的通信带宽占用却容易造成云中心的网络拥塞。如何兼顾计算效率和通信开销,科学地部署工作流意义重大。两类典型的工作流部署算法为基于列表的部署算法和基于分簇的部署算法。然而,前者致力于提高计算效率,未关注工作流中任务之间的通信开销,大规模工作流的部署易带来较重的网络负荷;后者关注通信开销的最小化,但牺牲了工作流中任务的并行计算效率,导致工作流完成时间较长。文中从图论的角度出发,充分挖掘工作流中各任务之间的依赖性和并行性,通过对经典图分割算法进行改进,实现了工作流任务分区过程中通信开销最小化和计算并行性最大化之间的平衡。仿真结果表明,在不同的工作流规模下,所提算法的通信开销比列表部署算法平均减少约35%~50%,工作流完成时间比分簇部署算法平均降低约50%~65%,且对于具有不同通信计算比的工作流均具有良好的稳定性。
