数据分配策略优化的全条带遥感影像流水线并行处理

李亚林 张洪群 李山山

1(中国科学院遥感与数字地球研究所 北京 100094)2(中国科学院大学 北京 100049)



数据分配策略优化的全条带遥感影像流水线并行处理

李亚林1,2张洪群1李山山1

1(中国科学院遥感与数字地球研究所 北京 100094)2(中国科学院大学 北京 100049)

如何快速处理大区域覆盖的高分辨率全条带遥感影像是遥感应用急需解决的问题。提出分布式环境下全条带遥感影像并行处理模型。该模型采用了数据并行和流水线并行两级并行方法。首先综合考虑遥感数据及其处理算法的特殊性和分布式环境的异构性，提出一种新的数据分配策略，然后在计算节点引入流水线并行技术。实验结果显示，该模型不仅可以灵活进行复杂的数据处理，还能有效提高数据处理效率。在7个计算节点的环境下，相较于传统的串行处理方法，可获得24.32的加速比。

数据分配 全条带遥感影像 流水线 并行处理

0 引 言

随着遥感技术的飞速发展，传感器的空间分辨率和光谱分辨率大幅提高。分辨率的提高导致单幅影像覆盖的区域显著减小，而以时空演变为特征的大规模环境检测、重大自然灾害遥感监测等遥感应用迫切的需要实时或者近实时的大区域覆盖的遥感影像数据。因此，大区域覆盖的全条带数据的快速处理成为遥感数据处理研究的重点。全条带遥感影像的数据量庞大，以30 m分辨率的Landsat-8卫星影像为例，其单个全条带影像文件数据量最高可达35 GB。而且，由于遥感影像存在复杂的辐射和几何畸变[1]，其处理算法复杂度较高。传统的单机处理方式耗时较多、效率较低，为了满足数据近实时处理的需求，需要采用并行处理的方法来加快遥感数据的处理速度。

国内外学者对分布式环境下的遥感影像并行处理方法进行大量的研究。目前的研究主要从两个方面入手，一种是针对特定的遥感算法研究并行的处理模型，另一种是研究遥感数据处理任务的调度模型。针对特定遥感算法研究并行处理模型的主要有蒋艳凰等[2]提出的并行几何校正算法、刘义等[3]提出的遥感影像瓦片金字塔并行构建算法和李先涛等[4]提出的图像融合并行算法等。遥感数据的处理多为一系列算法的时序组合，以上模型难以满足全条带遥感影像的处理需求。针对调度模型的研究工作关注通过合理的调度来充分利用计算资源，进而达到提高处理速度的目的。常用的任务轮转法根据计算节点的需求进行任务分配。朱泽民等[5]提出的基于QoS的调度算法通过建立多维QoS模型并利用蚁群算法实现任务的调度。付征叶等[6]提出基于优先级的任务分配策略根据节点的负载和性能量化节点的优先级，并利用该优先级进行任务分配。然而这些分配策略忽略了遥感数据及其处理算法的特殊性，在应用于全条带遥感数据处理难以保证数据的处理效率及其通用型。

基于上述问题的考虑，本文提出一种全条带数据处理模型。该模型采用兼顾不同遥感算法对数据完整性的要求和异构环境下各节点的负载平衡的数据分配策略，并在计算节点使用流水线技术，使之既能够应对可变的处理算法，又能最大限度发挥计算节点的计算能力。最后，本文选取Landsat-8的全条带影像作为实验数据来验证本文并行处理模型的正确性及效率。

1 全条带数据并行处理模型

为了最大限度利用分布式系统的计算能力，以达到全条带遥感数据近实时处理的目的，需要解决以下两方面的问题。

