论文部分内容阅读
随着大数据时代的到来,基于大规模数据的信息分析和数据挖掘技术逐渐适用于众多领域。对于大规模数据处理的编程模型以及计算效率的需求一直是研究领域的热点问题之一。其中,数据并行(Data-Parallel)的处理模型(如Map-Reduce等分布式编程框架)的提出与优化,在过去的几年中为大规模数据的并行处理提供了重要的支持;然而,随着搜索与分析等需求的语义化,数据分析的应用场景也不断增多,机器学习与数据挖掘技术的兴起,也使得分布式应用的算法趋向于复杂化,主要体现为计算的过程在单元数据的顺序计算的基础上增加了迭代性与关联性。因此,图并行(Graph-Parallel)的处理模型被提出,并逐渐成为大数据时代的下一个研究重点。大规模图并行处理模型的设计本质上具有迭代与收敛的计算特性:输入数据以一个单元的顶点结构为中心,单元数据之间的关联性被抽象为图结构中的边,每个顶点根据边的依赖关系不断进行信息传递与迭代计算,直到达到平衡的收敛状态。由于图并行处理模式的这种计算特性,在实现时具有同步(Sync)与异步(Async)两种不同的迭代调度模式。而这两种调度模式在顶点计算的调度顺序、调度层的管理结构以及硬件和网络资源的利用率等方面都具有显著的差异。然而,现阶段基于这两种调度模式的比较与分析的相关研究仍然十分稀缺,在实际的图并行处理应用的开发中,图计算编程人员通常需要根据经验选择同步或异步调度模式其中之一。这不仅要求编程人员对于图并行编程框架的底层实现具有深入的理解,也使得图并行应用的计算性能无法得到最优的保障。基于这些问题,本文主要进行了以下几个方面的研究:首先,我们基于同步和异步两种调度模式的经典实现框架与一系列典型的图并行计算的应用,创新性地对这两种调度模式的特性和性能表现进行了深入的对比分析与归纳。我们的研究通过详细的性能测试,展示了这两种调度模式在不同的图并行处理算法、不同的图划分算法、不同的计算执行阶段、不同的输入数据以及不同的集群性能配置等情况下,具有显著的性能表现差异。同时,我们归纳和总结了不同情况下调度模式选择的倾向性,并发现了潜在的性能提升空间。其次,本文提出了Hsync模式——一种自适应切换于同步与异步调度方式之间的启发式的图并行处理调度模式,从而尝试达到图并行处理应用在性能表现上的最优化。Hsync模式会在应用的计算过程中持续地收集执行时的系统状态,结合启发式的判断策略,预测同步与异步两种调度方式的执行性能,判断是否应该进行状态转换从而切换到一个更优的调度方式继续执行。本文的研究在经典的分布式图并行计算框架——PowerGraph框架的基础上进行了修改和扩展,实现了支持Hsync调度模式的PowerSwitch系统。该实现的核心主要包括了调度方式转换的支持模块,以及用于预测两种方式的调度性能的在线和线下的采样分析模块,并归纳总结了一系列的启发式判断规则。此外,我们的研究基于一个48个节点的分布式集群配置,对于PowerSwitch系统进行了详细的性能评测。评测显示,我们系统的计算性能优于同配置下的同步或异步的单一调度模式。通过调度方式的转换,PowerSwitch系统在相较于同步或异步中最优的调度模式的基础上,能够额外获得9%到73%的性能提升。