图计算中基于一致性约束条件的迭代模型研究

孙茹君1 张鲁飞1 郝子宇1 陈左宁2

1(数学工程与先进计算国家重点实验室 江苏无锡 214125)2 (国家并行计算机工程技术研究中心 北京 100190)

迭代计算是数值计算中有效的逼近方式,能够拟合多种计算模型.在大数据分析领域尤其是图计算中,迭代计算能够抽象描述大部分图算法,对结构化数据挖据和关联分析至关重要.随着数据规模的增长,很多精确算法的时空复杂度已经难以满足现实需求,迭代计算的算法越来越丰富.并行迭代是图计算的主要实现形式,已有的图并行策略大多数是同步模型,少量异步模型,对于一致性约束条件下的迭代研究较少.研究内容重点关注图计算模型中迭代执行技术,分析了同步迭代和异步迭代的适用性,以及不同一致性下的异步迭代方式,针对已有异步迭代方式的不足提出了自适应的弱一致异步执行模型,并进行了验证性实验.实验证明:该模型能有效提高部分图算法的执行效率,尤其是收敛速度和效果.

关键词 图计算;图迭代;分布式计算;同步迭代;弱一致异步迭代

在图计算模型中,图用点和边上的数据来表示,计算在点上进行.迭代计算是图计算的重要执行方式,大多数数据挖掘的算法都可以描述为迭代的形式.在分布式并行计算环境下,迭代过程复杂,也关系到算法的执行结果.

在大规模分布式条件下,图的并行策略包括同步和异步的执行方式.本研究将从图并行的同步和异步方式入手,讨论2种不同的执行模式对图计算不同算法的适应性.并在一致性条件的约束下,分析不同一致性模型异步迭代的特征,提出一种基于一致性约束的自适应弱一致迭代模型.

本文首先介绍图计算和迭代计算的背景和相关工作,对迭代计算进行理论建模和分析,接着分析了同步和异步迭代执行模式并提出了弱一致迭代模型,随后对之前的理论分析和提出的新模型进行了实验.

1

1.1 相关工作

迭代计算用数值逼近的方式解决了许多科学计算问题.在图计算中,迭代执行是主要的计算方式.每一轮中,每个点根据自己及邻居的信息完成计算,更新自己的值.

串行的迭代方法有雅可比(Jacobi)和高斯-赛德尔(Gauss-Seidel)方法[1].迭代计算可以转化为矩阵乘法,迭代的收敛性可以用矩阵的特征值对应:当矩阵的谱小于1时,迭代问题收敛[2].

并行的迭代方法起源于块同步并行(bulk syn-chronize parallelism, BSP)模型[3-4],目前许多图计算框架都基于BSP模型实现,例如Pregel[5],GraphX[6]等.ApacheFlink[7]提供了BSP迭代和增量迭代,后者可减少每一步迭代的计算量.在不规则的图数据上,并行同步迭代各个点上的计算难以同时结束,同步迭代可能面临着严重的“落后者问题”(一个节点的延迟会影响整体计算).异步迭代能充分利用计算资源,避免每轮迭代的同步开销.除了一些图算法的异步实现,如PageRank[8]等,一些图计算框架也加入了异步机制.GRACE[9]图计算模型提供了用户友好的BSP编程接口,迭代执行时采用异步方式.PowerGraph[10]图计算模型提供了同步和异步迭代2种计算引擎,用户只需描述图中点的计算,可以指定任意一种执行方式.除了以上SMP(symmetric multi-processor)模式的框架,Frog[11]和Gunrock[12]等框架提供了GPU上的异步图计算实现.

同步迭代和异步迭代有不同的适用条件.Power-Switch[13]将同步迭代和异步迭代相结合,能够在计算过程中按照设定的阈值在二者之间进行切换.

异步迭代执行面临数据一致性的问题,为了迭代的收敛和迭代速度,针对边和点的数据读写,还有异步迭代的不同一致性之分:完全一致、边一致和点一致.不同一致性下的异步迭代执行会有不同的执行过程甚至结果[9].目前图计算模型的一致性研究不多,且仅有单一异步一致性的迭代方式,即只单独使用完全一致、边一致、点一致这3种方式里的1种.

1.2 图计算中迭代执行算法

大规模分布式并行图计算的执行模式可称为图并行,是一种迭代的模型.计算发生在图中的点上,通信沿边的方向.以图中点的视角,整个执行过程是不停迭代地“计算”、“通信”,直至收敛或达到其他终止条件.