(1) 合理数据分配：主要是解决如何对全条带数据进行分片，并调度到分布式系统中的计算节点上的问题。合理的数据分配应满足以下三个条件：① 数据完整性：由于全条带遥感数据处理通常为一系列算法的时序组合，而且处理算法原理多样，难以寻求一种适合于全部处理算法的数据划分方法，需根据处理算法选择合适的数据划分方法以保证各算法的正确进行；② 避免节点通信：分布式计算环境下各节点之间的通信极为耗时，合理的数据划分还应该尽量避免计算节点之间的通信；③ 负载均衡：考虑到分布式计算环境下各个计算节点具有不同的计算能力，对同一计算任务，不同的计算节点的耗时是不同，因此，在满足以上两个条件之外，还需考虑各个计算节点的性能对数据划分的影像，防止出现“水桶效应”导致全条带影像处理时间大大增加[7]。

(2) 计算节点的优化：主要包括两方面的内容：① 可扩展性：由于遥感数据处理算法的多样性，因此各计算节点应能够应对可变的处理算法，进而实现遥感影像的连续自动处理；② 数据处理的高效性：在数据合理分配的基础上，各计算节点的处理效率决定了全条带数据的处理效率，因此，需设计合理的数据处理方法以最大限度发挥计算节点的计算能力。

针对上述问题，本文设计了如图1所示的全条带遥感影像并行处理模型。该模型采用两级并行机制。第一级为数据并行，根据遥感处理算法对数据完整性的需求确定数据划分的基准，综合考虑分布式计算环境下计算节点的异构性，确定数据分配策略，依据该策略将全条带数据在空间上划分成若干独立的子图；第二级为流水线并行，对按照数据划分基准对子图进行规则分块，采用流水线的方式进行并行处理，将遥感影像的各个处理算法看作是流水线中的一个阶段，可以自由进行组合，既能实现处理算法的可定制，又可以使计算节点的计算能力得到充分利用。

图1 全条带遥感影像并行处理模型

2 全条带遥感影像数据分配策略

由第1节问题(1)的三个条件可知，合理的全条带遥感数据分配主要受到遥感数据处理算法的约束和计算节点性能的约束。为了满足多种遥感处理算法对数据完整性的要求，尽量避免节点通信，本文根据算法的原理对遥感数据处理算法进行分类。根据处理算法的要求确定数据划分的基本准则，在数据划分的基准之上，本文对各个计算节点的性能进行量化，并根据该量化指标完成数据的分配。

2.1 遥感处理算法约束因子

高分辨率遥感数据的处理包括辐射校正处理和几何校正处理两部分[8]。遥感图像的辐射校正主要是校正仪器和环境等因素导致的影像降质，几何校正的目的是消除由于传感器畸变、轨道姿态变化、地球曲率及旋转导致的图像变形，得到符合特定地图投影的新影像。全条带遥感影像的辐射和几何校正由一系列的算法组合而成，可将这些算法分为三类[9,10]：点处理、线处理和域处理。

(1) 点处理PBA(pixel_based algorithm)算法只针对图像中的单个像元，与周围像元无关，如辐射校正中的图像噪点修复、辐射定标针对这类算法，可以进行任意形式的分割，但是为了方便影像的划分及合并，一般采取规则分割的策略，如图2(a)；

(2) 线处理LBA(line_based algorithm)算法针对图像中一行像元的所有像元，如辐射校正中的错误行检查，针对这类算法，将全条带遥感影像划分成若干水平条带即可满足数据的完整性要求和避免节点通信的要求，如图2(b);

(3) 域处理RBA(region_based algorithm)算法不仅与待处理的像元有关，还与待处理像元周围的像元有关，如辐射校正中的传感器响应归一化处理和几何校正中的重采样处理； 这类算法会对遥感影像的边界产生影响，为保证数据的完整性并避免处理器之间的通信，各处理器根据插值模板的大小在本地输入的子图像的边界处冗余存储若干行像元，这样并行重采样计算时各处理器所需的像元灰度值均保存在本地，整个计算工程无需通信，加快了并行处理的速度[11]，如图2(c)。

图2 高分辨率全条带影像不同算法对应的影像划分方法

