并行数字地形分析的容错算法研究

宋效东，刘学军，汤国安＊，窦万峰，江岭，杨坤

（1.南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210023；2.南京师范大学计算机科学与技术学院，江苏 南京 210023）

0 引言

在高性能地学计算领域，任务计算失败将会导致计算资源的巨大浪费。高性能地学计算不仅要满足实时性需求，还要求在计算机的软硬件出现故障时保证计算的正确进行。但高性能计算的发展远远领先于软件设计及应用的发展，这使得利用已有的硬件资源实现高质量的软件容错功能成为重要的研究方向［1－3］。

根据对容错资源的使用性质分类，容错技术主要分为软件容错与硬件容错。软件容错不仅需要处理计算机中的硬件故障，还需要在系统运行周期内及时发现并处理自身的设计错误［4］。软件容错技术不仅避免了增加冗余硬件的开销，又能有效屏蔽软件设计中的错误［5］，提高系统整体的可靠性，因此成为目前应用较为广泛的容错模型。基于算法的容错技术（Algorithm Based Fault Tolerance，ABFT）是为容忍硬件瞬时故障而设计的一类算法［6，7］。与传统的容错技术相比，ABFT技术能够高效地实现硬件错误的检测、定位甚至恢复［8，9］。ABFT在20世纪90年代得到广泛关注，其理论与应用也得到了丰富与发展［10，11］。但由于算法本身固有的缺点——低通用性，此类算法只对部分操作具有容错功能，如矩阵乘、矩阵分解、快速傅里叶变换算法等。

近十年来，各种空间数据获取技术的飞速发展为数字地形分析提供了海量的数据源，并行计算的应用已是大势所趋［12］。本文针对并行数字地形分析技术的特点提出基于算法的容错模型，以此为基础完成对邻域型算法的错误检测与恢复。

1 容错模型与前提假设

1.1 前提假设

有别于一般的高性能计算程序，并行地形分析的算法复杂度一般不是很高。由于数据日益增长的精度与分辨率，导致海量空间数据的运行时间相对较长［13－15］，一旦计算失败，将会浪费大量的计算资源进行重算。在并行数字地形分析的容错研究中，本文将注意力集中在软件容错方面。假设基于算法的容错模型应用于：有N个进程进行分布式并行计算，同时该集群可以提供稳定的通信。集群中有两个主节点，同时负责对各子进程计算结果的校验（图1）。这样主进程也有一个相应的副本，该主从模型可以很好地避免子节点与主节点同时发生故障时系统崩溃的情况。

根据算法的分析范围与数据依赖关系，可以将地形分析算法基本分为邻域型算法与全局型算法［16］。邻域型算法可以有效地研究与表达地貌形态特征，算法种类繁多［17］，具有重要的理论与应用价值。在数据划分时，假设DEM数据以行为单位进行数据划分，相应地，所有的计算节点上DEM的列数都相等。为了更好地体现基于算法的容错模型的特点，本文不考虑数据或算法间的依赖关系，着重研究邻域型算法并行化设计中的容错机制。

图1 基于算法的容错模型Fig.1 Basic diagram of fault－tolerant model based on algorithm

1.2 基于算法的容错模型

并行算法将规则格网DEM数据以一维行的形式划分。以二维坐标系的形式表示，X轴为东西方向，Y轴为南北方向。借鉴经典的基于算法的容错思想，本文提出增加每一数据块部分的校验行，通过校验行计算结果的对比来检验计算节点是否发生了计算错误。

定义1 并行数据集D ＝ ｛D1，D2，…，Dn｝，其中Di（1≤i≤n）为某一计算节点需要处理的数据块，并且该空间数据的部分属性会保存在主节点上。

数据集存储在网络文件系统（Network File System，NFS）中，各节点读取的数据都将记录在主节点相应的日志文件中，从而为从节点的计算提供有效的管理功能。

定义2 全局数据划分控制ID，用于标识并行数据集的计算任务。该ID由计算节点的节点标识（计算机名或网卡MAC地址）和划分数据的左上角坐标——CoordFrom组成。节点标识数据类型为string类型。

定义3 邻域型算法的容错属性集合PNeigh，用于记录所有数据块的空间属性。主节点负责维护该属性集合，用于管理备份所有节点计算的任务信息。该属性集合部分成员及属性注释表述如下：

定义4 冗余行NRow。假设算法分析窗口为M×N，每一数据块添加冗余行的数目：

其中的（M－1）／2行是为了避免最后一行数据的边界效应增加的缓冲区，额外增加的最后一行是为了计算下一节点的第一行数据，用来与相邻节点的计算结果进行正确性校验。

