陈亮，李景山

(1.中国科学院空天信息创新研究院，北京 100094；2.中国科学院大学 电子电气与通信工程学院，北京 100094)

0 引言

遥感卫星数据预处理系统是卫星地面系统的重要组成部分之一，是获取卫星产品数据的重要环节，国内外很多学者和组织都对遥感卫星数据处理系统及预处理算法进行了深入的研究。大型卫星图像数据处理中心越来越多地开发模块化的多任务开放式架构[1]。基于工作流的预处理系统具有较为广泛的应用[2-3]，根据不同卫星的预处理要求，将卫星的预处理任务以工作流形式串联起来，解决了遥感卫星数据预处理系统多卫星处理功能扩展问题。

随着预处理系统中新的卫星处理功能不断集成，预处理任务的复杂程度也随之提高，主要体现在以下三个方面。一是任务类型复杂。不同卫星、不同处理阶段都对应不同的任务类型。二是任务组合复杂。同一时刻需对多种任务类型进行调度。三是任务需求复杂。根据处理要求，各卫星处理任务在常规和应急情况下所处理的数据时效性和系统吞吐量要求存在差异。复杂的预处理任务对调度算法提出了更高的要求。

本文所要研究的内容是通过建立调度模型对机群环境下的遥感卫星数据预处理系统中的复杂任务进行调度，在满足预处理数据时效性要求的同时，提高系统吞吐量。相关概念定义如下。

1)系统吞吐量。系统在单位时间内的工作量。具体在遥感卫星数据预处理系统中，吞吐量表示为单位时间内处理原始码流数据的总数据量。

2)数据时效性。是指从接收到原始数据开始，到完成目标产品生产，并向用户分发的整个过程的时间要求。

1 调度算法分析及问题描述

传统调度算法主要从时间和资源两个角度对任务进行调度，如最基本的调度算法包括先来先服务(first come first serve，FCFS)，根据任务所需资源数目多少而采取的大任务优先(largest job first，LJF)、小任务优先(smallest job first，SJF)，根据任务执行时间采取的长任务优先(longest processing time first，LPT)、短任务优先(shortest processing time first，SPT)，根据任务等待时间采取的资源预约(reservation)、加权轮转调度(weighted round-robin)，以及为提高资源利用率而采取的各种回填算法(backfilling)、首次适应算法(firstfit)、贪婪算法(greedy)等。这些调度算法因逻辑简洁且具有较强通用性，因而被广泛应用。但这些算法在进行任务调度时，任务资源是用户提交任务时指定的，且在调度过程中是固定的，调度算法仅根据特定规则对任务执行次序进行调度，并未考虑资源可动态分配任务的调度需求。

为解决遥感卫星数据处理任务在调度过程中资源分配的问题，史园莉等[4]提出了“双级调度策略”实现资源的最优分配，其中“一级资源调度策略”根据“最优资源分配经验查找表”自动获得任务对应的最优资源数，“二级资源调度”采用传统的调度策略和算法对进行过资源重新分配的任务进行调度；汤灿恩等[5]提出了一种“基于先验知识动态分配资源的调度策略”，以任务单位资源量、单位数据量的运行时间和机群的实时系统负载作为依据，动态地决定任务分配的资源数；葛强等[6]为解决系统负载均衡及紧急任务调度的问题，提出了一种基于任务需求与服务能力相匹配的遥感产品生产任务调度算法。这些调度算法虽然具体实现的方式不同，但都是通过增加调度过程中任务和系统相关信息的方式，改善了传统方法在特殊应用场景下针对特殊需求时的调度效果。本文在进行研究时，也从系统和任务特性的角度展开，从而更好地对预处理系统中的复杂任务进行调度。

遥感卫星数据预处理系统与用户交互式数据处理系统不同。用户交互式处理系统中，用户通过客户端等途径提交随机处理任务，并希望更早得到结果数据；而遥感卫星数据预处理系统则一般通过卫星地面站获取卫星下传的原始码流数据，并由系统自动发起并完成各级产品生产、分发等工作。基于上述遥感卫星数据预处理业务，预处理系统在性能上主要有两方面要求：数据时效性要求及系统吞吐量。数据时效性要求是指在规定时间内完成所需产品生产，一般并不强调完成时间越短越好。表1为高分六号在数据时效性和系统吞吐量方面的具体要求。