为了满足全条带遥感影像的处理需求，需将多个处理算法按照数据流向的依赖顺序组合，形成一系列的组合算法。在处理过程中，为保证计算节点中所有算法均能正确执行，则必须满足所有算法所需数据的完整性。因此，对三种类型的数据处理算法进行优先级评定，基于邻域的处理优先级最高，基于影像行的处理其次，基于像元的处理优先级最低。根据任务中算法的种类，根据算法中优先级最高的算法选择长条带遥感影像的分割策略。假设S表示待处理的遥感影像，R表示处理得到的遥感影像，A表示处理算法的集合，region表示像元的邻域， 和表示像元在遥感影像中的二维坐标，则可用式(1)表示数据的划分方法：

(1)

2.2 计算节点性能约束因子

全条带遥感影像的分块策略除了受到处理算法的约束之外，还受到并行计算环境下各计算节点性能的约束。需考虑各计算节点性能的差异，以避免出现部分节点负载过大、部分节点零负载或轻负载的情况，使不同类型的计算节点相互协作，高效地完成生产任务。本文引入计算节点的性能函数，根据该性能函数确定每个节点处理的数据量。

定义1节点的性能函数:计算节点性能的评价指标，以节点完成特定数据量的遥感影像的时间作为衡量标准。节点的性能受到数据传输速度和节点计算能力两个因素的影响。在分布式存储系统中，根据遥感影像的特性对其进行冗余存储和分片存储，并通过合理的数据布局对数据传输进行优化，可以忽略数据分布对数据传输的影响，可认为各计算节点的数据传输时间消耗由传输数据量和网络带宽决定[12]。Esper[13]公布的数据表明，CPU是影响数据处理性能的关键，因此，本文采用每秒浮点运算次数(TFLOPS)来表征计算节点的计算能力。节点性能函数如式(2)所示：

(2)

式中，D表示待处理的数据量；TFLOPSi表示节点i的每秒浮点运算次数；B表示从分布式文件系统到计算节点的网络带宽，α与β表示网络带宽和节点计算能力对节点性能的影响程度，由遥感数据密集指数来确定[14]。α与β之和为1；Ci表示节点i算法的复杂度。全条带数据处理中各算法的复杂度如表1所示。

表1 全条带数据处理中各算法的复杂度

在计算节点处理算法复杂度的时候同样需要考虑算法组合的影像。假设节点i的数据需要经过j个算法的处理，则节点i的算法复杂度Ci可由式(3)确定：

Ci=Max{Ci(A1),Ci(A1),…,Ci(Aj)}

(3)

2.3 全条带数据的分配

为了充分分离计算和存储资源，使计算节点专注于数据的处理，存储服务器专注于数据的存储和分发，本系统采用Lustre文件系统。Lustre是透明的全局文件系统，计算节点上的客户端可以根据分配的任务透明地获取文件系统中的数据，而不需要考虑其实际存放的位置。存储服务器负责实际文件系统的读写操作以及存储设备的连接，元数据服务器完成文件系统的目录结构、文件权限和文件扩展属性的管理以及维护整个文件系统的数据一致性和响应客户端的请求。Lustre文件系统对大数据读写做了优化，在全条带遥感数据处理中，可以提供高性能的I/O吞吐率，减小了文件I/O对系统效率的影响。Lustre文件系统的架构如图3所示。

图3 Lustre文件系统架构图

在数据分配过程中，首先根据遥感处理算法约束因子和计算节点性能约束因子确定分配策略，然后各计算节点内的Lustre客户端并行地从Lustre服务端中读取其需要处理的数据。其具体过程如下：

步骤1启动任务调度服务器，接收计算节点的注册信息，并根据遥感算法的特殊性，计算各计算节点的计算量。

步骤2将计算量信息发送给各计算节点。

步骤3各计算节点从MDS中读取待处理数据的元数据信息。

步骤4各计算节点从OSS中读取其需要处理的数据。