和迭代相关的图算法可以归为3类:随机漫步算法(random walk)[14]、串行遍历算法(sequential traversal)和并行遍历算法(parallel traversal).随机漫步算法中每轮迭代当前节点的值都会按照一定的比例影响其邻居节点,也接受邻居节点的影响,例如PageRank[15]、近似计数、k-SAT[16]算法、HITS(hyperlink-induced topic search)算法等.串行遍历算法在迭代的每一轮当前节点会将值传播给邻居节点,如路径可达判定、单源最短路径(single-source shortest path, SSSP)、宽度优先搜索(breadth-first search, BFS)、深度优先搜索(depth-first search, DFS)等.并行遍历算法下,图中的每个点都作为起始点执行串行遍历算法,如标签传播、图聚类、图着色(graph coloring)等.

1.3 迭代的串行执行方式

迭代计算的后一步依赖于前一步的计算结果.如果将计算第t轮的中间值描述为x(t),那么迭代计算可被描述为x(t+1)=f(x(t)),初始值为x0,结束条件为g(x(t+1)-x(t))<δ.在矩阵计算中,函数f一般为f(x(t))=x(t)A+b.

迭代有雅可比法(Jacobi method)和高斯-赛德尔法(Gauss-Seidel method).设x=(x0,x1,…,xn),雅可比法每次迭代可以被描述为

而高斯-赛德尔法每次的迭代可以被描述为

.

雅可比法和高斯-赛德尔法都直观地描述了迭代的串行执行过程.在串行迭代时,每轮迭代依次进行,1轮迭代中图中的点按照编号依次更新值.雅可比迭代每一轮中计算的参数是上一轮的值,而高斯-赛德尔迭代每一轮汇总计算的参数是最近产生的值(包括本轮之前产生的值和上一轮产生而在本轮还未更新的值).

1.4 迭代的并行执行方式

在分布式并行环境下,迭代可以并行执行.并行执行方式分为同步和异步.

1.4.1 同步迭代

同步迭代下,每一轮的执行仅与当前轮有关,本轮之内各节点并行计算.只有当所有节点本轮计算完毕之后,才会进入下一轮迭代.这种同步执行方式是BSP.

1.4.2 异步迭代

异步迭代下,各节点的计算与其他节点不相关,没有轮与轮同步和节点的相互等待过程.各节点并行计算,当本节点迭代1次之后,立即开始下一轮迭代.在迭代过程中如果需要其他节点的数据,则请求获得其他节点的最新数据即可.特别地,在一些条件约束下,为了异步迭代数据的一致性,请求其他节点的数据有可能不是即刻更新的值而是上一轮的值.

不考虑计算的串并行,单从同步和异步的角度看,雅可比迭代法是BSP类型的同步模式,而高斯-赛德尔迭代法已有异步的思想,即新计算采用当前最新的值,无论这个值是在当前轮或是上一轮产生.

并行分布式计算中的异步迭代中,当前计算可以采用的最新的值不仅仅局限于前一轮,由于异步执行在各个节点的可能轮数相差很大,最新的值很有可能横跨多轮.

1.4.3 同步和异步的执行过程

在执行过程中,同步迭代下,划分到同一个机器上的边和点在1轮迭代中依次进行计算,在2轮之间进行同步和可能的合并计算.异步迭代时,每个机器上的子图中各个点单独计算,本节点1轮计算之后直接进入下轮,不等待其他节点的计算进度.

1.5 不同迭代的适用性

在图计算的迭代算法中,同步执行与异步执行有不同的适用范围.PageRank等基于随机漫步的算法同步执行比异步执行效率更高.因为在每一轮迭代中,每个节点都参与计算,且计算量相当,各节点收敛的速率接近.异步执行相较于同步执行会引起更多的通信,各节点请求终止与综合判断的开销较大.而图着色等遍历算法异步执行效率更高,因为每个节点虽然计算模式相同,但计算量有区别,同步迭代会面临“落后者问题”,此外,一些算法需要执行的“异步性”来保证算法跳出不断翻转的死循环.因此同步迭代较适用于随机漫步类算法,异步迭代更适用于并行遍历类算法.

2 迭代过程的理论建模

2.1 并行迭代描述

