遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)復(fù)雜任務(wù)調(diào)度模型研究與實(shí)現(xiàn)

陳亮，李景山

(1.中國科學(xué)院空天信息創(chuàng)新研究院，北京 100094；2.中國科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院，北京 100094)

0 引言

遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)是衛(wèi)星地面系統(tǒng)的重要組成部分之一，是獲取衛(wèi)星產(chǎn)品數(shù)據(jù)的重要環(huán)節(jié)，國內(nèi)外很多學(xué)者和組織都對(duì)遙感衛(wèi)星數(shù)據(jù)處理系統(tǒng)及預(yù)處理算法進(jìn)行了深入的研究。大型衛(wèi)星圖像數(shù)據(jù)處理中心越來越多地開發(fā)模塊化的多任務(wù)開放式架構(gòu)[1]?；诠ぷ髁鞯念A(yù)處理系統(tǒng)具有較為廣泛的應(yīng)用[2-3]，根據(jù)不同衛(wèi)星的預(yù)處理要求，將衛(wèi)星的預(yù)處理任務(wù)以工作流形式串聯(lián)起來，解決了遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)多衛(wèi)星處理功能擴(kuò)展問題。

隨著預(yù)處理系統(tǒng)中新的衛(wèi)星處理功能不斷集成，預(yù)處理任務(wù)的復(fù)雜程度也隨之提高，主要體現(xiàn)在以下三個(gè)方面。一是任務(wù)類型復(fù)雜。不同衛(wèi)星、不同處理階段都對(duì)應(yīng)不同的任務(wù)類型。二是任務(wù)組合復(fù)雜。同一時(shí)刻需對(duì)多種任務(wù)類型進(jìn)行調(diào)度。三是任務(wù)需求復(fù)雜。根據(jù)處理要求，各衛(wèi)星處理任務(wù)在常規(guī)和應(yīng)急情況下所處理的數(shù)據(jù)時(shí)效性和系統(tǒng)吞吐量要求存在差異。復(fù)雜的預(yù)處理任務(wù)對(duì)調(diào)度算法提出了更高的要求。

本文所要研究的內(nèi)容是通過建立調(diào)度模型對(duì)機(jī)群環(huán)境下的遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)中的復(fù)雜任務(wù)進(jìn)行調(diào)度，在滿足預(yù)處理數(shù)據(jù)時(shí)效性要求的同時(shí)，提高系統(tǒng)吞吐量。相關(guān)概念定義如下。

1)系統(tǒng)吞吐量。系統(tǒng)在單位時(shí)間內(nèi)的工作量。具體在遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)中，吞吐量表示為單位時(shí)間內(nèi)處理原始碼流數(shù)據(jù)的總數(shù)據(jù)量。

2)數(shù)據(jù)時(shí)效性。是指從接收到原始數(shù)據(jù)開始，到完成目標(biāo)產(chǎn)品生產(chǎn)，并向用戶分發(fā)的整個(gè)過程的時(shí)間要求。

1 調(diào)度算法分析及問題描述

傳統(tǒng)調(diào)度算法主要從時(shí)間和資源兩個(gè)角度對(duì)任務(wù)進(jìn)行調(diào)度，如最基本的調(diào)度算法包括先來先服務(wù)(first come first serve，F(xiàn)CFS)，根據(jù)任務(wù)所需資源數(shù)目多少而采取的大任務(wù)優(yōu)先(largest job first，LJF)、小任務(wù)優(yōu)先(smallest job first，SJF)，根據(jù)任務(wù)執(zhí)行時(shí)間采取的長(zhǎng)任務(wù)優(yōu)先(longest processing time first，LPT)、短任務(wù)優(yōu)先(shortest processing time first，SPT)，根據(jù)任務(wù)等待時(shí)間采取的資源預(yù)約(reservation)、加權(quán)輪轉(zhuǎn)調(diào)度(weighted round-robin)，以及為提高資源利用率而采取的各種回填算法(backfilling)、首次適應(yīng)算法(firstfit)、貪婪算法(greedy)等。這些調(diào)度算法因邏輯簡(jiǎn)潔且具有較強(qiáng)通用性，因而被廣泛應(yīng)用。但這些算法在進(jìn)行任務(wù)調(diào)度時(shí)，任務(wù)資源是用戶提交任務(wù)時(shí)指定的，且在調(diào)度過程中是固定的，調(diào)度算法僅根據(jù)特定規(guī)則對(duì)任務(wù)執(zhí)行次序進(jìn)行調(diào)度，并未考慮資源可動(dòng)態(tài)分配任務(wù)的調(diào)度需求。

為解決遙感衛(wèi)星數(shù)據(jù)處理任務(wù)在調(diào)度過程中資源分配的問題，史園莉等[4]提出了“雙級(jí)調(diào)度策略”實(shí)現(xiàn)資源的最優(yōu)分配，其中“一級(jí)資源調(diào)度策略”根據(jù)“最優(yōu)資源分配經(jīng)驗(yàn)查找表”自動(dòng)獲得任務(wù)對(duì)應(yīng)的最優(yōu)資源數(shù)，“二級(jí)資源調(diào)度”采用傳統(tǒng)的調(diào)度策略和算法對(duì)進(jìn)行過資源重新分配的任務(wù)進(jìn)行調(diào)度；湯燦恩等[5]提出了一種“基于先驗(yàn)知識(shí)動(dòng)態(tài)分配資源的調(diào)度策略”，以任務(wù)單位資源量、單位數(shù)據(jù)量的運(yùn)行時(shí)間和機(jī)群的實(shí)時(shí)系統(tǒng)負(fù)載作為依據(jù)，動(dòng)態(tài)地決定任務(wù)分配的資源數(shù)；葛強(qiáng)等[6]為解決系統(tǒng)負(fù)載均衡及緊急任務(wù)調(diào)度的問題，提出了一種基于任務(wù)需求與服務(wù)能力相匹配的遙感產(chǎn)品生產(chǎn)任務(wù)調(diào)度算法。這些調(diào)度算法雖然具體實(shí)現(xiàn)的方式不同，但都是通過增加調(diào)度過程中任務(wù)和系統(tǒng)相關(guān)信息的方式，改善了傳統(tǒng)方法在特殊應(yīng)用場(chǎng)景下針對(duì)特殊需求時(shí)的調(diào)度效果。本文在進(jìn)行研究時(shí)，也從系統(tǒng)和任務(wù)特性的角度展開，從而更好地對(duì)預(yù)處理系統(tǒng)中的復(fù)雜任務(wù)進(jìn)行調(diào)度。

遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)與用戶交互式數(shù)據(jù)處理系統(tǒng)不同。用戶交互式處理系統(tǒng)中，用戶通過客戶端等途徑提交隨機(jī)處理任務(wù)，并希望更早得到結(jié)果數(shù)據(jù)；而遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)則一般通過衛(wèi)星地面站獲取衛(wèi)星下傳的原始碼流數(shù)據(jù)，并由系統(tǒng)自動(dòng)發(fā)起并完成各級(jí)產(chǎn)品生產(chǎn)、分發(fā)等工作?；谏鲜鲞b感衛(wèi)星數(shù)據(jù)預(yù)處理業(yè)務(wù)，預(yù)處理系統(tǒng)在性能上主要有兩方面要求：數(shù)據(jù)時(shí)效性要求及系統(tǒng)吞吐量。數(shù)據(jù)時(shí)效性要求是指在規(guī)定時(shí)間內(nèi)完成所需產(chǎn)品生產(chǎn)，一般并不強(qiáng)調(diào)完成時(shí)間越短越好。表1為高分六號(hào)在數(shù)據(jù)時(shí)效性和系統(tǒng)吞吐量方面的具體要求。

表1 高分六號(hào)數(shù)據(jù)處理要求

綜上所述，本文所要解決的問題為從預(yù)處理系統(tǒng)和任務(wù)的角度，建立相應(yīng)的調(diào)度模型，從而滿足系統(tǒng)中多衛(wèi)星數(shù)據(jù)產(chǎn)品同時(shí)生產(chǎn)時(shí)的時(shí)效性要求，并提高預(yù)處理系統(tǒng)的吞吐量。實(shí)驗(yàn)結(jié)果表明，本文建立的調(diào)度模型通過采用更具針對(duì)性的資源分配策略，既滿足了多衛(wèi)星數(shù)據(jù)同時(shí)處理時(shí)的時(shí)效性要求，也提高了預(yù)處理系統(tǒng)的吞吐量。

2 調(diào)度模型研究

本調(diào)度模型所解決的兩個(gè)關(guān)鍵問題及本文的主要工作如下：為復(fù)雜任務(wù)資源動(dòng)態(tài)分配提供合理的依據(jù)；通過對(duì)任務(wù)執(zhí)行次序進(jìn)行調(diào)度確保所有任務(wù)滿足時(shí)效性要求。在綜合考慮預(yù)處理任務(wù)的各方面特征和預(yù)處理系統(tǒng)特性后，遙感衛(wèi)星數(shù)據(jù)預(yù)處理復(fù)雜任務(wù)調(diào)度模型的設(shè)計(jì)結(jié)構(gòu)如圖1所示。

圖1 遙感衛(wèi)星數(shù)據(jù)預(yù)處理復(fù)雜任務(wù)調(diào)度模型結(jié)構(gòu)

1)預(yù)處理任務(wù)性能模型。對(duì)預(yù)處理系統(tǒng)中的復(fù)雜任務(wù)進(jìn)行研究分析，將復(fù)雜任務(wù)的性能差異通過模型參數(shù)差異進(jìn)行體現(xiàn)，建立符合各任務(wù)特性的性能模型，從而對(duì)并行任務(wù)的執(zhí)行時(shí)間進(jìn)行預(yù)估，提供更為詳細(xì)的任務(wù)信息作為調(diào)度算法的決策依據(jù)。

2)工作流任務(wù)預(yù)估模型。根據(jù)各衛(wèi)星處理業(yè)務(wù)的工作流，對(duì)預(yù)處理任務(wù)及其子任務(wù)的數(shù)量和總執(zhí)行時(shí)間進(jìn)行預(yù)估，并根據(jù)數(shù)據(jù)時(shí)效性規(guī)定的時(shí)間，計(jì)算各階段預(yù)處理任務(wù)的最長(zhǎng)等待時(shí)間之和，從而將數(shù)據(jù)時(shí)效性要求轉(zhuǎn)化為各階段處理任務(wù)的時(shí)效性要求。

3)任務(wù)時(shí)效性及系統(tǒng)資源利用率驅(qū)動(dòng)的調(diào)度算法。充分利用預(yù)處理任務(wù)性能模型和工作流任務(wù)預(yù)估模型提供的任務(wù)信息，動(dòng)態(tài)調(diào)整任務(wù)的資源分配和執(zhí)行次序，以滿足時(shí)效性要求為前提減少資源碎片，提高系統(tǒng)吞吐量。

2.1 預(yù)處理任務(wù)性能模型

在具體闡述如何建立預(yù)處理任務(wù)性能模型前，需引入總并行開銷[7](total overhead)的概念。求解同一個(gè)問題，開銷函數(shù)To的表示如式(1)所示。

To=pTp-Ts

(1)

