基于MPI的遥测源码多站拼接并行化算法研究∗

张志国 张慧娟 徐洪洲

（91550部队 大连 116023）

1 引言

完整、无误码的遥测原始数据是进行遥测事后数据处理的基础。实际任务中，一台套遥测设备因作用距离的限制，只能接收一段时间内的遥测数据；受设备工作状态、遥测传输信号稳定性等因素影响，单台遥测设备一般接收不到完整、无误码的遥测数据。为保证可靠性，在一个任务时段内往往有多台套遥测设备同时接收遥测数据。为得到一组完整的遥测数据，需要将多台套遥测设备测到的遥测数据拼接组合。由于遥测数据量大，遥测源码多站拼接工作需要进行上千万点的数据比较和大量的磁盘I/O操作，因此遥测数据源码拼接需要耗费很长的时间，目前此功能已成为制约遥测数据快速处理的瓶颈。为加快遥测数据处理速度、缩短遥测处理时间，迫切需要对遥测源码拼接工作进行优化。目前遥测源码拼接工作是在一台计算机上进行的，可以考虑将拼接作业分配到局域网内的多台计算上，使整个拼接工作实现并行化，效率将会得到很大的提升。文中先介绍MPI并行化基本概念，再阐述遥测源码多站拼接并行化算法，并给出实例和结果分析。

2 MPI并行化概述

2.1 并行计算

所谓的并行计算（parallel computing），首先将任务进行分解，细分为多个子任务，然后在并行机上将这些子任务分配给不同的处理器［1～4］。这些处理器之间通过相应的技术手段进行通信，并发地执行子任务［7］。这样可以充分地利用计算资源，提高求解速度，缩小求解应用问题规模。

为保障并行计算的成功进行，以下三个基本条件是必备的［5，6］：

1）并行机。两台以上可以通过网络互连，互通的处理机。

2）所要解决的问题必须具备并行度［7］。也就是说，应用问题能够分解成多个子任务，这些子任务可以并发地执行［8～9］。而并行算法的设计核心，就是将应用问题进行拆分，分解为多个子任务同时执行［10］。

3）并行编程。在并行编程开发环境下，将原有串行程序改造为并行程序，从而实现应用问题的并行化求解。

2.2 MPI编程

MPI（message passing interface），从字面上理解是消息传递接口。它并非一种编程语言，而是一组具有近百个函数可供调用的编程模型。它提供的这些函数可以在C语言和Fortran中进行调用，完成子任务进程间的通信［11］。

MPICH是MPI最流行的非专利实现，由Ar⁃gonne国家实验室和密西西比州立大学联合开发，具有更好的可移植性［12］。MPICH的开发与MPI规范的制定是同步进行的，因此MPICH最能反映MPI的发展与变化。MPICH的主要特点是：开源、高效、可移植性好、功能强大；支持多核、多程序多数据编程、对称多处理系统、异构集群系统和大规模并行计算系统。

主从（Master/Slave）模式是常用的MPI并行编程模式，它由运行在主节点的主程序和多个运行在子节点的子程序构成。主进程负责进程初始化、任务分配、子结果收集、最终结果显示等任务。子进程负责主进程任务数据接收、数据计算、结算结果提交等任务。主程序工作流程如下：1）初始化并行计算环境；2）数据划分并进行子节点任务分配；3）将数据和子计算任务发送到各个子计算节点；4）等待接收各子节点的计算结果；5）将各子节点的计算结果整合为一个完整结果，并显示输出。子程序工作流程如下：1）等待接收主进程的计算数据；2）根据标识识别出主进程分配给本子进程的任务，并进行计算；3）将计算结果发送给主进程。

3 遥测源码多站拼接并行化方法

现有的遥测多站拼接串行算法如下：

1）分离提取遥测数据和时间，形成数据文件和时间文件，时间文件的一个时间点对应数据文件的一个全帧数据。此步对所有测站数据（分别编号为D1，D2，D3，…，Dm）分别进行；

2）找到所有测站接收的最早遥测数据时间T1及最晚接收的数据时间T2；