“以点为中心”的计算下,迭代过程可以用点上的计算来描述.迭代的并行执行可以用点的迭代计算表示.设点上的计算为P(v(t))=p(v(t-1),,,…,,uiΓ(v),其中Γ(v)表示v的邻域(邻居节点集合),表示节点ui在第ti轮之后的值,p为点v上的计算函数.在同步迭代的条件下ti=tj=t-1,(i,j∈{1,2,…,k}).而在异步迭代的条件下,函数p中参数可以发生在任意轮,即titj等可以各不相同.在图迭代实现时,可以设置点迭代的收敛条件,如v(t)-v(t-1)<δ.当图中所有的或者超过一定比例的点达到收敛条件时,整个迭代计算收敛.

2.2 迭代执行的收敛性

迭代过程中的计算可以用矩阵描述x(k+1)=x(k)T(f)+b,当矩阵T的谱半径小于1时,迭代过程收敛[17].谱半径ρ(T)=maxλii=1,2,…,nλi为矩阵的特征值.图的迭代计算也可以用以上形式描述.求解每个xi的值不一定需要所有点上的值,大多数情况下只需要对应图邻居节点的值,所以此时矩阵T中图中各点对应的非邻居元素都为0.

许多算法其本身的特点就会使对应矩阵的谱半径小于1,例如PageRank算法,其迭代公式是xi=(1-α)+α,要求0<α<1.对于此类算法,异步迭代与同步迭代一样,都可以达到收敛.

另外一些图算法对应于图的选择问题,每次计算会根据收到的信息(例如邻居节点的值)对本节点进行直接修改.由于修改对应的矩阵每行只有一个元素为1,其余皆0,矩阵的谱半径为1,此类算法的迭代收敛性不能保证[18].例如图着色算法,节点可选颜色用自然数表示:如果采用同步迭代的方式,每次迭代当前节点选择与周围所有邻居颜色都不同的最小颜色编号的值,如果最后2个节点的颜色不断交换跳变,图着色算法不能收敛;如果采用异步迭代执行,此种情况很有可能避免.另如标签传播类的算法,每次节点会根据选取收到的所有邻居节点值的其中一个作为本节点的值,当节点信息保持稳定时节点会请求终止,类似地,异步迭代相比于同步迭代执行方式更容易收敛[19].

3 弱一致的异步迭代执行方式

3.1 完全一致边一致点一致

对于异步迭代,由于当前节点可以随时访问其他节点,而被访问的节点可能处于任何状态,如果要使用最新的值,则需保证数据的一致性.然而由于异步迭代中不同节点间轮数可能会差异很大,所以即使没有使用节点的最新值(比如该节点正在计算而拒绝访问其值)而使用其旧值也没有影响,此时可以理解为该节点在请求节点的视角下还处于上一轮的状态.

数据一致性指的是节点在同时读写时为了数据的有效性而设置的约束条件.图计算中迭代的一致性也是执行的一种约束条件,但其不仅仅约束本节点,还约束与本节点相关的邻居节点.图中计算存在于点,而数据在点和边上都有分布.考虑到收敛性要求,异步迭代的一致性约束分为3类[10],如表1描述,按照当前节点计算时,是否允许其他节点读写自己、邻边及邻节点的数据(R表示可读,W表示可写,表示不可读,表示不可写),分别是完全一致(complete consistent)、边一致(edge consistent)、点一致(vertex consistent).

Table 1 ReadabilityWriteability in Different AsynchronousConsistent Models

表1 不同异步一致性与计算时的可读写性

ConsistentModelLocalVertexNeighborEdgeNeighborVertexComplete ConsistentR WR WR WEdge ConsistentR WR WR WVertex ConsistentR WR WR W

Note: R—readable; W—writable; —unreadable;—unwritable

以上异步执行模式中,点一致即全异步可能出现写竞争情况.一致性要求越高,异步执行的并行性越低,执行速度也会因此降低.但较高的一致性能有效减少竞争情况,从而加快迭代后期的收敛速度,甚至使原本由于竞争而不能收敛的算法收敛[20].

3.2 单一异步一致性执行的不足

在异步执行时,可采用统计活跃点的方式来判断异步执行的并行性(活跃点指同一时刻正在计算的点的数量).已有的异步迭代方式[9]只有单纯的完全一致、边一致和点一致,各有优劣.

1) 完全一致的异步迭代执行能够有效避免竞争,但是在同一时间段内同时执行的点数有限,并行效率较低.

2) 边一致相对于完全一致约束较松,但在边上没有数据的条件下,边一致和点一致相同(由于写锁排斥读锁,而读锁之间不互相排斥.在异步执行时,读到的邻居数据并不要求是最新值.所以在没有边数据时,点一致和边一致都只维持本节点的范围计算即可).

3) 点一致是完全异步的执行模式,但是在迭代执行的后期,对于一些算法会出现竞争的情况而难以收敛.

3.3 弱一致的异步迭代执行方式

针对已有异步迭代模型的不足,本文提出弱一致的异步迭代执行模型:综合已有的不同一致性约束条件,根据异步迭代的不同时间段的特征,选择最合适的一致性模型.