3 计算节点流水线处理模型

全条带遥感数据的处理可以分为若干个步骤，各步骤之间存在单向的数据依赖关系，且没有反馈或者迭代处理。因此，采用流水线并行技术以满足第1节问题(2)提出的可扩展性的要求，并通过优化流水线的调度充分利用节点的计算资源以满足问题(2)提出的数据处理高效性的要求。而且，在流水线数据处理中，各计算节点不需要等到该节点所有的数据全部传输完毕再进行数据处理，而是当数据达到一定数量后即开始进行处理，可以减少数据I/O的等待时间。

在流水线处理中，将遥感影像处理看作是一个顺序执行的处理链。处理链中的算法为流水线的各个阶段，将分块的数据以数据流的形式从流水线的起点连续输入，上一阶段将处理后的数据传入下一阶段继续进行其他处理，各自独立完成处理任务。当全条带遥感影像应用目的不同时，根据其应用需求从遥感算法集中选取合适的遥感算法构成数据处理链，并在流水线处理中进行的阶段组合即可适应新的处理需求，进而达到算法可定制的目标[15]。流水线的设计示意图见图4所示。

图4 流水线的设计示意图

流水线中的各个操作以重叠方式执行，而且由于计算节点一般都是多核心的，流水线处理可以使得所有的处理核心一起工作，最大限度提高了CPU的利用率，提高整个数据的处理效率。但在遥感数据处理中，各处理算法的时间复杂度并不完全相同，这导致流水线中各个阶段的处理速率不尽相同。因此，不能直接将前一阶段的处理结果直接送入下一阶段进行处理，各个步骤之间需要一定的缓存。本文在各处理阶段之间加入缓冲区来平衡两个处理阶段吞吐率的差异，并通过线程调度，即在流水线处理中调整各阶段的资源占用以充分利用计算资源，来尽量减少吞吐率差异。

定义2阶段过载：流水线处理中某个阶段的数据处理速度低于数据的到达速度，则称此阶段过载。

在流水线处理中，当某个阶段过载时，可通过阶段内控制器，增加该阶段的线程数来提高CPU的利用率，进而提高该阶段的数据处理速率。但是，当CPU的利用率达到一定程度之后，如果继续增加处理线程，则会造成由于频繁的线程切换导致系统开销增加，处理速度降低。Welsh等[16]指出，当CPU的利用率低于75%时，线程切换的开销呈线性增长，大于75%时则呈指数级增长。为减少多线程的开销，将75%作为线程总量的上限，当CPU利用率小于75%时，通过阶段内控制器增加过载阶段的线程数；当大于75%时，通过阶段见控制器，移动部分非过载阶段的线程到过载阶段，以保证整个数据处理流程能够高速进行。计算节点流水线调度优化示意如图5所示。

图5 计算节点流水线调度优化示意图

4 实验验证

4.1 实验环境

为验证本文提出的长条带数据处理方法的正确性及高效性，选取2014年7月30日获取的LANDSAT-8全条带数据作为实验数据。该全条带数据数据量为35 GB，遥感影像覆盖从内蒙古到广西的区域。

实验在由10个节点构成的集群下进行：管理节点为：2× Intel Xeon E5 4610，2.4 GHz,16 GB内存，600 GB热插拔SAS硬盘，计算节点有三种配置，如表2所示。存储系统为Lustre文件系统，软件环境为CENTOS 6.5。

表2 硬件及软件测试环境

4.2 正确性验证

本文对实验数据进行辐射和系统级几何校正，该处理为遥感影像处理的广泛应用，具有代表性。同时该处理包含了几类遥感算法，能够清楚地验证本文影像处理的正确性，其处理过程主要包括：影像噪点的去除、辐射定标、辐射归一化和系统级几何校正。

实验数据处理前后的影像如图6所示，由(b)可以看出，处理后的遥感影像并没有缺失或者存在未处理的情况，证明数据分块正确，所有的数据都得到了处理。且由(c)与(d)的对比可以看出，遥感影像的噪点、条带噪声等都得到了消除，证明所有的处理步骤都得到正确的执行。