性质1：每一数据块的总行数：Row＝LocakSizeY＋NRow。图2为一个5×5分析窗口额外增加冗余数据行的示意图。

图2 5×5算法数据划分冗余行示意图Fig.2 Schematic showing redundant rows of algorithm based on five－by－five window

定义5 校验结果，是在计算节点i（i＜N）上对校验行执行地形分析算法计算出的结果。

定义6 被校验结果，是节点i（i＞1）第一行数据计算的结果。

定义7 校验结果集V，用于保存所有节点的校验结果。V保存了每个计算节点的冗余行计算结果和相邻节点中被校验的计算结果。

第i个数据块中冗余行计算结果也是相邻节点（i＋1）的第一行数据计算的结果。因此，前（N－1）个数据块的冗余行是在当前数据块的最底部。第一块数据没有被校验结果，最后一块数据没有校验结果。

性质2：结果集V的大小为（TotalSizeX，2×（N－1））。数据划分时所有数据块的列数均为TotalSizeX，所以结果集的列数也是TotalSizeX。在N个节点中，节点1和节点N均只能提供校验结果或被校验结果，因此结果集的总行数是2×（N－1）。结果集中包含了绝大部分数据块的校验结果和被校验结果，通过与相邻计算节点的两次对比，可以保证计算结果的正确性。

定义8 邻域型算法的容错模型N－ABFT。通过以上定义，将邻域型算法的容错模型表示为一个三元组 N－ABFT ＝｛PNeigh，NRow，ID｝。通过该三元组，算法可以对比分析各节点计算结果的正确性，实现计算错误的快速检测。

2 容错处理算法

通过对邻域型算法冗余的容错机制分析，本章设计基于容错模型的具体算法：错误检测算法和任务恢复算法。错误检测算法通过对比数据块冗余行的计算结果对相邻进程进行检错。任务恢复算法主要负责在其他节点重新执行计算失败的节点，当其他节点计算结束后，结果数据需要重新进行错误检测，从而保证所有数据均正确。

为方便描述，定义以下符号：1）TMaxC（i，j）：无故障情况下，计算节点i执行算法j的最长计算时间，其包含计算结果的读写时间；2）TMaxLat（i）：计算节点i将计算过程中的消息发送给主节点最大的延迟时间；3）Equal（arri，arrj）：数组相等判断函数，用于判断数据arri与arrj是否完全相等，两数组相等时函数返回true，否则返回false；4）Updata（FileName）更新主节点的日志文件；5）F｛f1，f2，…，fn＋2｝：各节点计算的正确性数据集，其中n是计算节点数，fi（1≤i≤n＋2）为整型，是节点计算结果的正确性标识，取值范围是｛0，1，10｝，0代表不可恢复的计算错误，1代表瞬时错误，10代表正常。

2.1 错误检测算法

利用各节点计算数据的属性集合，错误检测算法主要负责计算结果的正确性检验。错误检测算法与各节点计算同时开始，在计算节点的计算过程中，负责统计各计算节点执行一次计算的总时间、最早完成时间和最大延迟时间。在错误检测时，如果某节点运行时间超过最大延迟时间，则判定该节点计算失败，立即启动任务恢复算法。在各节点计算全部结束后，主节点根据校验结果集对各节点计算的结果进行正确性检验。如果相邻行计算结果相等，代表这两个节点均已正确执行，否则，启动任务恢复算法。如果所有的数据块均已正确计算，主节点将算法的容错属性集合PNeigh写入日志文件。如果各节点均正确执行或执行任务恢复算法后，需判定主节点是否存在计算失败的情况。算法描述如下：

算法1 N－ABFT错误检测算法

输入：计算节点个数N，全局数据划分控制ID，校验结果集V，邻域型算法的容错属性集合PNeigh，TMaxLat（i）；

输出：各节点计算的正确性数据集F，TMaxC（i，j）。

（1）判断机群中是否存在节点失败的情况，依次对各计算节点进行错误检测（for i＝1，…，N）。在计算开始前，向各进程i发送计算任务，包括PNeigh和Di；如果节点均能在TMaxLat（i）之内将消息发送给主节点，则该节点初始化正常，fi＝10，否则记录并修改该节点的状态属性fi＝0。两个主节点分别对节点1和节点N的数据进行冗余计算，并保存在本地，其他的从节点计算地形分析算法，计算结束后将计算结果写入全局输出文件；当所有节点计算结束后，根据算法j的复杂度，记录各计算节点的TMaxC（i，j）。各节点发送结束消息到主节点，如果节点均能在TMaxLat（i）之内将消息发送给主节点，则该节点计算结束，fi＝10；否则判定该节点计算失败，记录修改该节点的状态属性fi＝0。