在“以点为中心”的计算中,异步迭代执行过程以活跃点的数目描述.例如,在图着色算法(随机漫步类算法)中,初始阶段,活跃点逐渐增加;中间阶段,活跃点在较高的范围内波动;最后阶段,活跃点开始下降.并行遍历算法和随机漫步算法不同,在开始时活跃点的个数较多,中间过程中活跃点在一定范围内波动,最后活跃点数目逐渐下降.

不同的一致性适用于异步执行的不同阶段.完全一致和边一致能够有效避免数据一致性问题引发的死锁,同时能够避免产生点一致中的竞争危害.在异步执行的开始阶段,较强的一致性限制会降低各点迭代的速度,因为此时竞争较少,而基于一致性要求,只有不到50%的节点在同时计算,较多的等待节点制约了执行速度.而在异步执行的后期,较高的一致性会加快收敛,而较低的一致性会引发竞争,甚至难以收敛.一个恰当的解决方式是在执行的初期采用完全异步的方式进行迭代,在中后期提高一致性约束加快收敛.

针对当前节点,迭代的计算过程如算法1,执行模型的流程如图1.

算法1. 弱一致的异步迭代执行.

① while (没有收敛)

② [根据活跃点信息等条件选择异步一致性模型];

③ 检查邻居状态,等待所有邻居状态满足本节点的计算要求;

④ 修改本节点状态;

⑤ 请求邻居数据;

⑥ 接收数据;

⑦ 计算vf(Γv,e(v));

⑧ 修改本节点状态;

⑨ end while

Fig. 1 Process of weakly consistent asynchronous iteration
图1 异步弱一致迭代的计算流程图

3.3.1 选择模型的时机

算法1行②表示异步迭代过程选择一致性模型.一致性模型的选择时机有很多:

1) 每轮迭代前选择(如算法1描述).此方式的优点是可以实时调整一致性模型的选择;缺点是每轮检查开销巨大,如果用活跃点检查,需要全局的All-reduce操作,这会大大降低迭代速度.

2) 间隔一定轮数,需要每个节点保持1个计数器.此方法的优点是避免了过多全局开销,但前提是间隔轮数设置合理;其缺点是需要权衡计数器的计算存储开销与图计算节点的计算开销.如果图计算节点的计算简单(例如仅仅是选择值),此方法会使计算量加倍.此外,此方法在迭代中间阶段会增加迭代一致性模型选择的开销,因为该时刻活跃点变化复杂,不同一致性模型下活跃点变化趋势不同,可能会引起此阶段选择的一致性模型不断跳变.

3) 间隔一定时间,需要计时器和时钟响应.需要全局的时钟开销和时钟中断响应,在分布式条件下需要考虑其数据一致性.一个替代的方法是采用“master节点法”管理时钟,但其缺点是该节点的IO开销巨大.

4) 活跃点阈值驱动,需要在一定时刻检查,例如每轮迭代开始前.这会增大迭代开销.

5) 邻居节点模型驱动,根据邻居节点更改一致性模型的情况决定本节点的一致性模型.此方法代价较小,只需要在每次节点请求邻居节点数据的时候一同接受模型信息;缺点是需要与其他方式配合,否则无法开始模型的更改.而引入其他方式的配合就会引入其缺点.

以上选择模型的时机并不是单一存在于异步迭代过程中,而是可以多种选择方式相结合.这样不仅可以融合各种模型选择方法的优势,还可以避免单一选择方法引发的单一方面开销巨大的问题.

3.3.2 选择的一致性模型

一致性模型的选择是弱异步迭代的关键.3.1~3.2节已经分析,完全一致、边一致、点一致的竞争性逐步加强,收敛性逐步减弱.

一个图算法采用弱一致的方式执行,一般会经历从点一致、边一致,到完全一致的过程.如果在执行过程中收敛和竞争并重,可能会出现以上过程的重复或部分重复.

从宏观上可以判断,活跃点数量越多,说明竞争占据更主要的地位;而活跃点数量越少,说明算法执行到更需要收敛的阶段.如果以活跃点驱动的算法,活跃点数量长时间不变,需要适时检查其计算情况,有时需要调整一致性模型(例如从点一致到边一致甚至完全一致)增加收敛能力.

而采用固定间隔的方法切换一致性模型时,可以根据算法的经验运行轮数总时间,确定初步的切换时机,用小规模的图运行做测试、调整,最终确定运行的模型选择.

3.3.3 不同一致性共存

由于一致性模型可变,在分布式环境下,各个节点之间的模型变化时机可能不同.当节点之间模型不一致时,多种一致性模型可在同一次图计算中共存.