3）从T1开始，以一帧的时间间隔为步长，在所有测站中寻找在每个数据时间节点Tn对应的完整遥测帧，直到T2结束；其中，在所有测站中寻找在每个数据时间节点Tn对应的完整遥测帧需要进行多次搜索和比较，其具体过程如下：（1）依次搜索D1，D2，D3，…，Dm在数据时间节点Tn对应的遥测帧；（2）比较Tn对应的遥测帧，取相同个数最多的遥测帧为Tn点对应的遥测帧加入到完整遥测帧序列。其中，（1）步搜索，每个测站数据最多需要进行n次搜索，最少需要一次搜索；（2）步使用两两比较的方式，在测站数量m是2的几何级数时，所有测站都相同的情况下需进行次搜索；如有8个测站，所有测站在Tn节点都有遥测帧、且遥测帧相同时，需进行4+2+1=7次比较；测站数据有异常情况导致数据帧不同的情况下，需进行的比较次数要多于7次。在测站数量不是2的几何级数时或者遥测帧有不相同的情况下，比较次数更多。（1）、（2）步骤中多次的搜索和比较，是导致遥测源码拼接耗费时间较长的主要原因。

为了能够使用MPI计算框架，需要对遥测源码拼接算法进行改进：

第1）步，由于是对多个测站的遥测数据文件分别进行处理，可以将作业分配到不同计算机上进行；这一步有大量的I/O操作，计算机的I/O是瓶颈，通过多台计算机并行处理；

第2）步耗费时间很少，不需要并行处理；

第3）步，是耗时最多的步骤，需对其算法进行并行化改造，以提高计算效率。

（1）主控制节点将数据拼接工作尽量平均，可以通过时间段平均或者数据量平均等方法，分为多个子段，有几个计算节点分几个子段；

（2）每个计算节点并行对分到的子段进行遥测源码拼接；

（3）计算节点计算完成后，将计算结果反馈给控制节点，由主控制节点完成各个子段结果的拼接工作。

4 算例与分析

通过单机单核计算和多机并行化计算两种方式，对某三次任务的遥测数据进行了多站拼接的耗时测算，结果如表1～表3、图1～图3所示。

表1 6站每站100M拼接耗时

表2 6站每站200M拼接耗时

表3 6站每站400M拼接耗时

图1 6站每站100M拼接耗时结果比对

图2 6站每站200M拼接耗时结果比对

图3 6站每站400M拼接耗时结果比对

从实验数据可知，在目前多站遥测体制条件下，并行算法基本上与测量站个数无关，只与单站数据大小、子节点数量正相关；理论上只要计算节点足够，便可完成多站遥测体制下的数据拼接任务。

5 结语

针对当前多站体制下遥测源码拼接较慢，制约遥测数据快速处理的问题，文中提出利用MPI并行计算框架，将遥测源码拼接串行算法改进为并行算法。算例结果表明，该方法能充分地利用局域网内计算资源，大大提高了遥测源码拼接速度，可以用于遥测事后数据快速处理。

［1］刘晶.基于PVM的并行计算［J］.广东石油化工学院学报，2012（4）：34-35.

［2］杨忠志，张晶，刘翠，等.ABEEMσπ/MM模型中静电相互作用能的并行化［J］.辽宁师范大学学报，2009（4）：457-461.

［3］曾芷德.对并行测试生成理论的一点综述［J］.桂林电子工业学院学报，2000（4）：100-105.

［4］赵俊军，刘士锋，张直云.基于网络分割技术的交通最短路径应用［J］.昆明冶金高等专科学校学报，2015（5）：60-64.

［5］李永兵.并行编程环境与工具［J］.长治学院学报，2009（2）：41-43.

［6］廉灿国，李军营，王长江，等.并行算法在弹道与诸元计算中的应用［J］.弹箭与制导学报，2011（4）：162-164.

［7］龙柏.并行计算平台上的数据索引技术研究［D］.合肥：中国科学技术大学，2011：52-55.

［8］魏秋娟.网格环境下电力营销系统任务调度的研究［D］.北京：华北电力大学，2011：32-37.

［9］符丁，黄汉堂.基于本体和多Agent的面向任务协同编程［J］.计算机工程，2010（9）：47-49.

［10］张宇.对Linux集群在并行计算中的应用研究［D］.广州：中山大学，2009：45-56.

［11］赵少林.广域网协议在HPC集群上的应用分析［D］.郑州：郑州大学，2005：23-24.

［12］张伟.航空电子系统中的光纤通道技术研究［D］.西安：西北工业大学，2005：34-37.