网络断路感知的同步机制*

2019-02-13项哲慧秦小麟

计算机与生活 2019年2期

项哲慧，秦小麟+，犹锋，刘亮

1.南京航空航天大学计算机科学与技术学院，南京 210016

2.南瑞集团有限公司，南京 210003

1 引言

近年来随着数据规模的增大，优化各种大数据处理平台的性能已成为研究的热点。图计算平台Pregel[1]和Giraph[2]等基于并行计算加快图数据的处理，它们采用BSP[3]编程模型作为并行算法的基础框架。Barrier（栅栏）同步是并行计算常采用的一种同步方法,用于BSP的两个超步（super-step）之间的同步。一个线程调用Barrier意味着该线程需要在该点等待所有线程到达，控制线程的执行进度确保并行计算的正确性。在并行最小生成树算法中[4]，对多个连通分量进行合并需要先统计所有连通分量选择的边，再确定该边是否同时被两个连通分量选中，进而合并连通分量。因此线程在计算完连通分量选择的边之后需要同步，否则会出现先计算完的线程无法判断边是否同时被两个分量选中，因为选择该边的另一个连通分量可能由其他线程处理。可见Barrier同步是保证并行计算正确性不可或缺的部分，它的效率直接影响并行计算的性能。

并行计算有两种计算结构：共享内存结构和消息传递结构。后者在大数据处理平台中更常见，如Pregel，Giraph的Barrier同步机制是通过消息传递实现线程之间的同步的。然而在网络中，消息过量、消息重发以及消息的输入速率超过输出速率[5-6]等原因都能造成网络拥堵或者网络断路。而现有的Barrier算法在遇到网络拥堵或者网络断路时只能等待或者选择一条更远的路由传递消息，降低了同步算法的效率。

造成上述问题的主要原因是现有Barrier算法的通信模式[7](communication pattern)是固定的。如图1（a）所示：在由节点a、b和c组成的网络上进行同步，3个节点两两之间有物理链路连接（双向箭头表示物理链路）。Barrier算法设定由a汇总3个节点的状态，则节点b、c需分别向a传送同步消息，此时，节点b、c消息传递分别只需1跳的距离（实线箭头）。如果ab链路断路，节点c向a传送消息的路径不变，但节点b与a通信时要通过节点c转送消息，导致节点a、b的通信距离增加到2跳（虚线箭头），且加重了ac链路上的拥堵状况。但如果能改变通信模式，由c来汇总消息，则节点a、b分别向c传递同步消息，均可1跳到达，避开了断掉的ab链路。然而直接修改通信模式代价较大，如调整最小生成树结构的Tree算法的通信模式时需重新构建最小生成树，调整过程依赖多个轮次的同步[4]、额外的消息来确认节点间的通信关系以及额外的空间来存储新的通信模式结构，避免与调整过程中依赖的通信模式混淆。

Fig.1 Network topology图1 网络拓扑

此外，通信模式的结构与网络拓扑的契合度会影响算法效率。现有的大数据平台[1-2]使用的同步算法（如PUB[8]）的通信模式结构为主从结构(masterslave，MS)，而MS结构仅适合星型拓扑的网络结构。如图1（b）所示：由节点a、b和c组成的线型网络由ab、bc两条物理链路连通（双向箭头表示物理链路），设定由a汇总3个节点的状态，在MS结构中，节点b给a发送同步消息需要1跳，节点c给a发送同步消息需要2跳（实线箭头）。在2层树形结构中，节点a为树根，b为中间节点，c为叶子节点，叶子节点c给b发送同步消息，中间节点b汇总自身及子节点（节点b、c）的消息再发送给根节点a，节点b、c发送消息分别只需1跳距离（虚线箭头）。可知通信模式决定的需要通信的节点间的距离（跳数）越小越好（更契合网络拓扑）。

针对上述问题，本文在原来的Barrier算法基础上提出一种新的同步算法，可调整通信模式，提高同步算法在网络断路下的效率。本文贡献如下：

（1）引入节点编码将通信模式与网络拓扑结构分离开，并提出一个异步调整算子（asynchronous adjustment operator，AAO）通过修改节点编码的方式达到调整通信模式的目的，这种调整方式比直接调整通信模式的代价低。

（2）提出了局部连续树（local continuous tree,LCT）结构的通信模式，LCT结构具有局部连续性，可以减小网络中需要相互通信的节点之间的距离，提高通信效率。

