基于MPI的数据融合并行化容错技术研究∗

张路青

（海军驻中南地区光电系统军事代表室 武汉 430223）

1 引言

数据融合是对来自多源的信息和数据进行检测、关联、相关、估计和综合处理，以得到精确的状态和身份估计，以及完整、及时的态势、威胁和重要程度的估计［1］，是去粗取精、去伪存真、由此及彼、由表及里的过程。随着计算机、电子技术的高速发展，现代战场情报探测手段更加丰富，信息量都有了很大的增长，可用的情报来源（岸、海、空、天、潜等）和情报种类（电磁、红外、光电、水声等）越来越多。同时，对信息感知和信息融合能力的要求也越来越高。单机难以负担大规模数据的实时、精确计算，需要引入并行计算技术，采用高性能并行并行融合方法。目前，MPI（Message Process Interface）是科学计算领域中广泛使用的标准化并行编程环境，具有移植容易、扩展性好、结构简单高效等多种优点［2］，但在容错性方面还达不到融合系统并行化的要求随着并行计算集群节点数的增加，融合系统发生故障的概率也迅速增大，对于拥有几万个处理器的大规模并行融合系统，平均故障时间可达小时级［3］，因此必须考虑容错机制。本文先分析MPI容错的研究进展，再根据数据融合系统的特点提出一种在融合系统中引入MPI容错的解决方案。

2 基于MPI的容错技术的研究进展

系统并行计算系统的错误主要来自于节点失效、进程异常、终止和网络故障这三个方面。实现MPI的容错方法有很多，有硬件容错和软件容错。硬件容错实时性好，纠错速度快，但是可扩展性不好，需要额外的软件支持，可能与消息传递机制不兼容［4］。软件容错又可以分为回卷恢复和副本冗余两种。

2.1 回卷恢复

回卷恢复也就是在系统正常运行的适当时刻设置检查点，保存未出错时的状态，当出现故障时，MPI应用程序回卷到最近的一次检查点时的状态，恢复状态后继续执行。现阶段回卷恢复主要包括检查点/回卷（CRR，Checkpoint-based Rollback Re⁃covery）和日志/回卷（LRR，Log-based Rollback Re⁃covery）两种。LRR也依赖于检查点，只是增加了消息日志，日志由进程历史上发生的事件组成，保存了日志就可以重新运行位于最近的检查点和错误发生点之间的那部分程序。日志又分为乐观日志、悲观日志和因果日志［5～7］。检查点／回卷可以分为系统（内核）级检查点［4，6～7］和应用（用户）级检查点［8～10］。常用的系统级检查点工具有Epckpt、Crak、BLCR等，基于用户层开发的工具有Condor、Libckpt等工具［8］。

检查点无论是串行还是并行，同步或者异步，协同设置或者独立设置，都必须考虑全局一致性状态。一个消息传递系统的全局状态包括所有参与进程的状态信息以及通信通道的状态［11］。只有检查点或者日志记录的是回卷时全部必要的状态信息，回卷才能正确的恢复MPI程序。全局一致性状态的必要性是保存的全局状态中不包含孤立消息。孤立消息也就是消息的接收事件被记录，但是发送事件却没有被记录。如图1所示，P1，P2，P3是三个MPI进程，图中消息m1在P1处已经记录发送，虽然在P2处没有收到，但是消息被保存于消息信道里面（这样的消息被叫做中途消息）。如果程序运行到B点发生故障回卷到CK0，则不会造成不一致状态。图中消息m4已经从P2发送到P3中，但是P2并未记录（这样的消息被叫做孤立消息）。如果程序运行到C点发生故障，回卷到CK1，则P2会再发送一次m4消息给P3，造成全局不一致状态。

图1 一致性状态与不一致性状态

文献［4］介绍了回卷恢复和CO-CRR协议，通过对每个进程设置检查点广播的方式避免孤立消息，但是相关性能还需进一步测试。文献［5］提出的MPI容错系统采用了基于发送方储存的乐观消息日志，通过运用Venkatesan算法独立异步的为每个进程设置检查点，然后通过基于消息计数的协同式检查点协议恢复到检查点。文献［7］首先介绍了基本的系统是检查点协议（CO-CRR）并进行了开销分析，然后利用可重建的全局检查点设计了一个基于可重建检查点的非阻塞协同式检查点协议。文献［8］主要利用容错RAID的数据布局方法，在应用级做检查点，对每个MPI进程的计算数据做内存编码，文中提出的内存检查点方法可以有效防止系统出现数据存取错误。文献［10］提出了使用检查点的源到源转换工具ALEC在期望保存点设置预编译指令的方法，通过预编译确定需要保存的关键数据。这种方法可以有效的减小检查点文件的大小，减少了系统设置和恢复检查点的开销。文献［11］采用了基于消息驱赶的协调式检查点协议设置检查点，分别论述了检查点设置、基于MPD的错误探测、处理及恢复流程。