图计算迭代中不同的一致性能够适应图中不同节点迭代收敛速度不同的情况.有实验表明[9],在完全异步(点一致)的模型下,图着色计算最后1%的活跃点计算用到整体迭代时间的34%.如果采用不同一致性的模型,可以使较难收敛的点首先提高一致性约束,而其他的点仍保持原来较低的一致性约束.这样在迭代过程中,较难收敛的点就能以更大的速度收敛,不会出现少量节点在迭代后期一直活跃的情况.

由于各个节点根据自身情况或者全局情况独立地选择异步迭代模型,本节提出的弱一致模型能够自动适应不同一致性共存的情况,且各节点之间不会相互干扰.

4

4.1 实验设计

本实验的执行流程如图2所示.在实验过程中采用负载均衡的划分策略进行图划分,比较同步迭代策略和异步迭代策略在执行PageRank,SSSP,Graph Coloring的结果.对于Graph Coloring的异步迭代,在不同一致性(完全一致,边一致,点一致,以及三者综合的弱一致)下执行,以比较不同一致性的计算区别.

实验采用公开数据集SNAP[21]中部分类别的图和Kronecker生成器生成的图(表2).

Fig. 2 Process of iterating experiment
图2 迭代执行流程图

Table 2 Graphs for Experiment
表2 实验用图

CategoryGraphVerticesEdgesWebWeb-Google8757135105039Social NetworkTwitter813061768149RoadRoadNet-CA19652065533214GeneratedK.3351—K.23951903351—2395190130654—134212448

实验环境为8个节点组成的集群,通过千兆以太网连接.每个节点包含8个2.50 GHz Intel® Xeon® E5420 CPU,8 GB DDR2 RAM.

4.2 实验算法

选择PageRank,SSSP,Graph Coloring这3种算法作为基本的实验算法分析迭代执行的效果.

PageRank算法每轮迭代中单点的计算过程:收集所有邻居节点的值pi;计算本节点值将本节点值发送给所有邻居.

SSSP算法每轮迭代中单点的计算过程:收集所有入边邻居节点的值pi;计算本节点值p=min{p,(min{pi}+1)};将本节点值发送给所有出边邻居.

Graph Coloring算法每轮迭代中单点的计算过程:收集所有邻居节点的值pi;计算本节点值,(N表示集合{0,1,2,…,n});将本节点值发送给所有邻居.

4.3 同步迭代与异步迭代的比较

图3和图4是PageRank计算在同步和异步2种迭代方式下的执行结果.本实验选择了典型的2种图——网页链接图(Web-Google)和社交网络图(Twitter),这2种图的大部分分析都会用到PageRank这种随机漫步类算法.该类计算需要得到具体数值作为最终结果,故比较2种迭代方式计算结果的区别,如图3(b)和图4(b).

从图3和图4可以看出,PageRank的同步迭代执行模式要优于异步迭代执行模式,执行时间更短.这是因为PageRank算法每一轮的计算量接近,采用同步的方式能够整合同一轮中的所有通信,在2轮之间的通信部分进行整体通信,而异步的迭代方式每个点计算完成之后都要单独通信,大量小消息带来了巨大的通信开销.图3(b)和图4(b)表明,同步和异步执行的计算结果基本一致,其误差在1%以内,也证明了异步迭代执行的合理性和正确性.

Fig. 3 SynchronousAsynchronous iterations in PageRank algorithm (Web-Google graph)
图3 PageRank算法同步迭代与异步迭代比较(Web-Google图)

Fig. 4 SynchronousAsynchronous iterations in PageRank algorithm (Twitter graph)
图4 PageRank算法同步迭代与异步迭代比较(Twitter图)

图5表示SSSP算法的同步和异步执行结果.选择了2种典型的图——社交网络图(Twitter)和道路交通图(RoadNet-CA),它们在实际应用中经常需要遍历类算法.例如用SSSP求2个人间的最短好友路径和2个地点之间的最短路径.该类型的计算同步迭代方式也优于异步迭代方式,这是由于图遍历的最短路径选择依赖于图的整体信息,采用同步的方式能够在每一轮中都有效计算图中每个点相对于源点的路径长,而采用异步的方式路径长度的变化更改更快,在相同的长度下可能需要记录更多的入节点信息.此外异步执行最严重的缺点仍是大量小消息的通信开销.对于图遍历类算法SSSP,由于结果唯一,同步和异步迭代方式计算结果相同,都可以保证正确性.

Fig. 5 SynchronousAsynchronous iterations in SSSP algorithm
图5 SSSP算法同步迭代与异步迭代比较