（2）对比分析各节点计算结果的正确性。读取校验结果集V，依次判断数据行（for i＝1，…，（N－1））：首先判断节点1和节点N的正确性，并修改fi的值；读取数据集，取出2×i－1与2×i两行数据（分别对应计算节点i和i＋1的校验结果与被校验结果），分别存入浮点数组arri，arrj，执行Equal（arri，arrj）；如果函数返回true，节点i与i＋1计算的结果完全正确，修改fi＝10；如果函数返回false，验证节点i＋1计算结果的正确性，读取第2×（i＋1）－1与2×（i＋1）行的数据（分别对应计算节点i＋1与j＋2的校验结果与被校验结果），并分别存入浮点数组arri＋1，arrj＋1，并执行Equal（arri＋1，arrj＋1）：如果函数返回true，说明节点i＋1计算结果正确，节点i计算错误，修改fi＋1＝10，fi＝1；如果函数返回false，说明节点i计算结果错误，节点i＋1计算正确，修改fi＝10，fi＋1＝1。

（3）判断主节点的计算是否发生错误，执行如下操作：两个主节点同时对PNeigh和F进行判断与更新；两节点相互发送确认消息，如果其中的一个节点效应时间超过TMaxLat（i），则判定该节点失败，fN＋1＝0，取另外一个主节点的数据作为输出结果；输出各节点计算的数据集F与TMaxC（i，j）。

2.2 任务恢复算法

在程序计算结束后，对于发生计算故障的计算任务，算法将根据其故障类型进行重算。对于不可恢复故障，算法使用其他的计算节点对计算任务进行重算。对于瞬时故障，算法会在该节点上重新计算。算法描述如下：

算法2 N－ABFT任务恢复算法

输入：各节点计算的正确性数据集F；

输出：校验结果集V，邻域型算法的容错属性集合PNeigh、TMaxC（i，j）和TMaxLat（i）。

（1）统计出现可恢复和不可恢复故障的计算节点数，分别为NErrRecov、NErrUnrecov。

（2）对于可恢复故障的计算节点（for i＝1，…，NErrRecov）：重新执行可恢复故障计算失败的计算任务，对V中相应的内容进行重写；根据V的内容，重新执行错误检测算法：如果正确执行，修改fi＝10；否则，判定该节点不可用，从计算资源中删除该节点，fi＝1；计算TMaxC（i，j）、TMaxLat（i），并更新正确性标识集合F。

（3）对于不可恢复故障的计算节点上的计算任务（for i＝1，…，NErrUnrecov）：重新分配计算资源，对计算失败的任务重新计算。从计算资源中删除不可用节点；对重新计算的计算结果进行错误检测；其余节点执行新的计算。

（4）输出并更新校验结果集V等信息。

3 实验结果

本文在一个小规模的机群系统上实现了该算法。性能测试的环境为：18台计算机构成Cluster结构（2个管理节点，16个计算节点），处理器配备Xeon E5645 2.8GHz的四核处理器和8GB内存，节点间使用千兆以太网互连。机群采用主从模型，两个主节点用来负责数据分发、管理、容错检测与调度。DEM数据规模是16 000×15 120，数据类型是16位浮点型，数据大小约为540MB，TIFF格式。

在可靠性需求较大的重要领域，以往的容错技术主要采用三部件冗余［18］或进程副本，其错误检测的资源消耗分别为200%和100%。软件容错方法中的冗余进程（Redundant Processes）被认为是并行程序错误检测的有效方法［19，20］。本文以冗余进程为对比对象，使用不同的资源进程对不同的算法进行性能测试。设计并实现了不同分析窗口下的并行容错算法：3×3窗口的坡度算法和11×11窗口的切割深度算法。软件错误概率分别为0～0.2。为了测试部分计算失败对算法性能的影响，假设节点具有相等且独立的错误概率，系统随机地设定部分计算失败，包括CPU崩溃、内存申请失败、文件读写异常、NoData值设定异常和程序计算错误。

并行坡度提取算法与切割深度的平均检错开销如图3和图4所示。测试结果表明，该算法的检错开销明显比冗余进程方法低很多，能很好地检测到计算错误，并能够根据校验结果集找出计算错误的节点。尽管冗余进程可以实时地检测程序错误，但是需要占用较多的资源进行容错，而本文的检错开销在5%以内。通过引入冗余行的概念，不仅使系统获得了高错误检测率，还为容错调度提供了参考方法。