表1 高分六号数据处理要求

综上所述，本文所要解决的问题为从预处理系统和任务的角度，建立相应的调度模型，从而满足系统中多卫星数据产品同时生产时的时效性要求，并提高预处理系统的吞吐量。实验结果表明，本文建立的调度模型通过采用更具针对性的资源分配策略，既满足了多卫星数据同时处理时的时效性要求，也提高了预处理系统的吞吐量。

2 调度模型研究

本调度模型所解决的两个关键问题及本文的主要工作如下：为复杂任务资源动态分配提供合理的依据；通过对任务执行次序进行调度确保所有任务满足时效性要求。在综合考虑预处理任务的各方面特征和预处理系统特性后，遥感卫星数据预处理复杂任务调度模型的设计结构如图1所示。

图1 遥感卫星数据预处理复杂任务调度模型结构

1)预处理任务性能模型。对预处理系统中的复杂任务进行研究分析，将复杂任务的性能差异通过模型参数差异进行体现，建立符合各任务特性的性能模型，从而对并行任务的执行时间进行预估，提供更为详细的任务信息作为调度算法的决策依据。

2)工作流任务预估模型。根据各卫星处理业务的工作流，对预处理任务及其子任务的数量和总执行时间进行预估，并根据数据时效性规定的时间，计算各阶段预处理任务的最长等待时间之和，从而将数据时效性要求转化为各阶段处理任务的时效性要求。

3)任务时效性及系统资源利用率驱动的调度算法。充分利用预处理任务性能模型和工作流任务预估模型提供的任务信息，动态调整任务的资源分配和执行次序，以满足时效性要求为前提减少资源碎片，提高系统吞吐量。

2.1 预处理任务性能模型

在具体阐述如何建立预处理任务性能模型前，需引入总并行开销[7](total overhead)的概念。求解同一个问题，开销函数To的表示如式(1)所示。

To=pTp-Ts

(1)

式中：Ts表示最快串行算法运行时间；并行运行情况下，p表示所用资源总数；Tp表示单个资源运行时间；所有资源所用总时间之和可以表示为pTp，这个时间的Ts部分是完成有用工作所花费的时间，剩余部分即是开销。

机群平均资源利用率(Uave)是一段时间内任务所用资源与机群总资源的比值，用于衡量机群资源的利用情况，定义如式(2)所示。

(2)

式中：Ntask表示任务总数；pi和Ti分别表示第i个任务所用资源数和执行时间；分母中Ttotal表示所有任务的总执行时间；Nnode表示机群总节点数；Nk表示第k个节点的资源数。

根据式(1)，机群平均资源利用率的分子可以表示为所有任务的总并行开销与所有任务的有用工作时间之和，则总执行时间的表示如式(3)所示。

(3)

式中：Toi表示第i个任务的总并行开销；Tsi表示第i个任务的最快串行算法运行时间。

对于预处理系统而言，在输入数据一定时，有用工作所花费的时间总和是一定的。由式(3)可知，机群平均资源利用率Uave越高，所有任务的总并行开销越小，总执行时间Ttotal也就越短，系统吞吐量越高。

因不同任务的总并行开销各不相同，建立性能模型对其进行定量描述，可在满足任务时效性要求为任务分配更多计算资源的同时，降低因并行带来的总并行开销之和，减少资源浪费，从而提高系统吞吐量。

性能模型的建模方法有很多种，但从原理上主要分为三类：程序源代码人工分析的解析建模、通过插桩等手段记录程序行为并还原的模拟建模、通过记录程序执行日志并进行学习的经验建模方法[8-9]。本文在进行预处理任务性能模型建模时，对于源代码不可获取的第三方软件使用经验建模法，对于源代码可获取的并行程序使用解析建模和经验建模相结合的方法。依据任务能否进行动态资源分配，将预处理任务分为两类：一类是刚性任务，这类任务无法进行动态资源分配，必须获取指定资源后才能执行，为方便研究，串行任务也认为是一种特殊的刚性任务；另一类为可塑任务，该类任务在执行前能根据任务可用的资源进行动态资源分配。