图6 处理前后的长条带影像对比图

此外，几何校正之后几何定位的误差图如图7所示，长条带结果的最大误差为80.7 m，最小误差为28.8 m，平均误差为59.8 m。几何校正后的全条带遥感影像的误差达到了系统级几何校正的精度要求，且几何误差分布均匀，证明几何校正得到了正确的执行。

图7 处理后的长条带影像定位误差图

上述两点可以证明，全条带遥感影像的各个处理得到正确执行，证明本文方法的正确性。

4.3 效率验证

为了验证本文方法的效率，本文从数据分配策略效果、流水线处理加速效果和总体处理效率三个方面进行分析。

4.3.1 数据划分策略效率分析

在7个计算节点的分布式环境中，分别采用常用的轮询的方法和本文的数据分配策略将全条带数据分发到各计算节点，各计算计算节点串行执行接收到的数据。统计各个节点完成数据处理所消耗的时间如图8所示。

图8 各节点处理消耗的时间

由于传统的轮询方法只是简单地将任务分发给各个计算节点，未考虑到处理算法导致的计算节点间的通信以及各计算节点的计算能力。因此，图8中存在个别节点处理时间较长的情况，严重影响全条带数据的处理速度。本文方法则综合考虑处理算法的特殊性和各计算节点计算能力的差异，在尽量避免节点间通信的前提下，按照各计算节点的计算能力向其分发数据。因此，本文方法的各个节点的运行时间基本相同，进而保证整个全条带数据处理任务能快速完成。

4.3.2 流水线并行效率分析

选取一个计算节点，向其分发4 GB的数据，统计流水线并行处理方法和传统的串行处理方法完成数据处理任务所消耗的时间如表3所示。

表3 流水线并行和串行方法处理4 GB数据消耗的时间

由表3可以看出，采用流水线并行可显著的减少数据处理消耗的时间。这是因为两方面的原因：1) 流水线处理不必等待所有的数据都分发到节点上再进行处理，减少了数据I/O时间；2) 各处理流程的并行化，充分的利用了节点的计算能力。

4.3.3 系统整体处理效率分析

对全条带遥感数据分别使用本文方法和传统的单机串行方法进行处理，通过对比两种方法消耗的时间来测试本文方法的整体性能。本文方法的运行时间及相较于传统方法获得的加速比如表4所示。

表4 计算节点数目对处理性能的影响

由表4和图9可以看出，本文方法相较于传统方法，处理效率显著提高，且随着参与全条带数据处理的计算节点数目的增加，处理时间大大减少，加速比不断增加，这说明本文提出的并行全条带数据处理方法能够有效提高数据处理速度。

图9 本文方法在不同数目计算节点下获得的加速比

5 结 语

本文提出的分布式环境下的全条带数据处理模型，采用兼顾不同遥感算法对数据完整性的要求和异构环境下各节点的负载平衡数据分配策略 ，并在计算节点使用流水线技术。本模型有以下特点：1)数据分配策略兼顾遥感数据及处理算法的特点和分布式环境的特点，在保证数据处理正确进行的前提下，有效减少了节点的通信，提高了数据的处理效率。2)在节点采用流水线技术使计算节点能够应对可变的处理算法，并通过线程调优等方法最大限度地发挥计算节点的计算能力。实验结果表明，本文模型能够快速有效地完成全条带遥感影像的处理，在7个计算节点的环境下可获得24.32的加速比。下一步将重点研究本模型在更大规模分布式计算环境下，针对国内外不同遥感影像的适用性，从而加以推广和改进。

[1] 周海芳.遥感图像并行处理算法的研究与应用[D].国防科学技术大学,2003.

[2] 蒋艳凰,杨学军,易会战.卫星遥感图像并行几何校正算法研究[J].计算机学报,2004,27(7):944-951.