图3 并行坡度算法的检错开销Fig.3 Execution time of parallel slope algorithms

图4 并行切割深度算法的检错开销Fig.4 Execution time of parallel cutting depth algorithms

4 结语

软件质量的提高并不意味着不再需要容错。随着软件运行环境的开放与集群规模的增大，残留在并行系统中的各种故障隐患被激活的概率也随之增加。本文设计的容错算法主要针对海量DEM的并行地形分析邻域型算法而设计，通过定义基于算法的容错模型与冗余行所计算的校验结果集，对比分析节点间计算同一数据行的正确性。测试结果表明，该算法可以有效检测集群中的计算错误，缩短错误检测时间，提高并行系统稳定性。该算法虽然为邻域型地形分析算法而设计，但算法原理有望在其他邻域型并行算法容错上得到应用。下一步，笔者将深入探讨检查周期的系统耗费及二次容错机制。

［1］ RANDELL B.System structure for software fault tolerance［J］.IEEE Transactions on Software Engineering，1975，1（2）：221－232.

［2］ LEVITIN G.Optimal structure of fault－tolerant software systems［J］.Reliability Engineering and System Safety，2005，89（3）：286－295.

［3］ LEVITIN G，XIE M，ZHANG T.Reliability of fault－tolerant systems with parallel task processing［J］.European Journal of Operational Research，2007，177（1）：420－430.

［4］ 杜云飞，唐玉华.容错并行算法的分类和设计［J］.华中科技大学学报（自然科学版），2011，39（4）：49－52.

［5］ HANMER R S.Patterns for Fault Tolerant Software［M］.John Wiley ＆Sons Ltd，2007.

［6］ HUANG K H，ABRAHAM J A.Algorithm－based fault tolerance for matrix operations［J］.IEEE Transactions on Computers，1984，33（6）：518－528.

［7］ OBORIL F，TAHOORI M B，HEUVELINE V，et al.Numerical defect correction as an algorithm－based fault tolerance technique for iterative solvers［A］.17th IEEE Pacific Rim International Symposium on Dependable Computing Pasadena，CA，USA，2011.144－153.

［8］ BOSILCA G，DELMAS R，DONGARRA J，et al.Algorithm－based fault tolerance applied to high performance computing［J］.Parallel and Distributed Computing，2009，69（4）：410－416.

［9］ BANERJEE P，ABRAHAM J A.Bounds on algorithm－based fault tolerance in multiple processor systems［J］.IEEE Transactions on Computers，1986，35（4）：296－306.

［10］ CHEN Z，DONGARRA J.Algorithm－based fault tolerance for fail－stop failures［J］.IEEE Transactions on Parallel and Distributed Systems，2008，（19）12：1628－1641.

［11］ MISHRA A，MILI L，PHADKE A G.Algorithm based fault tolerant state estimation of power systems［A］.Proceedings of the 8th International Conference on Probabilistic Methods Ap－plied to Power Systems，Iowa State University，Ames，IA，2004.97－103.

［12］ 王结臣，王豹，胡玮，等.并行空间分析算法研究进展及评述［J］.地理与地理信息科学，2011，27（6）：1－5.

［13］ MINETER M J，DOWERS S，CALDWELL D R，et al.Highthroughput computing to enhance intervisibility analysis［A］.Proceedings of the 7th International Conference on GeoComputation［C］.Southampton，United Kingdom，2003.

［14］ GUAN X，WU H.Leveraging the power of multi－core platforms for large－scale geospatial data processing：Exemplified by generating DEM from massive LiDAR point clouds［J］.Computers＆ Geosciences，2010，36（10）：1276－1282.

［15］ 宋效东，刘学军，汤国安，等.DEM与地形分析的并行计算［J］.地理与地理信息科学，2012，28（4）：1－7.

［16］ SCHIELE S，M LLER M，BLAAR H，et al.Parallelization strategies to deal with non－localities in the calculation of regional land－surface parameters［J］.Computers ＆ Geosciences，2012，44：1－9.

［17］ WILSON J P.Digital terrain modeling［J］.Geomorphology，2012，137（1）：107－121.

［18］ LYONS R E，VANDERKULK W.The use of triple－modular redundancy to improve computer reliability［J］.IBM Journal of Research and Development，1962，6（2）：200－209.

［19］ 富弘毅，宋伟，杨学军.利用冗余进程实现 MPI程序错误检测［J］.微电子学与计算机，2009，26（9）：53－56.

［20］ REED D A，LU C，MENDES C L.Reliability challenges in large systems［J］.Future Generation Computer Systems，2006，22（3）：293－302.