BLCR是伯克利实验室未来技术组的研究者为Linux操作系统设计实现了一种Checkpoint/Restart技术。它使用户不需要修改应用程序的源码就能让绝大部分应用软件拥有执行Checkpoint/Restart能力。新版的MPI不再使用MPD进程管理，而是采用Hydra进程管理器。Hydra进程管理器使BLCR可以作为MPI的一个可扩展用户空间插件自动编译到MPI系统中。为了在编译MPI使加入BLCR功能，需要在编译前将BLCR的路径加入到MPI的配置选项里，例如在configure命令后面添加--with-blcr=＜BLCR_INSTALL_DIR＞即可。

在MPI中，当程序出错时，会返回一个错误代码，默认的错误返回代码是MPI_ER⁃RORS_ARE_FATAL。MPI会把任何返回这个代码的错误，不管能处理还是不能处理，都当成致命性的错误，从而导致错误进程所在通信域的所有进程集体退出。可以在编译配置时加入“-disable-au⁃to-cleanup”选项，使进程只返回错误代码。

MPI支持两种主要的设置检查点的方式—定时设置和用户指定设置。通过使用指令mpiex⁃ec-ckpointlib blcr-ckpoint-prefix/tmp/app.ckpoint-ckpoint-interval 3600-f hosts-n 4./app，可以以3600S的定时间隔设置检查点。用户还可以通过给mpiexec发送SIGUSR1信号通知BLCR设置检查点。

2.2 副本冗余

副本冗余，也就是为正在运行的程序设置副本。副本冗余也包含很多层级和机制。譬如，按照层级分为集群冗余、节点冗余、进程冗余［12～13］，按照机制分为计算冗余［12～13］和通信冗余［14］等等。

文献［12］主要研究了三模冗余进程机制（并行MPI程序的任意一个进程P0都存在两个冗余的副本P1和P2，P0与其对应的冗余副本P1和P2进行完全相同的运算，发送和接收完全相同的消息。称由这样3个进程构成的整体为三模冗余进程簇），介绍了一种面向MPI大规模并行计算的可扩展三模冗余容错机制，主要从传统TMR的开销角度计算分析出传统三模冗余进程机制的局限性，对三个作业进程之间的通信和数据比较选择进行了优化，减少了数据通信和比较的开销。文献［13］提出了一种基于进程冗余的MPI程序容错机制REDReP，REDReP为运行并行程序的每个MPI进程创建一个冗余副本，当该进程需要与其他进程通信时，先比较两个冗余进程的结果，如果相同才继续执行后续任务。文献［12］和文献［13］都从冗余进程之间数据通信、数据比较等角度分析并优化了开销。

文献［14］主要介绍了一种基于故障接管的网络容错策略。文中认为并行计算主要的顾虑是消息是否到达，所以为主通信协议（精简通信协议RCP）设计了一个备份通信协议（以太网），并设计了协议虚拟接口层实现协议的无缝切换，整个体系结构由消息接口层、容错协议层、多协议层和守护控制进程组成。

3 数据融合系统的并行容错分析

3.1 数据融合系统的结构特点

系统并行计算系统的错误主要来自于节点失效、进程异常、终止和网络故障这三个方面。实现MPI的容错方法有很多，有硬件容错和软件容错。硬件容错实时性好，纠错速度快，但是可扩展性不好，需要额外的软件支持，可能与消息传递机制不兼容［4］。软件容错又可以分为回卷恢复和副本冗余两种。

数据融合系统主要包括数据配准、数据相关、数据滤波与合成。具体到航迹融合，主要是时空配准、数据预处理、航迹滤波、航迹相关、航迹合成等功能模块（如图2所示）。时空配准将各传感器探测到的目标位置转换到同一坐标系，探测到目标的时间也建立统一时序，并估计传感器的系统误差和参数。数据预处理剔除异常数据和虚假目标。航迹滤波是对一个观测序列进行数据处理，以获得更精确的态势估计与预测的过程。航迹相关是信源间的航-航互联过程，其目的是确定哪些航迹数据来源于同一个目标，为去除重复信息、进行目标信息提纯奠定基础。航迹合成就是对不同信源相关后的航迹进行合成，以获得更精确的态势估计与预测的过程。从图2可以看出，整个航迹融合流程逻辑序贯性强，数据之间的耦合性大，这些都对融合的并行及容错造成了很大的困难［15］。

3.2 数据融合系统中引入并行容错架构分析

由图2可知，航迹融合系统中各功能模块序贯性强，且有相对严格的处理顺序，所以试图从流程方面进行并行任务划分效率不会很高。本文采用文献［15］和文献［16］中论述的基于网格划分的方法。即将多部雷达输出的航迹信息根据空间位置关系和航迹间的模糊关联关系动态聚类成多个不同的区域，区域内的航迹间具有相关性，不同区域内的航迹相互独立。从而可以将相同区域内的航迹分配到同一个任务节点进行处理，这样各任务节点就具有独立性，可以充分发挥并行处理的优势。并行融合架构如图3所示。