式中：Ts表示最快串行算法運(yùn)行時(shí)間；并行運(yùn)行情況下，p表示所用資源總數(shù)；Tp表示單個(gè)資源運(yùn)行時(shí)間；所有資源所用總時(shí)間之和可以表示為pTp，這個(gè)時(shí)間的Ts部分是完成有用工作所花費(fèi)的時(shí)間，剩余部分即是開銷。

機(jī)群平均資源利用率(Uave)是一段時(shí)間內(nèi)任務(wù)所用資源與機(jī)群總資源的比值，用于衡量機(jī)群資源的利用情況，定義如式(2)所示。

(2)

式中：Ntask表示任務(wù)總數(shù)；pi和Ti分別表示第i個(gè)任務(wù)所用資源數(shù)和執(zhí)行時(shí)間；分母中Ttotal表示所有任務(wù)的總執(zhí)行時(shí)間；Nnode表示機(jī)群總節(jié)點(diǎn)數(shù)；Nk表示第k個(gè)節(jié)點(diǎn)的資源數(shù)。

根據(jù)式(1)，機(jī)群平均資源利用率的分子可以表示為所有任務(wù)的總并行開銷與所有任務(wù)的有用工作時(shí)間之和，則總執(zhí)行時(shí)間的表示如式(3)所示。

(3)

式中：Toi表示第i個(gè)任務(wù)的總并行開銷；Tsi表示第i個(gè)任務(wù)的最快串行算法運(yùn)行時(shí)間。

對(duì)于預(yù)處理系統(tǒng)而言，在輸入數(shù)據(jù)一定時(shí)，有用工作所花費(fèi)的時(shí)間總和是一定的。由式(3)可知，機(jī)群平均資源利用率Uave越高，所有任務(wù)的總并行開銷越小，總執(zhí)行時(shí)間Ttotal也就越短，系統(tǒng)吞吐量越高。

因不同任務(wù)的總并行開銷各不相同，建立性能模型對(duì)其進(jìn)行定量描述，可在滿足任務(wù)時(shí)效性要求為任務(wù)分配更多計(jì)算資源的同時(shí)，降低因并行帶來的總并行開銷之和，減少資源浪費(fèi)，從而提高系統(tǒng)吞吐量。

性能模型的建模方法有很多種，但從原理上主要分為三類：程序源代碼人工分析的解析建模、通過插樁等手段記錄程序行為并還原的模擬建模、通過記錄程序執(zhí)行日志并進(jìn)行學(xué)習(xí)的經(jīng)驗(yàn)建模方法[8-9]。本文在進(jìn)行預(yù)處理任務(wù)性能模型建模時(shí)，對(duì)于源代碼不可獲取的第三方軟件使用經(jīng)驗(yàn)建模法，對(duì)于源代碼可獲取的并行程序使用解析建模和經(jīng)驗(yàn)建模相結(jié)合的方法。依據(jù)任務(wù)能否進(jìn)行動(dòng)態(tài)資源分配，將預(yù)處理任務(wù)分為兩類：一類是剛性任務(wù)，這類任務(wù)無法進(jìn)行動(dòng)態(tài)資源分配，必須獲取指定資源后才能執(zhí)行，為方便研究，串行任務(wù)也認(rèn)為是一種特殊的剛性任務(wù)；另一類為可塑任務(wù)，該類任務(wù)在執(zhí)行前能根據(jù)任務(wù)可用的資源進(jìn)行動(dòng)態(tài)資源分配。

遙感衛(wèi)星數(shù)據(jù)預(yù)處理流程主要包括幀同步、解擾、譯碼、通道分離、圖像數(shù)據(jù)解壓縮、輔助數(shù)據(jù)解析、相對(duì)輻射校正、系統(tǒng)幾何校正等。處理流程繁雜，且各階段的處理任務(wù)完全不同，但相同點(diǎn)是在預(yù)處理的整個(gè)流程的每一階段所處理的數(shù)據(jù)都具有嚴(yán)格的格式規(guī)定，如圖2所示。

圖2 預(yù)處理各階段格式

雖然不同的預(yù)處理系統(tǒng)具體實(shí)現(xiàn)預(yù)處理功能的形式存在不同，但各階段處理任務(wù)的處理邏輯一般均為對(duì)“最小格式數(shù)據(jù)單元”處理的循環(huán)。如輔助數(shù)據(jù)解析階段根據(jù)相機(jī)數(shù)據(jù)編排格式解析出衛(wèi)星姿態(tài)、衛(wèi)星位置等信息。圖3為高分六號(hào)衛(wèi)星的相機(jī)數(shù)據(jù)編排格式。高分六號(hào)的高分相機(jī)每寫入32行圖像數(shù)據(jù)完成一次輔助數(shù)據(jù)插入，因而在進(jìn)行預(yù)處理時(shí)，則按照數(shù)據(jù)格式每32行為一周期，循環(huán)解析輔助數(shù)據(jù)。

圖3 高分六號(hào)輔助數(shù)據(jù)格式

據(jù)此，可歸納出遙感衛(wèi)星數(shù)據(jù)預(yù)處理程序的一般邏輯，如圖4所示。首先，加載用于描述數(shù)據(jù)格式信息的配置文件，讀取元數(shù)據(jù)文件中信息；然后，根據(jù)配置文件中的數(shù)據(jù)幀的幀頭標(biāo)識(shí)符及幀結(jié)構(gòu)獲取所有數(shù)據(jù)幀的起始結(jié)束位置，再采取循環(huán)的方式對(duì)每一幀數(shù)據(jù)進(jìn)行解析；最后，進(jìn)行元數(shù)據(jù)文件更新、數(shù)據(jù)輸出、資源釋放等。