表3表示图着色算法的同步和异步迭代执行结果.2幅图由于结构不同,需要的迭代次数有差异,其执行时间增加的比例也不同.与理论分析一致:异步迭代下图着色可以收敛,而同步迭代图着色不能收敛.

Table 3 Execution Time of SynchronousAsynchronousMethods in Graph Coloring Algorithm

表3 图着色算法同步迭代与异步迭代执行时间比较

ParallelNodesTwitter GraphRoadNet-CA GraphSyncAsyncSyncAsync2∞2.76973∞4.119174∞7.16003∞5.81978∞18.6696∞8.319616∞42.2898∞11.5532∞93.8981∞17.270364∞234.006∞34.8584

Fig. 6 Active vertices in synchronous SSSP algorithm
图6 SSSP的同步迭代执行

同步迭代中的活跃节点分析:图6和图7分别表示同步迭代下SSSP和图着色算法(RoadNet-CA图)的活跃点数变化趋势.由于SSSP是单源开始计算,故计算初始时只有源点为活跃点,随着迭代的增加逐步向邻居扩展,到迭代结束时所有节点的值都已更新完毕达到稳定值,活跃点降为0.图着色的初始状态下所有节点同时开始着色,在同步迭代的每一轮中活跃点个数都为总节点数,迭代无法收敛.这是因为相邻的2个点会不断同时变换颜色难以跳出此模式.

Fig. 7 Active vertices in synchronous graph coloring
algorithm
图7 图着色的同步迭代执行

4.4 弱一致的异步迭代

表4是不同一致性模型下图着色算法的执行情况,以Kronecker生成器生成1 048 576点数的自然图(K.1048576),8个机器运行为例.

Table 4 Graph Coloring in Different Consistent Models(K.1048576 Graph)

表4 不同一致性模型下图着色算法执行情况(K.1048576图)

Consistent ModelsExecution ResultExecution Time∕sComplete ConsistentFinished42.3Edge ConsistentFinished42.3Vertex ConsistentDead Lock∞

由于图着色算法的信息只包含在点上,边上没有信息,故不存在修改边数据的问题,边一致和完全一致相同.从表4可以看出,在点一致的异步迭代下,图着色难以结束,这是因为点一致时各点计算独立,当请求其邻边的数据时,邻边可能也在计算,从而引发死锁.而边一致与完全一致的迭代下,图着色能正常收敛结束.

异步迭代对于请求的邻居节点值于何轮产生没有要求.为了避免点一致下死锁的问题,可以采用更强的一致性策略.为了详细分析不同一致性的执行特点,可以统计执行过程中活跃点的变化规律.

异步执行时各节点的执行状态不同(有的在通信,有的在计算),难以找到合适的时间点进行统计,每次统计活跃点采用的All-gather操作又会影响其本身的迭代执行(需要每个点的当前轮计算结束,相当于1次同步过程,只是各点执行的轮数不同).因此对于异步执行的分析仅抽样执行阶段的指定时间步长.

图着色计算过程不会用到边上的数据,由于边一致和完全一致在图的边上没有数据时写锁的范围一致,故其执行情况一样.所以后文我们比较点一致和边一致2种约束条件,以及对应的弱一致策略.

图8表示图着色问题分别用点一致的异步迭代和边一致的异步迭代执行时,相同时间步长下活跃点数、总着色数、着色冲突数的变化情况.实验测得,点一致中的平均迭代轮数是边一致中的2倍.

Fig. 8 Asynchronous iteration of graph coloring
algorithm
图8 图着色的异步迭代执行

图着色的图并行迭代方法采用近似的算法,当着色冲突数(1条边的2个端点颜色相同表示1次冲突,总冲突数是冲突边数)下降到阈值以内,迭代结束.因此着色冲突数可以反映收敛速度.

从图8可以看出,点一致下,着色数逐步减少,异步竞争充分;实验中相同时间段内,平均每个点迭代的轮数多于边一致的条件下迭代轮数,迭代速度较快;而冲突数增加,收敛变差.边一致下着色数变化不大,异步竞争受到一致性条件的约束;而冲突数迅速减少,收敛变快.但是,冲突数到达一个略低的水平之后就会维持,有时难以达到设定的阈值.

图9表示本文提出的弱一致异步迭代模型在标签传播类着色算法上的执行结果.我们先通过点一致的异步迭代维持较高的迭代速度(虚线左边),再切换到边一致加速收敛(虚线右边).横轴表示近似迭代轮数,虚线左边平均迭代了500轮,用时9.823 s,虚线右边平均迭代了561轮,用时21.019 s;总用时30.842 s.