（3）结合LCT结构和AAO算子，提出了动态局部连续树(dynamic local continuous tree，DLCT)算法。并实验比较了DLCT算法与其他5种Barrier算法在网络断路情况下的效率，结果表明DLCT比其他算法的效率高30%到50%。

本文结构如下：第2章介绍Barrier算法的相关工作以及现有算法在网络断路下的局限性；第3章介绍提出的DLCT算法；第4章实验评估DLCT在网络断路下的效率；第5章总结工作。

2 相关工作

Barrier算法可分为三类：单相、双相和多层。单相算法用消息散播的方式，使得各节点都获得全局节点的同步状态并进行独立判断；双相算法有个中心节点来获取并判断全局节点的同步状态，在Gather阶段中心节点汇总所有节点的同步消息，判断全局的同步状态，并在Release阶段通知其他节点所有节点已到达同步状态并结束同步；多层算法将网络分层，每层应用不同的Barrier算法，使得不同算法间进行优势互补，并提高算法的拓展性。然而这些算法均不能很好地适应网络断路状况。

单相 Barrier算法有 All to All、Butterfly[9]、Dissemination[7]和Pairwise exchange[10]。其中后3种采用了Han等提出的消息散播模式[11]，把All to All的O(N2)的消息复杂度降低到O(NlbN)。此类算法适用于共享内存的多核框架，可以减少锁的使用。但是在网络框架下，该类算法的消息量比双相Barrier算法O(N)大，导致同步效率相对较差，且通信模式复杂，不易调整。

双相Barrier算法有MS（master-slave）、combining tree[12]、tournament[7,13]、MSC（Mellor&Scott’s combining tree）[14]、BST（binominal structure tree）[15]和2层树形结构[16]。其中MS算法简单，很多大数据平台的同步模型都使用MS算法[1-2]，但是master节点容易成为全局的热点。Combining tree的k叉树结构、tournament的锦标赛结构和BST的二项树结构等都能缓解一定的热点问题。上述结构都是不同形状的树形结构，调整代价大，涉及到额外的同步、通信和存储空间。

多层Barrier算法有 MLB（multi-layer barrier）[17]、TAB（tree-based all-to-all barrier）[18]和文献[19]等。但是因为多层算法只是融合现有算法，其通信模式依然是固定的，且不易调整，同样会出现断路时效率大幅降低的问题。

此外，文献[20]研究了上述Barrier算法在负载不均衡的情况下的效率。文献[21]在共享内存结构下研究Barrier算法的效率。

3 DLCT Barrier算法

3.1 LCT通信模式

因为双相Barrier算法消息复杂度低，比较适合在网络中同步线程，所以本文在双相Barrier算法的基础上改进。本文采用的通信模式为二项树结构。如图2（a）所示，在LCT结构中，ID=x的节点的父节点为ID=x&(x-1)，比如节点6的父节点为6&(6-1)=4，相当于将子节点的最低非0位置0。根节点0的父节点为null。通信模式结构中相连的节点间需要通信。

Fig.2 Structures of LCT&BST图2 LCT和BST的结构

本文给出通信模式的形式化定义，用一对映射G，R:{ID}→p({ID})分别表示节点x在Gather阶段和Release阶段的通信对象的集合，p({ID})表示节点集合的幂集（ID与节点一一对应）。在Gather阶段每个节点需要与父节点通信，从而逐步将同步信息汇总到根节点，计算父节点的过程对应通信模式中的G映射：G(ID)={(ID-1)&ID}，相当于将二进制形式的ID的最低非0比特位置0。在Release阶段每个节点需要与子节点通信，逐步广播同步结束消息到叶子节点，计算孩子节点的过程对应R映射，R(ID)的计算见算法1，即将二进制形式的ID的最低非0位之后的比特位逐个置1。

算法1 R(ID)LCT Release阶段的目标节点集合计算

通过引入节点编码以简化通信模式的调整：将网络中各节点的位置映射到全局唯一的ID值，使其与LCT结构中相同ID的节点对应，用映射num:{(x，y)}→[0，N)表示。其中，(x，y)表示节点位置，N表示网络节点个数。num映射用ID值将通信模式LCT结构中的节点与网络节点联系起来，网络节点先通过num映射得到相应的ID，再通过LCT的G、R映射计算出在Gather和Release阶段的通信对象。如在Gather阶段，位置为(x，y)的非根节点需要发送同步消息给位置为num-1(G(num(x，y)))的节点，其中num-1为num的反函数。在节点编号的基础上仅改变网络节点的ID值就能达到调整通信模式的目的，具体调整过程在3.2节阐述。