圖4 遙感衛(wèi)星預(yù)處理程序一般邏輯偽代碼

串行遙感衛(wèi)星預(yù)處理程序的執(zhí)行時(shí)間計(jì)算如式(4)所示。

Ts=Nframe·Tsingle+Tpre & fin

(4)

式中：Nframe表示處理數(shù)據(jù)幀個(gè)數(shù)；Tsingle表示處理一個(gè)數(shù)據(jù)幀所需時(shí)間；Tpre & fin表示環(huán)境準(zhǔn)備和程序結(jié)束數(shù)據(jù)輸出的時(shí)間。在對(duì)遙感衛(wèi)星預(yù)處理串行程序進(jìn)行時(shí)間預(yù)估時(shí)，需先實(shí)驗(yàn)測(cè)算或在代碼中以“插樁”的方式獲得Tpre & fin和Tsingle，再根據(jù)輸入數(shù)據(jù)大小計(jì)算出輸入數(shù)據(jù)的“數(shù)據(jù)幀”個(gè)數(shù)，即可實(shí)現(xiàn)對(duì)串行程序執(zhí)行時(shí)間的預(yù)估。

遙感衛(wèi)星預(yù)處理的并行程序普遍所采用的編程模型包括MPI和OpenMP以及二者相結(jié)合的MPI+OpenMP混合并行編程模型，采用這種方式能夠更簡(jiǎn)單高效地利用機(jī)群的計(jì)算資源[10]。但串行程序在并行化的過程中總會(huì)不可避免地引入額外的時(shí)間開銷，因此除串行程序性能模型所考慮的因素外，還需額外考慮并行化帶來的額外時(shí)間開銷。

對(duì)于遙感衛(wèi)星預(yù)處理程序來說，粗粒度并行的任務(wù)利用MPI實(shí)現(xiàn)機(jī)群節(jié)點(diǎn)間并行，如多通道原始碼流數(shù)據(jù)的解格式與通道數(shù)據(jù)分離；同一傳感器的多個(gè)相機(jī)數(shù)據(jù)解壓縮等，而細(xì)粒度的并行任務(wù)則通過OpenMP實(shí)現(xiàn)節(jié)點(diǎn)內(nèi)并行，如同一通道原始碼流數(shù)據(jù)內(nèi)幀與幀之間的并行處理；波段配準(zhǔn)時(shí)，圖像塊之間的并行等。這樣的設(shè)計(jì)能夠降低并行線程、進(jìn)程間依賴關(guān)系，最大程度消除因進(jìn)程、線程間通信帶來額外開銷，使并行帶來的額外成本僅與串行分量和進(jìn)程、線程的建立和銷毀有關(guān)。

綜上所述，對(duì)于并行的遙感衛(wèi)星預(yù)處理程序，總執(zhí)行時(shí)間Ttotal應(yīng)由串行分量執(zhí)行時(shí)間Tserial和并行分量執(zhí)行時(shí)間Tparallel組成。

Ttotal=Tserial+Tparallel

(5)

式中：串行分量時(shí)間Tserial由“配置文件加載”“元數(shù)據(jù)文件的讀寫”“線程、進(jìn)程建立和銷毀”等固定的時(shí)間消耗Tconst，以及與數(shù)據(jù)量有關(guān)的“數(shù)據(jù)加載”“數(shù)據(jù)寫入”等可變時(shí)間消耗r·Sdat組成，其中，r為比例系數(shù)；Sdat為輸入數(shù)據(jù)大小。

Tserial=Tconst+r·Sdat

(6)

而并行分量的執(zhí)行時(shí)間Tparallel又與程序所用節(jié)點(diǎn)數(shù)Nnode、每個(gè)節(jié)點(diǎn)所使用的資源數(shù)Nres有關(guān)。

(7)

式中：Sframe表示單個(gè)數(shù)據(jù)幀大?。籗dat/Sframe表示輸入數(shù)據(jù)幀個(gè)數(shù)；t為單個(gè)數(shù)據(jù)幀處理的耗時(shí)，通過記錄程序運(yùn)行過程中的執(zhí)行數(shù)據(jù)計(jì)算獲得。

式(1)中p的表達(dá)如式(8)所示。

p=Nnode·Nres

(8)

當(dāng)p等于1時(shí)，Ttotal與串行情況下有用工作時(shí)間Ts相等，如式(9)所示。

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

(9)

當(dāng)p大于1時(shí)，Ttotal與使用p個(gè)資源的并行執(zhí)行時(shí)間Tp相等，則根據(jù)式(7)、式(9)總并行開銷可表示為式(10)。

(10)

可見，通過建立預(yù)處理任務(wù)性能模型，可以將遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)中的復(fù)雜任務(wù)以統(tǒng)一的任務(wù)性能模型表示出來，將任務(wù)復(fù)雜性轉(zhuǎn)化為模型參數(shù)的差異，并能根據(jù)輸入數(shù)據(jù)大小和分配資源數(shù)進(jìn)行時(shí)間預(yù)估，計(jì)算不同資源分配情況下的總并行開銷。借助預(yù)處理任務(wù)性能模型，既可以根據(jù)任務(wù)的時(shí)效性要求對(duì)復(fù)雜任務(wù)分配相應(yīng)資源，又能通過計(jì)算不同資源分配情況下，任務(wù)組合的總并行開銷之和來減少資源浪費(fèi)，提高系統(tǒng)吞吐量。

2.2 工作流任務(wù)預(yù)估模型

在基于工作流的遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)中，所有衛(wèi)星數(shù)據(jù)的處理任務(wù)以工作流的方式被串聯(lián)起來，當(dāng)工作流執(zhí)行到相應(yīng)階段時(shí)則會(huì)提交對(duì)應(yīng)的預(yù)處理任務(wù)。