遥感卫星数据预处理流程主要包括帧同步、解扰、译码、通道分离、图像数据解压缩、辅助数据解析、相对辐射校正、系统几何校正等。处理流程繁杂，且各阶段的处理任务完全不同，但相同点是在预处理的整个流程的每一阶段所处理的数据都具有严格的格式规定，如图2所示。

图2 预处理各阶段格式

虽然不同的预处理系统具体实现预处理功能的形式存在不同，但各阶段处理任务的处理逻辑一般均为对“最小格式数据单元”处理的循环。如辅助数据解析阶段根据相机数据编排格式解析出卫星姿态、卫星位置等信息。图3为高分六号卫星的相机数据编排格式。高分六号的高分相机每写入32行图像数据完成一次辅助数据插入，因而在进行预处理时，则按照数据格式每32行为一周期，循环解析辅助数据。

图3 高分六号辅助数据格式

据此，可归纳出遥感卫星数据预处理程序的一般逻辑，如图4所示。首先，加载用于描述数据格式信息的配置文件，读取元数据文件中信息；然后，根据配置文件中的数据帧的帧头标识符及帧结构获取所有数据帧的起始结束位置，再采取循环的方式对每一帧数据进行解析；最后，进行元数据文件更新、数据输出、资源释放等。

图4 遥感卫星预处理程序一般逻辑伪代码

串行遥感卫星预处理程序的执行时间计算如式(4)所示。

Ts=Nframe·Tsingle+Tpre & fin

(4)

式中：Nframe表示处理数据帧个数；Tsingle表示处理一个数据帧所需时间；Tpre & fin表示环境准备和程序结束数据输出的时间。在对遥感卫星预处理串行程序进行时间预估时，需先实验测算或在代码中以“插桩”的方式获得Tpre & fin和Tsingle，再根据输入数据大小计算出输入数据的“数据帧”个数，即可实现对串行程序执行时间的预估。

遥感卫星预处理的并行程序普遍所采用的编程模型包括MPI和OpenMP以及二者相结合的MPI+OpenMP混合并行编程模型，采用这种方式能够更简单高效地利用机群的计算资源[10]。但串行程序在并行化的过程中总会不可避免地引入额外的时间开销，因此除串行程序性能模型所考虑的因素外，还需额外考虑并行化带来的额外时间开销。

对于遥感卫星预处理程序来说，粗粒度并行的任务利用MPI实现机群节点间并行，如多通道原始码流数据的解格式与通道数据分离；同一传感器的多个相机数据解压缩等，而细粒度的并行任务则通过OpenMP实现节点内并行，如同一通道原始码流数据内帧与帧之间的并行处理；波段配准时，图像块之间的并行等。这样的设计能够降低并行线程、进程间依赖关系，最大程度消除因进程、线程间通信带来额外开销，使并行带来的额外成本仅与串行分量和进程、线程的建立和销毁有关。

综上所述，对于并行的遥感卫星预处理程序，总执行时间Ttotal应由串行分量执行时间Tserial和并行分量执行时间Tparallel组成。

Ttotal=Tserial+Tparallel

(5)

式中：串行分量时间Tserial由“配置文件加载”“元数据文件的读写”“线程、进程建立和销毁”等固定的时间消耗Tconst，以及与数据量有关的“数据加载”“数据写入”等可变时间消耗r·Sdat组成，其中，r为比例系数；Sdat为输入数据大小。

Tserial=Tconst+r·Sdat

(6)

而并行分量的执行时间Tparallel又与程序所用节点数Nnode、每个节点所使用的资源数Nres有关。

(7)

式中：Sframe表示单个数据帧大小；Sdat/Sframe表示输入数据帧个数；t为单个数据帧处理的耗时，通过记录程序运行过程中的执行数据计算获得。

式(1)中p的表达如式(8)所示。

p=Nnode·Nres

(8)

当p等于1时，Ttotal与串行情况下有用工作时间Ts相等，如式(9)所示。

Ts=Tconst+r·Sdat+t(Sdat/Sframe)

(9)

当p大于1时，Ttotal与使用p个资源的并行执行时间Tp相等，则根据式(7)、式(9)总并行开销可表示为式(10)。

(10)