LCT与同为二项树的BST结构比较有两点优势：（1）简化节点编码；（2）易于更新链路集合。其中第（2）点在3.2节具体阐述。

LCT能简化节点编码：节点编码倾向于将需要通信的两个ID赋值给相互靠近的两个物理节点以减小通信距离，提高算法效率。如图2（a）、（b）所示，分别为LCT和BST的结构图，容易看出LCT的子树中的节点是连续编号的，而BST的编号是跳跃的，可知LCT结构中需要相互通信的节点编号相近。节点编码时只需根据节点距离依次编码，即可满足减少通信距离的需求，此类编码方式有S-order curve、Z-order curve[22]、Hilbert curve[23]等。本文采用的编码方式就是S-order curve，其num映射为num(x，y)=x×size+y+(x%2)×(size-1-2y)，其中size为网格型网络的长宽。用s-curve的编码方式将图2中虚线框内的节点映射到网络节点时（参考图3（a）或（c）），LCT结构中的节点12～15映射在一条直线上，而BST中的节点3、7、11、15却分别在置于网络中相距最远的4个位置形成一个波浪形。在相同的简单的节点编码方式下LCT结构在网络中的通信效率更高，即（在保证高效通信的情况下）LCT能够简化节点编码。

3.2 异步调整算子(AAO）

调整通信模式即改变节点的通信对象，从而改变使用的链路集合，起到避开断路的作用。通信模式调整主要有两种方式，改变节点编码num映射或者改变G、R映射。而改变G、R映射相当于改变逻辑上的树型连接，调整方式复杂，代价大。本文采用改变num映射的方式调整通信模式。异步调整算子round(K)的作用是更新网络节点的ID，即ID′=ID+KmodN，因为ID=num(x，y)，所以改变ID本质上即改变num映射：num′(x，y)=num(x，y)+KmodN。该调整过程仅对num映射进行模加运算，调整的计算代价很低。

Fig.3 Link set in use of BST&LCT before and after adjustment图3 BST和LCT调整前后使用的链路集合

UQ的值域为[0，1]：当A=B时UQ=0，无更新量；当A⋂B=∅ 时UQ=1，更新量最大。

LCT易于更新链路集合：如图3所示，分别为BST和LCT采用s-curve的方式映射到4×4的网络中，并调用round(1)更新通信模式。图中粗实线表示网络使用的链路集合，可看出通过调整，LCT和BST使用的链路集合都发生变化。根据LCT结构（图2）可知节点4、5之间需要通信，在图3（c）中为（2,3）和（2,4）节点通信，调整之后如图3（d）变为（1,4）和（2,4）节点通信，更换了使用的链路。LCT结构调整前后使用的链路集合的交集大小为7，并集大小为26，计算LCT的更新量UQ(LCT)=1-7/26=73.1%。同理根据图3（a）、（b）计算BST调整之后的更新量UQ(BST)=18.2%。LCT的更新量显著大于BST，即LCT更容易更新链路集合（在实验4.2节会给出BST和LCT完整的更新量的比较，说明在整体上LCT结构的更新量大于BST，上述例子并非特例）。

异步调整过程在Release阶段进行，其调整信息K值（round（K）的参数值）存放在同步消息结构中。同步消息结构如图4所示：G/R标志该消息的类型：Gather和Release；content在不同类型消息中的含义不同：在Gather消息中，content保存消息经过的路径的实际长度，该内容会被消息经过的每个节点更新，根节点根据Gather消息的content判断是否存在断路；在Release消息中，content表示调整算子的K值，收到Release消息的节点先转发消息给子节点，然后根据K值改变num映射，调整结构。调整信息借助同步消息进行传递，无须增加额外的消息量，且每个节点独立更新自己的num映射，异步调整结构。

本文定义了更新量UQ（update quantity）来量化AAO更新链路集合的效果，更新量越大说明结构越易于更新，从而越容易避开断路。

定义1（更新量UQ）在AAO的作用下链路集合从A变为B，则更新量为：

Fig.4 Structure of synchronous message图4 同步消息结构

此外，异步调整过程不会破坏同步过程的正确性。调整过程中只存在3种消息传递：旧节点给旧节点发送本次同步的Release消息，新节点给新节点发送下次同步的Gather消息，新节点给旧节点发送下一次的Gather消息。每个节点更新完num映射就结束本次同步过程，且如果节点未更新，它的子节点也一定未更新，所以不存在旧节点给新节点发送Release消息的情况。其中前两种情况相当于通信模式固定时的同步消息传送，不会破坏同步过程。在第3种情况中，因为旧节点处于本次同步过程的Release阶段，只要保证在Release阶段时本次的Gather消息已经清空，则下次的Gather消息与本次的Gather消息不会混在一起，隔离了两次同步中的消息就能保证两次同步过程正确。如何保证在Release阶段Gather消息已清空会在3.3节解释。

由调整过程可知，AAO有以下3个优点：（1）各节点异步调整num映射，不需要依赖额外的同步过程，或者额外的空间暂存新值；（2）断路的判定信息以及调整值K存放在同步消息中，不会增加消息量；（3）每次更新通信模式仅仅对节点num进行模加，计算量极低。降低通信模式调整对同步算法效率的影响。

3.3 DLCT Barrier同步过程

DLCTBarrier同步过程分为3阶段，分别为Gather、Release和调整阶段。相比原来的双相Barrier过程多了调整阶段。算法2为DLCT算法的具体过程。步骤1、2，初始化当前节点的ID和子节点的数量（需要接收的Gather消息数量）。Gather阶段：步骤3、4，节点等待接收所有子节点的Gather消息；步骤5，汇总子节点消息的路径长度；步骤6，清空Gather消息；步骤7、8，发送Gather消息给父节点。注意这里需要先清空消息队列再发送消息，确保节点不会在进入Release阶段之后还存有本次的Gather消息。因为如果先发送消息给父节点，可能出现还未清空消息时，就收到父节的Release消息的情况。Release阶段：步骤9、10，非根节点等待来自父节点的Release消息；步骤12，根节点汇总Gather消息，判断是否存在较大影响的断路，决定是否需要调整通信模式；步骤14，非根节点从Release消息中获取K值；步骤15、16，发送Release消息给子节点。异步调整阶段：步骤17、18，各节点根据K值调整通信模式；步骤19，最后结束同步过程，各节点恢复计算任务。

算法2DLCT Barrier同步过程

以4个节点的网络为例，节点0的子节点为1、2，节点1的子节点为3。假设节点0、2之间的链路中断，则在Gather阶段根节点0收到所有子节点的消息之后，根据消息的跳数判断网络出现断路情况，然后调用round(1)做出调整，并在Release阶段将调整参数K=1通过Release消息传递给子节点。根节点0调整之后节点编号变为1（成为叶子节点），标记该节点为x，假设当其他3个节点还处于Release阶段时，节点x已进入下一阶段的同步过程，并发送Gather消息给节点0（原节点3），节点3在Release阶段已清空Gather消息队列，此时节点x给原节点3发送消息可以安全缓存到队列中而不会与上一次的Gather消息混合，直到原节点3调整节点编号为0并进入下一次同步之后才会处理缓存的Gather消息，因此调整通信模式的过程是安全的。

4 实验与分析

4.1 实验设计

实验在JADE[24]4.4.0平台提供的通信基础上搭建模拟的网格型网络：每个节点都有唯一的位置信息(x，y)，并根据位置信息确定其邻居节点（可以直接发送消息的节点），在发送消息给目标节点的过程中，先将消息发送给离目标节点最近的邻居节点，如果接收到消息的节点非目标节点则继续选取离目标节点最近的邻居节点转发消息。断路情况通过删除邻居节点来实现，比如设定相邻的a、b节点之间的链路中断，则节点a删除邻居节点b，节点b删除邻居节点a。网络层封装消息的路由过程，保留send、receive接口供Barrier算法传送同步消息。实验采用一个简单的同步测试程序测试各Barrier算法的效率，测试程序调用3次Barrier进行同步，每两次同步之间sleep 0.5 s（无同步情况下的单个线程运行时间为1 s）。各Barrier算法都给同步测试程序提供统一的Barrier()接口用于各个节点的同步。

实验选取现有的5种Barrier算法进行实验，双相算法采用MS、Tree、Tournament，分别代表不同的结构，其中MS为单层树状结构，Tree为最小生成树结构，Tournament为锦标赛结构（混合二项树与单层树结构）。单相算法选取dissemination作为代表，因为该算法在单相算法中效率最高：A2A（all-to-all）算法消息量大，butterfly、pairwise exchange在节点数量非2的幂次方时效率骤降。多层算法由单相和双相算法中效率最高的dissemination+Tree构成。在实验过程中发现单纯的DLCT算法扩展性不好，因此实验采用了双层算法ID1：DLCT+MS和ID2：DLCT+Tree。ID1和ID2的结构依然是树状结构，通信模式的调整过程只作用于DLCT层。

实验结果有两个指标分别为更新量UQ和同步程序运行时间。采用更新量来量化LCT结构在AAO调整下避开断路的能力，更新量越大则越容易避开断路。用同步程序运行时间来比较各Barrier算法的同步效率，因为用于测试Barrier算法效率的程序是相同的，程序的运行时间可以侧面反映出Barrier算法的效率，程序运行时间越短则Barrier算法效率越高。此外，实验设定了不同比例的断路状况来测试Barrier算法在断路情况下的效率，并设定了不同的网络规模，测试Barrier算法的拓展性。

4.2 LCT结构避开断路的能力

为证明LCT避开断路的能力，实验在大小为4×4的网格型网络上计算LCT的更新量。在16节点的网络中，共有16种s-curve型的节点编号（确定了其中一个节点的编号就可以根据s-curve确定网络中所有节点的编号），每种编号可以通过调用异步调整算子round(K)转化成其他编号，一共有16×16种转化。分别计算出这256种情况下的UQ(LCT)，其平均更新量为0.552 7，即平均每次调整结构都能更新一半的链路。

此外实验比较了LCT和BST结构的更新量，计算BST在256种转化下的相应的更新量UQ(BST)，取LCT与BST更新量的差值UQ(LCT)-UQ(BST)作直方图，结果如图5所示。当LCT的更新量大于BST时，竖条为正，出现在x轴上方，反之则出现在下方。由图可知x轴上方的竖条比较密集，可见在绝大部分的转化中LCT通信模式的更新量比BST大，从而可知LCT比BST更易更新链路。因为DLCT可通过双层Barrier算法拓展，实验只考虑算法在4×4大小的网络中的更新量。

4.3 DLCT算法的拓展性

如图6所示（a）、（b）、（c）分别为各Barrier算法在网络链路完好、存在10%的网络断路和存在20%的网络断路的情况下，以及在不同网络规模下（网络节点数不同）的运行时间。

Fig.5 Update quantity of LCT&BST图5 LCT和BST结构的更新量

除ID1、ID2和Tree外，其他算法的拓展性都比较差。Dissemination算法的消息量为NlbN，随着网络规模的增大，其消息量与其他算法的消息量的差值增大，双层算法Dissemination+Tree有同样的问题。Tournament和MS中的通信模式不契合网络拓扑，导致通信距离比较长，网络规模的增长，越发加剧了这种现象。ID1、ID2和Tree的通信模式比较契合网络拓扑，其中Tree是依据实际网络建立的最小生成树，从图6（a）可以看出无断路情况下，随着网络规模的增大Tree算法的效率基本保持不变。DLCT在较大规模的网络中的效率略低于Tree算法。网络断路使得每种算法的效率都有不同程度的降低，从图6（b）、（c）可以看出在网络断路情况下，DLCT的斜率比Tree低，更适应断路情况。

Fig.6 Delay of Barrier algorithms in different break rates of link图6 Barrier算法在不同断路率下的延时

4.4 DLCT在网络断路下的效率

从图6可以看出双层DLCT与Tree算法的效率比较高。实验进一步比较断路情况对DLCT与Tree的效率的影响。如图7所示的横向5组实验分别是3种算法在不同网络规模下的运行时间，每组中的3条竖线分别为对应算法在断路率为[0%，50%]的网络中运行时间的范围，线上的黑点为算法在不同断路率下对应的运行时间。可以看出两种结构的DLCT的两种算法ID和ID2都比Tree算法效率高，能达到30%到50%的效率提升。比较线段最低点（断路率为0的情况）Tree算法跟DLCT算法的效率相差不大，但是在断路情况下Tree算法效率急剧下降，图7所示的Tree算法的线条长度最长便可说明该算法受断路影响最大。本实验说明了DLCT算法能在一定程度上提高Barrier算法在网络断路情况下的效率，从而表现得比其他算法优异。