圖5為高分一號(hào)、高分二號(hào)衛(wèi)星的預(yù)處理工作流，對(duì)于工作流中每個(gè)階段的預(yù)處理任務(wù)都可以依據(jù)性能模型獲取任務(wù)不同資源分配情況下的預(yù)計(jì)執(zhí)行時(shí)間，并能根據(jù)先驗(yàn)知識(shí)預(yù)估提交的任務(wù)數(shù)目。具體預(yù)估算法如下。

圖5 預(yù)處理工作流示例

1)根據(jù)原始碼流數(shù)據(jù)頭文件獲取載荷信息。

2)根據(jù)載荷信息及原始碼流數(shù)據(jù)大小確定解壓縮圖像數(shù)據(jù)塊數(shù)目。

3)根據(jù)壓縮數(shù)據(jù)塊數(shù)目估計(jì)條帶數(shù)據(jù)行數(shù)。

4)根據(jù)分景規(guī)則計(jì)算系統(tǒng)幾何校正產(chǎn)品總景數(shù)，至此可以估計(jì)出即該軌影像所需執(zhí)行的所有任務(wù)種類和數(shù)目。

通過工作流任務(wù)預(yù)估模型，能夠在接收到原始碼流數(shù)據(jù)后，對(duì)后續(xù)流程中所有處理階段提交的子任務(wù)進(jìn)行分階段預(yù)估，通過分析預(yù)估任務(wù)集合，使調(diào)度模型獲取將被提交任務(wù)的信息，并根據(jù)產(chǎn)品的時(shí)效性要求和產(chǎn)品的剩余所需執(zhí)行任務(wù)的性能模型計(jì)算出后續(xù)任務(wù)的最長(zhǎng)等待時(shí)間，從而能夠?qū)ΩL(zhǎng)時(shí)間段內(nèi)的任務(wù)進(jìn)行綜合調(diào)度。

2.3 任務(wù)時(shí)效性及系統(tǒng)資源利用率驅(qū)動(dòng)的復(fù)雜任務(wù)調(diào)度算法

本調(diào)度算法分兩次對(duì)預(yù)處理任務(wù)進(jìn)行調(diào)度：首次調(diào)度為接收到原始數(shù)據(jù)且未提交任務(wù)前，此時(shí)根據(jù)產(chǎn)品時(shí)效要求對(duì)同一工作流內(nèi)不同階段的預(yù)處理任務(wù)進(jìn)行資源分配，以滿足時(shí)效性要求；第二次調(diào)度根據(jù)任務(wù)最長(zhǎng)等待時(shí)間調(diào)整執(zhí)行次序，并根據(jù)系統(tǒng)實(shí)時(shí)資源利用率對(duì)任務(wù)所需資源進(jìn)行動(dòng)態(tài)分配。

根據(jù)預(yù)處理任務(wù)性能模型和工作流任務(wù)預(yù)估模型，預(yù)處理復(fù)雜任務(wù)的參與調(diào)度的任務(wù)屬性如表2所示。

表2 預(yù)處理復(fù)雜任務(wù)屬性信息

預(yù)處理工作流實(shí)際為一典型樹狀結(jié)構(gòu)，系統(tǒng)幾何校正產(chǎn)品生產(chǎn)時(shí)間可以表示為該產(chǎn)品每一處理階段所用時(shí)間的總和，如式(11)所示。

(11)

式中：Ti表示第i階段處理任務(wù)的執(zhí)行時(shí)間，而當(dāng)該任務(wù)為可塑任務(wù)時(shí)，Ti={Tq|Smin≤q≤Smax}。其中，q為分配資源數(shù)目；Tq表示當(dāng)分配資源q時(shí)對(duì)應(yīng)的執(zhí)行時(shí)間；Smin和Smax分別為該任務(wù)所能利用的最小和最大資源數(shù)目。

為滿足產(chǎn)品的時(shí)效性要求，需要通過增加資源分配的方式縮短任務(wù)的總執(zhí)行時(shí)間。在無約束條件時(shí)，為獲取最小的總執(zhí)行時(shí)間，調(diào)度算法應(yīng)盡可能為任務(wù)分配更多的計(jì)算資源從而更快地獲取數(shù)據(jù)產(chǎn)品。但由式(10)可知，因串行分量的存在，在對(duì)任務(wù)分配更多資源時(shí)，任務(wù)的總并行開銷增加，導(dǎo)致出現(xiàn)資源浪費(fèi)，因此，在對(duì)多任務(wù)進(jìn)行資源分配時(shí)，應(yīng)根據(jù)各任務(wù)總并行開銷大小進(jìn)行資源分配。

首次資源分配是為了確保任務(wù)在無等待情況下滿足時(shí)效性要求，且總并行開銷最小，算法步驟如下。

步驟1：根據(jù)工作流任務(wù)預(yù)估模型計(jì)算預(yù)處理任務(wù)集合，并修改該工作流內(nèi)部所有任務(wù)的時(shí)效要求時(shí)間。

步驟2：計(jì)算預(yù)處理任務(wù)集合中每個(gè)任務(wù)的可用資源數(shù)據(jù)及對(duì)應(yīng)執(zhí)行時(shí)間。

步驟3：所有任務(wù)取最小資源分配方案計(jì)算總時(shí)長(zhǎng)。

步驟4：計(jì)算單個(gè)系統(tǒng)幾何校正產(chǎn)品各階段任務(wù)執(zhí)行總時(shí)間。當(dāng)總時(shí)長(zhǎng)小于時(shí)效要求時(shí)間時(shí)，以原始數(shù)據(jù)名為索引，記錄本流程所有任務(wù)資源分配方案，并根據(jù)工作流由下至上計(jì)算剩余任務(wù)最長(zhǎng)執(zhí)行時(shí)間，第i階段最長(zhǎng)執(zhí)行時(shí)間如式(12)所示。