可见，通过建立预处理任务性能模型，可以将遥感卫星数据预处理系统中的复杂任务以统一的任务性能模型表示出来，将任务复杂性转化为模型参数的差异，并能根据输入数据大小和分配资源数进行时间预估，计算不同资源分配情况下的总并行开销。借助预处理任务性能模型，既可以根据任务的时效性要求对复杂任务分配相应资源，又能通过计算不同资源分配情况下，任务组合的总并行开销之和来减少资源浪费，提高系统吞吐量。

2.2 工作流任务预估模型

在基于工作流的遥感卫星数据预处理系统中，所有卫星数据的处理任务以工作流的方式被串联起来，当工作流执行到相应阶段时则会提交对应的预处理任务。

图5为高分一号、高分二号卫星的预处理工作流，对于工作流中每个阶段的预处理任务都可以依据性能模型获取任务不同资源分配情况下的预计执行时间，并能根据先验知识预估提交的任务数目。具体预估算法如下。

图5 预处理工作流示例

1)根据原始码流数据头文件获取载荷信息。

2)根据载荷信息及原始码流数据大小确定解压缩图像数据块数目。

3)根据压缩数据块数目估计条带数据行数。

4)根据分景规则计算系统几何校正产品总景数，至此可以估计出即该轨影像所需执行的所有任务种类和数目。

通过工作流任务预估模型，能够在接收到原始码流数据后，对后续流程中所有处理阶段提交的子任务进行分阶段预估，通过分析预估任务集合，使调度模型获取将被提交任务的信息，并根据产品的时效性要求和产品的剩余所需执行任务的性能模型计算出后续任务的最长等待时间，从而能够对更长时间段内的任务进行综合调度。

2.3 任务时效性及系统资源利用率驱动的复杂任务调度算法

本调度算法分两次对预处理任务进行调度：首次调度为接收到原始数据且未提交任务前，此时根据产品时效要求对同一工作流内不同阶段的预处理任务进行资源分配，以满足时效性要求；第二次调度根据任务最长等待时间调整执行次序，并根据系统实时资源利用率对任务所需资源进行动态分配。

根据预处理任务性能模型和工作流任务预估模型，预处理复杂任务的参与调度的任务属性如表2所示。

表2 预处理复杂任务属性信息

预处理工作流实际为一典型树状结构，系统几何校正产品生产时间可以表示为该产品每一处理阶段所用时间的总和，如式(11)所示。

(11)

式中：Ti表示第i阶段处理任务的执行时间，而当该任务为可塑任务时，Ti={Tq|Smin≤q≤Smax}。其中，q为分配资源数目；Tq表示当分配资源q时对应的执行时间；Smin和Smax分别为该任务所能利用的最小和最大资源数目。

为满足产品的时效性要求，需要通过增加资源分配的方式缩短任务的总执行时间。在无约束条件时，为获取最小的总执行时间，调度算法应尽可能为任务分配更多的计算资源从而更快地获取数据产品。但由式(10)可知，因串行分量的存在，在对任务分配更多资源时，任务的总并行开销增加，导致出现资源浪费，因此，在对多任务进行资源分配时，应根据各任务总并行开销大小进行资源分配。

首次资源分配是为了确保任务在无等待情况下满足时效性要求，且总并行开销最小，算法步骤如下。

步骤1：根据工作流任务预估模型计算预处理任务集合，并修改该工作流内部所有任务的时效要求时间。

步骤2：计算预处理任务集合中每个任务的可用资源数据及对应执行时间。

步骤3：所有任务取最小资源分配方案计算总时长。

步骤4：计算单个系统几何校正产品各阶段任务执行总时间。当总时长小于时效要求时间时，以原始数据名为索引，记录本流程所有任务资源分配方案，并根据工作流由下至上计算剩余任务最长执行时间，第i阶段最长执行时间如式(12)所示。

Rcur=Tcur+Rnext

(12)

式中：Rcur表示本阶段剩余任务的执行时间，由当前任务执行时间Tcur和下一阶段剩余任务执行时间Rnext组成。首次资源分配结束。否则，执行步骤5。

步骤5：若流程中第i阶段任务Taski能增加资源分配，则计算由增加资源而产生的额外总并行开销与降低时间的比值。

(13)

式中：j为当前已分配资源数；Δj为预计增加资源数；Tj和Tj+Δj分别表示在原资源数和增加Δj资源后的执行时间。