Fig. 9 Weakly consistent asynchronous iterating
图9 弱一致的异步迭代

Fig. 10 Convergence speed in weaklyedge consistent
asynchronous iterating
图10 弱一致与边一致的异步迭代下的收敛速度

可以看出,经过一致性切换,着色冲突数逐步减少,使算法快速收敛并结束.

图10表示弱一致(方块)和边一致(叉)的收敛情况,虚线仍表示弱一致下的切换.本实验用105边数的图做示意,设置收敛阈值(着色冲突数)是20(总边数的0.02%).可以看出虽然一直采用边一致的策略能够使着色冲突数快速降低,但其达到50左右就维持在附近小幅波动,不能达到阈值要求.而采用弱一致的方式,在初期增加竞争,后续切换至边一致的策略后,着色冲突数能迅速下降,很快达到阈值20以下,经过进一步测试,本弱一致迭代着色冲突数会维持在15附近小幅波动.

可以看出,采用本文提出的弱一致方法.迭代初始状态选择点一致的迭代模式,能加快迭代速度,使着色迅速分散.达到切换条件(轮数)后,采用边一致的方式,能加快收敛.弱一致的异步迭代能达到更好的收敛效果,且用时较短;而同步或者点一致的异步迭代难以收敛,边一致的异步迭代收敛效果有限.

5

迭代计算在数据计算中是有效的逼近方式,能够拟合多种计算模型.在大数据分析领域尤其是图计算中,迭代计算能够抽象描述大部分图算法,在结构化数据挖据和关联分析领域至关重要.

在分布式并行环境下,并行迭代有同步和异步的执行方式.同步迭代是雅可比迭代过程的并行描述,原理简单,适合于整体计算的图算法,但会遇到“落后者问题”.异步迭代能最大化地利用分布式系统的执行环境,避免“落后者问题”,但是完全的异步又会引起竞争.异步迭代有不同的一致性约束条件,点一致、边一致和完全一致,一致性要求越高,竞争越少,收敛越快,但是并行程度越低.

已有的异步模型都基于单一的一致性,本研究提出了弱一致的异步计算模型,将异步迭代中不同的一致性执行方式在异步迭代的各个阶段融合,自动选择适合的执行方式.该方法能够利用不同一致性的特征服务于迭代计算的不同阶段,既可满足迭代初期要求的迭代速度,也可满足迭代后期要求的收敛速度.实验证明,在异步迭代开始阶段,选择一致性较弱的执行方式(点一致)能达到较快的迭代速度;在异步迭代的结束阶段,采用一致性较强的执行方式(完全一致)能达到较快的收敛速度.一致性模型的选择代价较大,在实际实验中,采用较简单的方法,在迭代的中期切换已能达到综合利用的效果.

参考文献

[1]Milaszewicz J. Improving Jacobi and Gauss-Seidel iterations[J]. Linear Algebra and Its Applications, 1987, 93(8): 161-170

[2]Zhou Tie, Xu Shufang, Zhang Pingwen, et al. Computing Method[M]. Beijing: Tsinghua University Press, 2006:103-104 (in Chinese)(周铁, 徐树方, 张平文, 等. 计算方法[M]. 北京: 清华大学出版社, 2006: 103-104)

[3]Cheatham T, Fahmy A, Stefanescu D, et al. Bulk syn-chronous parallel computing—A paradigm for transportable software[G] Tools and Environments for Parallel and Distributed Systems. New York: Springer, 1996: 61-76

[4]Gerbessiotis A, Valiant L. Direct bulk-synchronous parallel algorithms[J]. Journal of Parallel and Distributed Computing, 1994, 22(2): 251-267

[5]Malewicz G, Austern M, Bik A, et al. Pregel: A system for large-scale graph processing[C] Proc of the 29th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 135-146

[6]Xin R, Gonzales J, Franklin M, et al. GraphX: A resilient distributed graph system on Spark[C] Proc of the 1st Int Workshop on Graph Data Management Experiences and Systems. New York: ACM, 2013: 2:1-6