Rcur=Tcur+Rnext

(12)

式中：Rcur表示本階段剩余任務(wù)的執(zhí)行時(shí)間，由當(dāng)前任務(wù)執(zhí)行時(shí)間Tcur和下一階段剩余任務(wù)執(zhí)行時(shí)間Rnext組成。首次資源分配結(jié)束。否則，執(zhí)行步驟5。

步驟5：若流程中第i階段任務(wù)Taski能增加資源分配，則計(jì)算由增加資源而產(chǎn)生的額外總并行開銷與降低時(shí)間的比值。

(13)

式中：j為當(dāng)前已分配資源數(shù)；Δj為預(yù)計(jì)增加資源數(shù)；Tj和Tj+Δj分別表示在原資源數(shù)和增加Δj資源后的執(zhí)行時(shí)間。

該比值表示為在增加資源時(shí)，降低單位任務(wù)執(zhí)行時(shí)間而產(chǎn)生的額外成本，當(dāng)Qi最小時(shí)，將資源分給該任務(wù)，然后繼續(xù)執(zhí)行步驟4。

根據(jù)該算法，進(jìn)行資源分配時(shí)，在滿足任務(wù)時(shí)效性要求的同時(shí)，對(duì)于并行程度高，串行分量小的預(yù)處理任務(wù)會(huì)被分配更多計(jì)算資源，減少了因盲目分配資源出現(xiàn)額外總并行開銷，防止了資源浪費(fèi)。

第二次資源分配的是為了提高機(jī)群平均資源利用率和確保因排隊(duì)而未及時(shí)執(zhí)行的任務(wù)能夠滿足時(shí)效性要求。根據(jù)系統(tǒng)實(shí)時(shí)負(fù)載情況進(jìn)行動(dòng)態(tài)資源分配：系統(tǒng)低負(fù)載時(shí)，為每個(gè)任務(wù)分配更多資源提高資源利用率；系統(tǒng)高負(fù)載時(shí)，通過降低時(shí)效要求較長(zhǎng)的任務(wù)的資源分配數(shù)目，從而讓因等待而未能按時(shí)提交的任務(wù)能夠及時(shí)完成。系統(tǒng)實(shí)時(shí)負(fù)載表示為機(jī)群實(shí)時(shí)資源利用率Ur，為使用資源數(shù)Rused和總資源數(shù)Rtotal的比值。

(14)

算法流程如圖6所示，每當(dāng)系統(tǒng)資源狀態(tài)更新時(shí)，進(jìn)行資源動(dòng)態(tài)分配和任務(wù)執(zhí)行，具體算法如下。

圖6 第二次資源分配算法流程圖

①更新所有任務(wù)的最短可等待時(shí)間，并由短到長(zhǎng)排序，并按序?qū)θ蝿?wù)進(jìn)行調(diào)度。

②當(dāng)存在任務(wù)最短可等待時(shí)間小于0時(shí)，按第一次資源分配算法重新對(duì)該任務(wù)所處工作流內(nèi)各階段子任務(wù)資源分配，并維持本次任務(wù)排序。

③選取排序后等待隊(duì)列中前x個(gè)任務(wù)，直到前第x+1個(gè)任務(wù)所需資源總和大于當(dāng)前剩余可用資源。當(dāng)x>0時(shí)，根據(jù)式(13)計(jì)算最小總并行開銷與加速時(shí)間的比值，并將資源分配給該任務(wù)，直至剩余可用資源為0。

當(dāng)x=0時(shí)，即可用資源不滿足任務(wù)需求。計(jì)算資源釋放時(shí)間，進(jìn)行資源預(yù)約，計(jì)算因預(yù)約產(chǎn)生的資源碎片，從排序后的等待隊(duì)列中，依次選出滿足資源需求且執(zhí)行時(shí)間小于資源預(yù)約時(shí)間的任務(wù)進(jìn)行回填。

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 復(fù)雜任務(wù)調(diào)度系統(tǒng)

調(diào)度系統(tǒng)主要包含基礎(chǔ)層、信息層、算法層、應(yīng)用層四層，如圖7所示。

圖7 遙感衛(wèi)星數(shù)據(jù)預(yù)處理復(fù)雜任務(wù)調(diào)度系統(tǒng)架構(gòu)圖

基礎(chǔ)層為調(diào)度系統(tǒng)的基礎(chǔ)環(huán)境，與遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)環(huán)境一致，預(yù)處理系統(tǒng)和調(diào)度系統(tǒng)基于高性能對(duì)稱多處理(symmetric multi processing，SMP)機(jī)群實(shí)現(xiàn)，調(diào)度系統(tǒng)通過對(duì)可移植的批處理系統(tǒng)(portable batch system，PBS)有關(guān)命令的封裝實(shí)現(xiàn)對(duì)機(jī)群資源的調(diào)度。PBS是目前應(yīng)用廣泛的機(jī)群資源管理系統(tǒng)，已經(jīng)成為機(jī)群系統(tǒng)優(yōu)先采用的任務(wù)管理系統(tǒng)[11]，Torque PBS為其開源的免費(fèi)版本之一。信息層用于提供調(diào)度系統(tǒng)在進(jìn)行調(diào)度決策時(shí)所需要的任務(wù)信息。算法層為前文所述算法的具體實(shí)現(xiàn)。應(yīng)用層主要功能為接收預(yù)處理系統(tǒng)提交的預(yù)處理任務(wù)，并根據(jù)任務(wù)時(shí)效性要求和機(jī)群資源利用狀態(tài)對(duì)任務(wù)進(jìn)行調(diào)度，同時(shí)提供任務(wù)監(jiān)控功能。