该比值表示为在增加资源时，降低单位任务执行时间而产生的额外成本，当Qi最小时，将资源分给该任务，然后继续执行步骤4。

根据该算法，进行资源分配时，在满足任务时效性要求的同时，对于并行程度高，串行分量小的预处理任务会被分配更多计算资源，减少了因盲目分配资源出现额外总并行开销，防止了资源浪费。

第二次资源分配的是为了提高机群平均资源利用率和确保因排队而未及时执行的任务能够满足时效性要求。根据系统实时负载情况进行动态资源分配：系统低负载时，为每个任务分配更多资源提高资源利用率；系统高负载时，通过降低时效要求较长的任务的资源分配数目，从而让因等待而未能按时提交的任务能够及时完成。系统实时负载表示为机群实时资源利用率Ur，为使用资源数Rused和总资源数Rtotal的比值。

(14)

算法流程如图6所示，每当系统资源状态更新时，进行资源动态分配和任务执行，具体算法如下。

图6 第二次资源分配算法流程图

①更新所有任务的最短可等待时间，并由短到长排序，并按序对任务进行调度。

②当存在任务最短可等待时间小于0时，按第一次资源分配算法重新对该任务所处工作流内各阶段子任务资源分配，并维持本次任务排序。

③选取排序后等待队列中前x个任务，直到前第x+1个任务所需资源总和大于当前剩余可用资源。当x>0时，根据式(13)计算最小总并行开销与加速时间的比值，并将资源分配给该任务，直至剩余可用资源为0。

当x=0时，即可用资源不满足任务需求。计算资源释放时间，进行资源预约，计算因预约产生的资源碎片，从排序后的等待队列中，依次选出满足资源需求且执行时间小于资源预约时间的任务进行回填。

3 仿真实验与结果分析

3.1 复杂任务调度系统

调度系统主要包含基础层、信息层、算法层、应用层四层，如图7所示。

图7 遥感卫星数据预处理复杂任务调度系统架构图

基础层为调度系统的基础环境，与遥感卫星数据预处理系统环境一致，预处理系统和调度系统基于高性能对称多处理(symmetric multi processing，SMP)机群实现，调度系统通过对可移植的批处理系统(portable batch system，PBS)有关命令的封装实现对机群资源的调度。PBS是目前应用广泛的机群资源管理系统，已经成为机群系统优先采用的任务管理系统[11]，Torque PBS为其开源的免费版本之一。信息层用于提供调度系统在进行调度决策时所需要的任务信息。算法层为前文所述算法的具体实现。应用层主要功能为接收预处理系统提交的预处理任务，并根据任务时效性要求和机群资源利用状态对任务进行调度，同时提供任务监控功能。

3.2 实验环境

通用遥感卫星数据处理系统设备系统包含68个计算刀片服务器，计算节点配置如表3所示。

表3 机群计算节点服务器配置

计算系统整体双精度峰值性能达到158.412 8×1012次/s。配置两台数据库服务器、两台管理节点服务器、两台数据分发节点服务器，以及一套曙光ParaStor300分布式并行存储系统，可用容量440 TB，同时并发40 GB/s读带宽+40 GB/s写带宽(每个节点700 MB/s读+700 MB/s写带宽)，整套设备采用万兆网络互联。实验中，在真实机群环境中测算不同卫星的各预处理任务性能模型，并使用20个计算节点进行仿真实验。

3.3 实验结果及分析

实验中将本文所采用的“二次资源分配算法”分别与传统调度算法中的“首次适应算法”和“优先级调度算法”在系统吞吐量和任务时效性性能上进行对比。

“首次适应算法”按照任务提交顺序选取等待队列中满足资源要求的任务进行执行，该算法不会因资源需求较大任务而出现任务阻塞现象，因而能够提高系统吞吐量。

“优先级调度算法”为系统根据任务优先级依次选择任务进行执行。实验中，优先级确定的依据为任务的时效性，任务时效性要求越短任务优先级越高。

传统调度算法在进行任务资源分配时，采用静态的资源分配方式，不同卫星不同阶段任务所分配的资源数根据经验值确定，该分配方案能满足最短时效性要求。通过在预处理任务调度系统算法层中增加算法模块的方式，实现对上述传统调度算法的集成。