[7]Ewen S, Tzoumas K, Kaufmann M, et al. Spinning fast iterative data flows[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1268-1279

[8]Li Chao, Chen Jianxia, Yang Zhi, et al. Asynchronous Page-Rank computation in Spark[C] Proc of the 11th Conf on Complex, Intelligent, and Software Intensive Systems. Cham, Switzeland: Springer, 2017: 567-573

[9]Wang Guozhang, Xie Wenlei, Demers A, et al. Asynchronous large-scale graph processing made easy[COL] Proc of the 6th Biennial Conf on Innovative Data Systems Research. 2013 [2017-06-29]. http:cidrdb.orgcidr2013PapersCIDR13_Paper58.pdf

[10]Gonzalez J, Low Y, Gu Haijie, et al. Distributed graph-parallel computation on natural graphs[C] Proc of the 10th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: No.2

[11]Shi Xuanhua, Luo Xuan, Liang Junling, et al. Frog: Asynchronous graph processing on GPU with hybrid coloring model[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(1): 29-42

[12]Wang Yangzihao, Davidson A, Pan Yuechao, et al. Gunrock: A high-performance graph processing library on the GPU[C] Proc of the 21st ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2016: 11: 1-12

[13]Xie Chenning, Chen Rong, Guan Haibing, et al. Sync or async: Time to fuse for distributed graph-parallel computation[J]. ACM SIGPLAN Notices, 2015, 50(8): 194-204

[14]Don C, Peter D, Prabhakar R, et al. Random walks on weighted graphs and applications to on-line algorithms[J]. Journal of the ACM, 1993, 40(3): 421-453

[15]Page L, Brin S, Motwani R, et al. The PageRank citation ranking: Bringing order to the Web, SIDL-WP-1999-0120 [R]. Palo Alto: Stanford InfoLab, 1999

[16]Friedgut E, Bourgain J. Sharp thresholds of graph properties, and the k-SAT problem[J]. Journal of the American Mathematical Society, 1999, 12(4): 1017-1054

[17]Fedorenko R. The speed of convergence of one iterative process[J]. USSR Computational Mathematics and Mathematical Physics, 1964, 4(3): 227-235

[18]Szyld D. The mystery of asynchronous iterations convergence when the spectral radius is one, Report 98-102 [R]. Philadelphia, PA: Department of Mathematics, Temple University, 1998

[19]Frommer A, Szyld D. On asynchronous iterations[J]. Journal of Computational and Applied Mathematics, 2000, 123(1): 201-216

[20]Low Y. GraphLab: A distributed abstraction for large scale machine learning[D]. Berkeley: University of California, Berkeley, 2013

[21]Leskovec J, Krevl A. SNAP Datasets: Stanford Large Network Dataset Collection[OL]. 2014[2017-08-25]. http:snap.stanford.edudata

Consistency Based Iterating Models in Graph Computing

Sun Rujun1, Zhang Lufei1, Hao Ziyu1 , and Chen Zuoning2

1(State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi, Jiangsu 214125)2(National Research Center of Parallel Computer Engineering and Technology, Beijing 100190)

Abstract The time and space complexity of many accurate algorithms is difficult to meet the realistic demands, while approximating algorithms are alternative choices. Iterative computing is an effective approximating method in numerical computing. A variety of algorithms and models can be classified into it. With the increase of data scale, iterative algorithms are blooming and developing. Graph computing is a natural way to express and analyze relationships. There are numerous graph algorithms being described as iterative models. Parallel iterating is regular in large graph computing. Graph iterating methods have different parallel execution models. Most of the existing parallel graph computing implementations are synchronous, and a few of them are asynchronous models. However, there are few studies about consistency constraints in graph iterating. In this paper, we discuss the iterative computing technique in graph computing model. We analyze the applicability of synchronous and asynchronous iterations, and study the asynchronous iterative methods under different consistency, as well as experimental proving. We propose an adaptive asynchronous execution model which is weakly consistent. It overcomes the shortcomings of existing asynchronous iterative methods. Experiments of this model were done in parallel and have shown that the model can effectively improve some graph algorithms, especially the iterating and converging speed.

Key words graph computing; graph iteration; distributed computing; synchronous iterating; weakly consistent asynchronous iterating

(sun.rujun@meac-skl.cn)

中图法分类号 TP311.5

收稿日期20171128;

修回日期:20180305

基金项目国家自然科学基金项目(9143020017);国家重点研发计划项目(2017YFB0202001)

This work was supported by the National Natural Science Foundation of China (9143020017) and the National Key Research and Development Program of China (2017YFB0202001).

Sun Rujun, born in 1990. PhD candidate. Student member of CCF. Her main research interests include high performance computer architecture and computing models.

Zhang Lufei, born in 1986. PhD and engineer. Member of CCF. His main research interests include high performance computing and software engineering.

Hao Ziyu, born in 1978. PhD and engineer. Member of CCF. His main research interests include high performance computing and algorithms.

Chen Zuoning, born in 1957. Academician, PhD supervisor. Fellow of CCF. Her main research interests include high performance computing and operating systems, etc.