3.2 實(shí)驗(yàn)環(huán)境

通用遙感衛(wèi)星數(shù)據(jù)處理系統(tǒng)設(shè)備系統(tǒng)包含68個(gè)計(jì)算刀片服務(wù)器，計(jì)算節(jié)點(diǎn)配置如表3所示。

表3 機(jī)群計(jì)算節(jié)點(diǎn)服務(wù)器配置

計(jì)算系統(tǒng)整體雙精度峰值性能達(dá)到158.412 8×1012次/s。配置兩臺(tái)數(shù)據(jù)庫服務(wù)器、兩臺(tái)管理節(jié)點(diǎn)服務(wù)器、兩臺(tái)數(shù)據(jù)分發(fā)節(jié)點(diǎn)服務(wù)器，以及一套曙光ParaStor300分布式并行存儲(chǔ)系統(tǒng)，可用容量440 TB，同時(shí)并發(fā)40 GB/s讀帶寬+40 GB/s寫帶寬(每個(gè)節(jié)點(diǎn)700 MB/s讀+700 MB/s寫帶寬)，整套設(shè)備采用萬兆網(wǎng)絡(luò)互聯(lián)。實(shí)驗(yàn)中，在真實(shí)機(jī)群環(huán)境中測(cè)算不同衛(wèi)星的各預(yù)處理任務(wù)性能模型，并使用20個(gè)計(jì)算節(jié)點(diǎn)進(jìn)行仿真實(shí)驗(yàn)。

3.3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中將本文所采用的“二次資源分配算法”分別與傳統(tǒng)調(diào)度算法中的“首次適應(yīng)算法”和“優(yōu)先級(jí)調(diào)度算法”在系統(tǒng)吞吐量和任務(wù)時(shí)效性性能上進(jìn)行對(duì)比。

“首次適應(yīng)算法”按照任務(wù)提交順序選取等待隊(duì)列中滿足資源要求的任務(wù)進(jìn)行執(zhí)行，該算法不會(huì)因資源需求較大任務(wù)而出現(xiàn)任務(wù)阻塞現(xiàn)象，因而能夠提高系統(tǒng)吞吐量。

“優(yōu)先級(jí)調(diào)度算法”為系統(tǒng)根據(jù)任務(wù)優(yōu)先級(jí)依次選擇任務(wù)進(jìn)行執(zhí)行。實(shí)驗(yàn)中，優(yōu)先級(jí)確定的依據(jù)為任務(wù)的時(shí)效性，任務(wù)時(shí)效性要求越短任務(wù)優(yōu)先級(jí)越高。

傳統(tǒng)調(diào)度算法在進(jìn)行任務(wù)資源分配時(shí)，采用靜態(tài)的資源分配方式，不同衛(wèi)星不同階段任務(wù)所分配的資源數(shù)根據(jù)經(jīng)驗(yàn)值確定，該分配方案能滿足最短時(shí)效性要求。通過在預(yù)處理任務(wù)調(diào)度系統(tǒng)算法層中增加算法模塊的方式，實(shí)現(xiàn)對(duì)上述傳統(tǒng)調(diào)度算法的集成。

數(shù)據(jù)方面，使用高分一、二、六號(hào)衛(wèi)星數(shù)據(jù)各三軌進(jìn)行實(shí)驗(yàn)，總原始碼流數(shù)據(jù)量為420.50 GB。為了模擬數(shù)據(jù)時(shí)效性要求不同時(shí)調(diào)度的情況，每顆衛(wèi)星各兩軌數(shù)據(jù)時(shí)效性要求為2 h，模擬常規(guī)生產(chǎn)，總數(shù)據(jù)量304.85 GB；每顆衛(wèi)星各一軌數(shù)據(jù)時(shí)效性要求為45分鐘，模擬緊急生產(chǎn)，總數(shù)據(jù)量115.64 GB。采取同時(shí)提交多軌原始數(shù)據(jù)的方式模擬預(yù)處理系統(tǒng)高負(fù)載。最終系統(tǒng)幾何校正產(chǎn)品共計(jì)2 638景，其中，常規(guī)生產(chǎn)1 806景，緊急產(chǎn)品832景。

圖8為三種調(diào)度算法系統(tǒng)幾何校正產(chǎn)品數(shù)目隨時(shí)間的變化情況，折線不再隨時(shí)間延伸表示已完成所有產(chǎn)品生產(chǎn)。完成所有產(chǎn)品生產(chǎn)前，各時(shí)間點(diǎn)及其對(duì)應(yīng)的產(chǎn)品數(shù)目差異反映了不同算法的調(diào)度行為差異。與傳統(tǒng)算法相比，本調(diào)度算法在100分鐘左右率先完成了所有產(chǎn)品的生產(chǎn)任務(wù)，吞吐量更高。同時(shí)，因本算法在進(jìn)行調(diào)度時(shí)，會(huì)根據(jù)時(shí)效性要求進(jìn)行資源分配，使時(shí)效性相同的產(chǎn)品趨于同時(shí)完成。故在實(shí)驗(yàn)中，緊急生產(chǎn)和常規(guī)生產(chǎn)的產(chǎn)品分別在30分鐘及90分鐘附近集中完成，這使得在集中完成前的一段時(shí)間內(nèi)產(chǎn)品數(shù)目低于其他算法。雖然在這些時(shí)間段內(nèi)產(chǎn)品數(shù)目較少，但當(dāng)產(chǎn)品集中完成后，本算法實(shí)際耗時(shí)更短，系統(tǒng)吞吐量更高。