图3 以区域为单位进行并行任务划分

综合2.1节的分析可知，基于回卷恢复的容错机制主要包括保存检查点状态和恢复继续执行两个步骤。检查点保存和恢复的开销与集群系统规模和所设置检查点的时间和数量都有关系［9］。融合程序属于计算密集型的程序，设置协调式检查点的性能要优于独立设置检查点，本文选择使用系统级检查点设置工具BLCR。一般来说，采用回卷恢复进行容错设计比较耗时，而指控系统需要的情报信息不仅要求准确可靠，更要求快速及时，所以单纯靠回卷恢复并不能满足系统容错的设计需求。本文在回卷恢复的基础上提出了回卷恢复与层级冗余任务进程相结合的机制。层级冗余任务也就是根据任务在整个融合程序中的处理次序和重要性进行划分。根据任务类型结构进行冗余既减轻了硬件开销，又充分利用了冗余容错的机制，提高了整个系统的可靠性和灵活性。

4 基于任务冗余的MPI并行架构设计的实现

通过前面的分析可知，航迹融合程序一般包括时空配准、数据预处理、航迹滤波、航迹相关、航迹合成等功能模块。这几个模块比较耗时和容易出错的是航迹滤波、相关和合成，所以并行的设计和相关容错的设计围绕这三个功能模块展开。具体过程如图4所示，从多源传感器输出的航迹先经过报文接收放到融合程序里进行时空配准，然后通过简单的预处理去掉错误异常数据和虚假目标。把预处理后的数据根据网格聚类划分为若干处理区域，再将各个区域通过数据分发模块分发到指定的任务节点上进行滤波、相关和合成。航迹滤波、航迹关联和航迹合成任务节点设一个冗余处理进程。这个冗余处理进程是通过数据分发模块进行切换的，如果没有任务节点出错，则不将数据推送到冗余进程。如果系统的心跳进程检测到某个处理单元出现错误或者负载太大，就会分发数据到冗余进程，出错任务进程执行检查点/重启技术恢复进程，这时重启恢复后的进程变为冗余进程，等待下一次程序出错。为了保证程序进程切换时不出现数据丢失，要求数据分发进程保留发送到各任务节点的最后一次数据的拷贝。状态检测进程一旦发现某个节点出现错误，切换到冗余任务节点后，将上一次分发给出错进程但是没有处理完的数据再次发送一遍。

图4 MPI并行容错设计架构

错误处理与恢复流程：

1）心跳监控进程检测到某个任务节点出现异常或者其它故障，心跳进程向数据分发任务进程发送封装了故障任务节点信息的消息报。

2）数据分发任务进程停止向故障任务节点分发数据。数据分发进程通过比较分发到故障节点输入和输出的数据确定正在故障节点中处理尚未输出的数据。并将这部分数据重新分发到冗余任务节点，冗余任务节点开始接收数据并正常工作。数据分发进程不再向故障任务节点分发数据，也不再接收故障任务进程输出的数据。

3）任务节点管理进程向故障任务节点发送重启进程的指令。故障任务节点开始寻找最近的检查点位置，然后重新启动进程，丢掉进程正常工作时的中间数据，开始等待分发数据。

4）这时，原故障进程就变为冗余任务进程。如果再一次故障，继续回到1）～3）进行处理。

5 仿真验证与分析

为了测试验证所设计的并行容错算法，将基于MPI的航迹融合程序部署在使用交换机连接的局域网系统中。局域网有三台配置相同的计算机（主频3.4GHZ的i7 2600，2G内存，操作系统为Solar⁃is11）组成。接入4部扫描周期2s的雷达，实际处理目标1500批。将融合后的输出接入态势软件显示。在相同时间内，串行处理效果如图5（a）所示，加入并行容错的执行效果如图5（b）所示。由图可看出，串行的融合算法执行效率低，相同数据量输入条件下，串行的程序将大部分数据放入缓冲区，航迹融合速度慢，航迹拖尾短；而并行则能快速执行算法，占用内存少，航迹拖尾长。

图5 相同时间内算法执行累积输出对比

MPI程序没加入容错时，进程域中某个进程出现错误就会导致所有进程全部退出。通过手动停止某个进程的方式可以验证冗余任务进程是否在进程出现故障时接手工作，但是基于检查点和冗余任务进程相结合的容错效率则需要进一步的验证。

6 结语

数据融合系统并行化虽然有很多的困难，但是对并行化和相关容错的需求很迫切。本文首先通过文献中关于MPI并行的论述和分析数据融合系统并行化所存在的困难，提出一种适合航迹融合系统的并行容错解决方案，即通过网格聚类划分并行任务，通过检查点和任务进程冗余相结合的方法设计容错方案。整个设计有一定的实用性，不过容错效果有待进一步的验证和改进。