[3] 刘义,陈荦,景宁,等.利用MapReduce进行批量遥感影像瓦片金字塔构建[J].武汉大学学报:信息科学版,2013,38(3):278-282.

[4] 李先涛,曾志,张丰,等.基于集群的海洋遥感图像融合并行计算策略[J].计算机应用与软件,2012,29(1):84-87.

[5] 朱泽民,张青.基于多维QoS和云计算的资源负载均衡调度研究[J].计算机测量与控制,2013,21(1):263-265,281.

[6] 付征叶,凡高娟,王俊岭.遥感影像并行处理中基于优先级的任务分配策略[J].计算机工程,2014,40(2):48-51,57.

[7] 李军,李德仁.分布式遥感图像处理中的若干关键技术[J].武汉测绘科技大学学报,1999,24(1):15-19.

[8] 李德仁,童庆禧,李荣兴,等.高分辨率对地观测的若干前沿科学问题[J].中国科学:地球科学,2012,42(6):805-813.

[9] 黄国满,郭建峰.分布式并行遥感图像处理中的数据划分[J].遥感信息,2001,6(2):9-12.

[10] 沈占锋,骆剑承,陈秋晓,等.高分辨率遥感影像并行处理数据分配策略研究[J].哈尔滨工业大学学报,2006,38(11):1968-1971,1976.

[11] Ma Y,Wang L,Liu D,et al.Distributed data structure templates for data-intensive remote sensing applications[J].Concurrency and Computation:Practice and Experience,2013,25(12):1784-1797.

[12] 宋杰,李甜甜,闫振兴,等.数据密集型计算中负载均衡的数据布局方法[J].北京邮电大学学报,2013,36(4):76-80.

[13] Motwani R,Widom J,Arasu A,et al.Query processing, resource management,and approximation in a data stream management system[C]//IEEE VLSI Test Symposium,2003:245-256.

[14] Ma Y,Wang L,Liu P,et al.Towards building a data-intensive index for big data computing-A case study of Remote Sensing data processing[J].Information Sciences,2015,319:171-188.

[15] 翟晓芳,龚健雅,肖志峰,等.利用流水线技术的遥感影像并行处理[J].武汉大学学报:信息科学版,2011,36(12):1430-1433.

[16] Welsh M,Culler D,Brewer E.SEDA:an architecture for well-conditioned,scalable internet services[C]//ACM SIGOPS Operating Systems Review. ACM,2001,35(5):230-243.

PARALLEL PROCESSING OF LONG STRIP REMOTE SENSING IMAGE BASED ON PIPELINE WITH DATA DISTRIBUTION STRATEGY OPTIMISATION

Li Yalin1,2Zhang Hongqun1Li Shanshan1

1(InstituteofRemoteSensingandDigitalEarth,ChineseAcademyofSciences,Beijing100094,China)2(UniversityofChineseAcademyofSciences,Beijing100049,China)

How to quickly process huge area-covering and high-resolution long strip remote sensing image is the problem of remote sensing application to be urgently resolved. Aiming at this problem, this paper proposes a parallel processing model for long strip image in distributed environment. The model adopts two-stage parallel approach with data parallel and pipeline parallel. First, we propose a new data distribution strategy by comprehensively considering the particularity of remote sensing data as well as its processing algorithm and the heterogeneous nature of distributed environment; then we introduce pipeline parallel technology to each computing node. Experimental results show that the model can flexibly carry out complicated data processing, it can effectively improve the efficiency of data processing as well. Under the condition of 7 computation nodes, it is able to acquire the speedup of 24.32 compared with traditional serial processing method.

Data distribution Long strip remote sensing image Pipeline Parallel processing

2015-03-02。国家自然科学基金项目(41301383)。李亚林，硕士，主研领域：遥感数据处理相关研究。张洪群，教授级高工。李山山，副研究员。

TP751

A

10.3969/j.issn.1000-386x.2016.11.028