圖8 各算法系統(tǒng)幾何校正產(chǎn)品數(shù)目對(duì)比

如圖9所示，本算法在30分鐘左右完成所有緊急產(chǎn)品生產(chǎn)，在100分鐘左右完成常規(guī)產(chǎn)品生產(chǎn)，相比傳統(tǒng)算法能夠在更短時(shí)間內(nèi)滿足不同產(chǎn)品的時(shí)效性要求。“首次適應(yīng)算法”因在進(jìn)行任務(wù)調(diào)度時(shí)，僅能獲取單個(gè)任務(wù)的提交順序、所需資源數(shù)，無法對(duì)任務(wù)類型進(jìn)行區(qū)分，任務(wù)調(diào)度具有相對(duì)隨機(jī)性，無法對(duì)緊急產(chǎn)品生產(chǎn)任務(wù)進(jìn)行優(yōu)先調(diào)度，最終滿足時(shí)效要求產(chǎn)品較少?！皟?yōu)先級(jí)調(diào)度算法”在進(jìn)行調(diào)度時(shí)，因緊急任務(wù)具有較高的優(yōu)先級(jí)而優(yōu)先執(zhí)行，能夠較好地滿足各類任務(wù)的時(shí)效性要求。

圖9 各算法滿足時(shí)效要求產(chǎn)品數(shù)目對(duì)比

表4為各算法總執(zhí)行時(shí)間、時(shí)效達(dá)成率及吞吐量對(duì)比。時(shí)效達(dá)成率為滿足時(shí)效要求產(chǎn)品景數(shù)與產(chǎn)品總景數(shù)的比值；吞吐量為原始碼流數(shù)據(jù)量與總執(zhí)行時(shí)間的比值?？梢姳舅惴ㄔ跁r(shí)效達(dá)成率和吞吐量上都具有一定優(yōu)勢(shì)。

表4 各算法時(shí)效達(dá)成率及吞吐量對(duì)比

從實(shí)驗(yàn)結(jié)果可知，“優(yōu)先級(jí)調(diào)度算法”能夠較好地從任務(wù)時(shí)效性角度對(duì)任務(wù)進(jìn)行調(diào)度，但當(dāng)系統(tǒng)負(fù)載較高時(shí)，存在高優(yōu)先級(jí)任務(wù)無法獲取所需資源，而低優(yōu)先級(jí)任務(wù)無法及時(shí)利用空閑資源的現(xiàn)象，導(dǎo)致了資源浪費(fèi)，系統(tǒng)吞吐量較低?！笆状芜m應(yīng)算法”能夠通過按序掃描等待隊(duì)列，防止了資源需求較大任務(wù)造成的“阻塞”現(xiàn)象，相對(duì)于優(yōu)先級(jí)調(diào)度法來說很大程度提高了吞吐量，但因調(diào)度過程中，僅考慮吞吐量，而未將任務(wù)時(shí)效性作為調(diào)度依據(jù)，故任務(wù)時(shí)效性不同時(shí)，難以主動(dòng)滿足不同任務(wù)的時(shí)效性要求。本算法在進(jìn)行調(diào)度時(shí)，為了使同時(shí)提交的所有任務(wù)都能滿足時(shí)效性要求，會(huì)優(yōu)先對(duì)資源需求量大、可等待時(shí)間較短的任務(wù)進(jìn)行調(diào)度。相應(yīng)地，會(huì)降低剩余子任務(wù)較少、可等待時(shí)間較長(zhǎng)的任務(wù)的調(diào)度優(yōu)先級(jí)和資源分配數(shù)目，從而滿足不同任務(wù)的時(shí)效性要求，且在進(jìn)行資源分配時(shí)，通過對(duì)比不同任務(wù)性能，減少了因額外總并行開銷導(dǎo)致的資源浪費(fèi)，提高了系統(tǒng)吞吐量。

4 結(jié)束語

本文針對(duì)遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)中復(fù)雜任務(wù)在進(jìn)行資源分配和調(diào)度過程中存在盲目性、難以滿足任務(wù)時(shí)效性要求的問題，在預(yù)處理任務(wù)性能模型和工作流任務(wù)預(yù)估模型的基礎(chǔ)上，確定了由任務(wù)時(shí)效性及系統(tǒng)資源利用率驅(qū)動(dòng)的復(fù)雜任務(wù)調(diào)度算法。該算法通過兩次資源分配，既滿足了任務(wù)時(shí)效性要求，也更合理地利用了計(jì)算資源，減少了資源浪費(fèi)，提高了系統(tǒng)吞吐量。

但本算法還存在一定的不足，主要表現(xiàn)在本調(diào)度算法的基礎(chǔ)是預(yù)處理任務(wù)性能模型，現(xiàn)階段確定性能模型主要采用人工測(cè)算的方式，進(jìn)行預(yù)估時(shí)的準(zhǔn)確度與測(cè)試樣本數(shù)相關(guān)，當(dāng)預(yù)處理程序版本更新或集成新的衛(wèi)星處理功能時(shí)，測(cè)算各任務(wù)性能模型的工作量較大。下一步研究計(jì)劃為通過記錄任務(wù)的執(zhí)行日志，實(shí)現(xiàn)數(shù)據(jù)驅(qū)動(dòng)的預(yù)處理任務(wù)性能模型自動(dòng)建模。一方面提高任務(wù)性能模型在預(yù)估時(shí)的準(zhǔn)確性，另一方面提高調(diào)度系統(tǒng)的可擴(kuò)展性，從而更好地對(duì)遙感衛(wèi)星數(shù)據(jù)預(yù)處理系統(tǒng)中的復(fù)雜任務(wù)進(jìn)行調(diào)度。