数据方面，使用高分一、二、六号卫星数据各三轨进行实验，总原始码流数据量为420.50 GB。为了模拟数据时效性要求不同时调度的情况，每颗卫星各两轨数据时效性要求为2 h，模拟常规生产，总数据量304.85 GB；每颗卫星各一轨数据时效性要求为45分钟，模拟紧急生产，总数据量115.64 GB。采取同时提交多轨原始数据的方式模拟预处理系统高负载。最终系统几何校正产品共计2 638景，其中，常规生产1 806景，紧急产品832景。

图8为三种调度算法系统几何校正产品数目随时间的变化情况，折线不再随时间延伸表示已完成所有产品生产。完成所有产品生产前，各时间点及其对应的产品数目差异反映了不同算法的调度行为差异。与传统算法相比，本调度算法在100分钟左右率先完成了所有产品的生产任务，吞吐量更高。同时，因本算法在进行调度时，会根据时效性要求进行资源分配，使时效性相同的产品趋于同时完成。故在实验中，紧急生产和常规生产的产品分别在30分钟及90分钟附近集中完成，这使得在集中完成前的一段时间内产品数目低于其他算法。虽然在这些时间段内产品数目较少，但当产品集中完成后，本算法实际耗时更短，系统吞吐量更高。

图8 各算法系统几何校正产品数目对比

如图9所示，本算法在30分钟左右完成所有紧急产品生产，在100分钟左右完成常规产品生产，相比传统算法能够在更短时间内满足不同产品的时效性要求。“首次适应算法”因在进行任务调度时，仅能获取单个任务的提交顺序、所需资源数，无法对任务类型进行区分，任务调度具有相对随机性，无法对紧急产品生产任务进行优先调度，最终满足时效要求产品较少。“优先级调度算法”在进行调度时，因紧急任务具有较高的优先级而优先执行，能够较好地满足各类任务的时效性要求。

图9 各算法满足时效要求产品数目对比

表4为各算法总执行时间、时效达成率及吞吐量对比。时效达成率为满足时效要求产品景数与产品总景数的比值；吞吐量为原始码流数据量与总执行时间的比值。可见本算法在时效达成率和吞吐量上都具有一定优势。

表4 各算法时效达成率及吞吐量对比

从实验结果可知，“优先级调度算法”能够较好地从任务时效性角度对任务进行调度，但当系统负载较高时，存在高优先级任务无法获取所需资源，而低优先级任务无法及时利用空闲资源的现象，导致了资源浪费，系统吞吐量较低。“首次适应算法”能够通过按序扫描等待队列，防止了资源需求较大任务造成的“阻塞”现象，相对于优先级调度法来说很大程度提高了吞吐量，但因调度过程中，仅考虑吞吐量，而未将任务时效性作为调度依据，故任务时效性不同时，难以主动满足不同任务的时效性要求。本算法在进行调度时，为了使同时提交的所有任务都能满足时效性要求，会优先对资源需求量大、可等待时间较短的任务进行调度。相应地，会降低剩余子任务较少、可等待时间较长的任务的调度优先级和资源分配数目，从而满足不同任务的时效性要求，且在进行资源分配时，通过对比不同任务性能，减少了因额外总并行开销导致的资源浪费，提高了系统吞吐量。

4 结束语

本文针对遥感卫星数据预处理系统中复杂任务在进行资源分配和调度过程中存在盲目性、难以满足任务时效性要求的问题，在预处理任务性能模型和工作流任务预估模型的基础上，确定了由任务时效性及系统资源利用率驱动的复杂任务调度算法。该算法通过两次资源分配，既满足了任务时效性要求，也更合理地利用了计算资源，减少了资源浪费，提高了系统吞吐量。

但本算法还存在一定的不足，主要表现在本调度算法的基础是预处理任务性能模型，现阶段确定性能模型主要采用人工测算的方式，进行预估时的准确度与测试样本数相关，当预处理程序版本更新或集成新的卫星处理功能时，测算各任务性能模型的工作量较大。下一步研究计划为通过记录任务的执行日志，实现数据驱动的预处理任务性能模型自动建模。一方面提高任务性能模型在预估时的准确性，另一方面提高调度系统的可扩展性，从而更好地对遥感卫星数据预处理系统中的复杂任务进行调度。