应用特征驱动的迭代处理优化机制研究

发布时间：2017-12-23 14:24

本文关键词：应用特征驱动的迭代处理优化机制研究　出处：《华中科技大学》2016年博士论文　论文类型：学位论文

【摘要】：迭代算法是指那些对初始输入数据集进行多轮反复处理寻找所需近似解或者精确解的算法。它在早期用于数值分析中线性方程组和微分方程等方面的近似求解。经过几十年的发展,迭代算法现已广泛应用于数据挖掘、机器学习和科学模拟等领域。在大数据时代,各行各业所产生的数据呈爆炸式增长,如何有效支持大规模迭代算法,快速挖掘海量数据背后潜在的商业或科学价值,已成为目前急需解决的重要任务。为了有效支持迭代算法,目前国内外学者已初步提出多个迭代处理系统。然而,迭代算法种类多样,各具特征。其中可异步性特征和幂律依赖关系图(Power-law Dependency Graph,简称PDG)特征对迭代算法性能影响最大。可异步性特征指迭代算法在消除各迭代层次之间的同步之后仍能收敛到其所需结果。具有此特征的迭代算法常称作异步迭代算法,反之则称作同步迭代算法。PDG特征指迭代算法的数据依赖关系图中各图顶点度数服从幂函数分布。由于现有方法没有考虑到迭代算法的多样性,各类迭代算法的高效运行可能分别面临着收敛速度慢、开销高、计算倾斜和通信倾斜等问题。具体体现为：1)具有PDG特征的异步迭代算法面临慢速的数据状态传递而收敛速度欠佳；2)异步迭代算法在投机运行时会面临冗余计算开销和冗余通信开销;3)具有PDG和不具有PDG特征的同步迭代算法将分别面临不同原因导致的计算倾斜；4)同步迭代算法由于各迭代层次之间的全局同步而面临网络抖动和计算倾斜负面影响累积问题。为了解决这些挑战,提出多个针对性的优化机制对运行时系统进行相应优化,有效支持各类典型迭代算法的执行。针对具有PDG特征的异步迭代图算法,提出基于核心图的异步图处理优化机制,解决其收敛速度慢的问题。由于PDG特征,此类算法中有部分重要图顶点。其状态传递速度决定整个算法收敛所需时间。然而,采用目前策略,重要图顶点之间的状态难于快速传递,导致其收敛速度无法达到最优。分析发现,异步图处理有级联效应,允许图顶点状态沿路径快速传递。基于此事实,为加快收敛速度,该机制将各图划分块中重要的图顶点以及它们之间的路径包含在核心图中,加快重要状态在各图划分块之间的推送。然后,它采用交替式策略处理各图划分块,根据图顶点在各路径上的排列顺序,以顺序-逆序交替的方式处理它们,使重要状态快速地在各图划分块内扩散。针对异步迭代算法,提出基于组执行模型的冗余开销控制机制,减少其投机运行中的冗余开销。分析发现,异步迭代算法允许合并和调度其中间结果数据。基于此特性,该机制以组的形式对中间结果数据进行管理、调度和处理,避免它们分别触发后续通信和计算。该机制通过权值的定义和中间结果数据处理顺序的调度,在投机运行带来的利益和开销之间进行折中,以获得最佳性能。针对不具有PDG特征的同步迭代算法,提出局限性感知的增量计算倾斜消除机制,解决其典型应用,即行为模拟应用,群迁移导致的持续性计算倾斜。分析发现,在行为模拟应用中,模拟对象移动范围具有局限性。基于此特征,该机制根据邻居域的负载变化情况实时增量地评估每个域(对应一个任务)的负载,然后在以前域划分基础上增量地进行域划分、合并以及分配,有效实现负载均衡。针对具有PDG特征的同步迭代算法,提出基于计算分解的负载均衡机制,解决其典型应用,即社交网分析应用,计算倾斜问题。由于PDG特征,在此类同步迭代算法中,某些任务所需计算量会是所有任务所需平均计算量的数倍,并且大量任务会在运行过程中收敛,导致计算倾斜。分析发现,同样由于PDG特征,其任务是对大量数据对象进行汇总的过程。基于此事实,该机制动态识别掉队的任务,将其大部分计算分解为多个子任务用于并行处理,然后采用动态任务分配策略,实现负载均衡。针对同步迭代算法,提出基于细粒度并行的倾斜容忍机制,解决其倾斜负面影响累积问题。分析发现,在大多数同步迭代算法中,各数据对象在每轮迭代之后只会对其邻居数据对象产生影响。基于此影响局部性特征,该机制通过挖掘多个迭代层次之间大量存在的可并行处理部分,利用各轮迭代中倾斜导致的闲散时间提前运行后续迭代层次中这些可并行处理部分,以容忍倾斜的负面影响,解决其随时间累积的问题。综上所述,这些优化机制能够加快异步迭代算法收敛速度并减少其运行时开销,消除和容忍同步迭代算法中的计算倾斜和网络抖动导致的通信倾斜,显著提升各类迭代算法在大规模云平台上的执行性能。
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O241.6

【相似文献】