方鑫+++周珂+++嚴(yán)運(yùn)廣+++陳前程+++黃祥志+++王棟

摘 要： 遙感技術(shù)的進(jìn)步使遙感數(shù)據(jù)質(zhì)量得以提高，體量急劇增長(zhǎng)，因此有必要研制高效的遙感數(shù)據(jù)處理集群系統(tǒng)用于提高遙感數(shù)據(jù)處理的效能。對(duì)遙感數(shù)據(jù)處理的時(shí)效性評(píng)估可以從處理效率和計(jì)算資源利用率兩個(gè)角度進(jìn)行評(píng)估。提出一種結(jié)合遙感數(shù)據(jù)處理先驗(yàn)值的動(dòng)態(tài)雙向?qū)崟r(shí)匹配調(diào)度算法，即同步考慮先驗(yàn)值、任務(wù)情況和計(jì)算節(jié)點(diǎn)狀態(tài)的雙向調(diào)度的方法。實(shí)驗(yàn)結(jié)果表明，該算法有效的提高了集群系統(tǒng)的遙感數(shù)據(jù)處理效能。

關(guān)鍵詞： 任務(wù)調(diào)度； 動(dòng)態(tài)雙向匹配； 遙感數(shù)據(jù)處理； 集群

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2016）05-04-04

Abstract： The progress of remote sensing technology makes the quality of remote sensing data improved， and the volume of the remote sensing data increased rapidly. Therefore， it is necessary to develop an efficient remote sensing data processing cluster system to improve the efficiency of remote sensing data processing. The timeliness of remote sensing data processing can be evaluated from two perspectives： the processing efficiency and the computing resource utilization. In this paper， a dynamic bidirectional real-time matching scheduling algorithm combined with the prior value of remote sensing data processing is proposed； it's a bi-directional scheduling method of simultaneous consideration of the priori values， task conditions and the computing node state. Experimental results show that the proposed algorithm can effectively improve the efficiency of remote sensing data processing in cluster system.

Key words： task scheduling； dynamic bidirectional matching； remote sensing data processing； cluster

0 引言

隨著遙感技術(shù)的快速發(fā)展，遙感數(shù)據(jù)量呈現(xiàn)幾何級(jí)增長(zhǎng)，實(shí)際應(yīng)用中對(duì)遙感數(shù)據(jù)處理的時(shí)間和精度要求越來(lái)越高。集群處理系統(tǒng)的出現(xiàn)大大提高了遙感數(shù)據(jù)處理的速度。高效的遙感數(shù)據(jù)處理集群調(diào)度方法，是充分發(fā)揮集群平臺(tái)優(yōu)勢(shì)的關(guān)鍵所在。

中國(guó)科學(xué)院遙感與數(shù)字地球研究所研制的面向遙感數(shù)據(jù)高性能處理集群系統(tǒng)[1，11]具有成本可控、可靠性高、擴(kuò)展性強(qiáng)等特點(diǎn)，該集群系統(tǒng)的作業(yè)調(diào)度模塊包括調(diào)度節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)兩個(gè)部分。調(diào)度節(jié)點(diǎn)是集群系統(tǒng)中某一臺(tái)計(jì)算機(jī)，負(fù)責(zé)整個(gè)集群系統(tǒng)資源分配和任務(wù)的調(diào)度，保存有面向任務(wù)隊(duì)列和面向計(jì)算節(jié)點(diǎn)隊(duì)列。此外，調(diào)度節(jié)點(diǎn)上存儲(chǔ)有各個(gè)計(jì)算節(jié)點(diǎn)的負(fù)載信息表，表中保存有計(jì)算節(jié)點(diǎn)的一些實(shí)時(shí)信息如計(jì)算節(jié)點(diǎn)MAC地址，CPU利用率等，還存有生產(chǎn)各種遙感產(chǎn)品所需要的平均時(shí)間等。計(jì)算節(jié)點(diǎn)是集群系統(tǒng)中所有計(jì)算機(jī)，調(diào)度節(jié)點(diǎn)也可作為計(jì)算節(jié)點(diǎn)使用。每個(gè)（臺(tái)）計(jì)算節(jié)點(diǎn)都連接到調(diào)度節(jié)點(diǎn)，負(fù)責(zé)接收調(diào)度發(fā)來(lái)的產(chǎn)品生產(chǎn)任務(wù)，和調(diào)度節(jié)點(diǎn)協(xié)同完成工作，計(jì)算節(jié)點(diǎn)還帶有各種產(chǎn)品生產(chǎn)所需要的動(dòng)態(tài)庫(kù)、參數(shù)等信息；數(shù)據(jù)的組織管理采用五層十五級(jí)標(biāo)準(zhǔn)[2]。

目前，常用的任務(wù)調(diào)度算法有：先來(lái)先服務(wù)算法、雙匹配動(dòng)態(tài)模型算法、截止期最早優(yōu)先等。這些算法都各有特點(diǎn)。先來(lái)先服務(wù)算法[10]就是根據(jù)到達(dá)的先后順序調(diào)度執(zhí)行，結(jié)構(gòu)簡(jiǎn)單容易實(shí)現(xiàn)，但該算法短作業(yè)在系統(tǒng)中的駐留平均時(shí)間與長(zhǎng)作業(yè)的駐留平均時(shí)間相同，這對(duì)短作業(yè)是不利的；雙匹配動(dòng)態(tài)算法[6]能夠較好地實(shí)現(xiàn)負(fù)載與系統(tǒng)吞吐率的平衡，但當(dāng)系統(tǒng)中任務(wù)量逐漸增多時(shí)，性能快速下降；截止期最早最優(yōu)先算法[12]根據(jù)任務(wù)截止期來(lái)決定任務(wù)執(zhí)行順序，讓截止期最早的任務(wù)優(yōu)先執(zhí)行，但是截止期最早的任務(wù)并不一定是最重要的任務(wù)。然而上述任務(wù)調(diào)度算法，均未考慮到遙感影像數(shù)據(jù)量大、產(chǎn)品算法耗時(shí)長(zhǎng)的特點(diǎn)。

1 集群調(diào)度算法模型

本文設(shè)計(jì)的集群調(diào)度算法模型是一種結(jié)合遙感數(shù)據(jù)處理先驗(yàn)值的動(dòng)態(tài)雙向?qū)崟r(shí)匹配調(diào)度算法模型，由面向任務(wù)隊(duì)列模型和面向計(jì)算節(jié)點(diǎn)隊(duì)列模型兩個(gè)部分組成。其主要思路是：在結(jié)合先驗(yàn)值的情況下，一方面，面向任務(wù)時(shí)考慮任務(wù)等待時(shí)間和任務(wù)量大小等因素來(lái)確定任務(wù)隊(duì)列；另一方面，面向計(jì)算資源時(shí)，在動(dòng)態(tài)獲取計(jì)算資源負(fù)載率的情況下，形成一個(gè)計(jì)算資源隊(duì)列；將最優(yōu)計(jì)算資源匹配給優(yōu)先級(jí)最高的任務(wù)，從而完成任務(wù)和計(jì)算資源的動(dòng)態(tài)雙向匹配。

1.1 先驗(yàn)值獲取

本文使用的先驗(yàn)值定義為集群處理某類產(chǎn)品時(shí)，根據(jù)各個(gè)并行節(jié)點(diǎn)反饋到調(diào)度節(jié)點(diǎn)上的該類產(chǎn)品的處理時(shí)間，取平均值。

先驗(yàn)值是動(dòng)態(tài)更新的，這種動(dòng)態(tài)更新使先驗(yàn)值的存在更具參考性，當(dāng)節(jié)點(diǎn)上反饋新的該類產(chǎn)品生產(chǎn)時(shí)間信息時(shí)，和該先驗(yàn)值再取平均值作為新的先驗(yàn)值。得到的先驗(yàn)值在調(diào)度中的數(shù)據(jù)結(jié)構(gòu)，用Map型數(shù)據(jù)結(jié)構(gòu)方式記錄下來(lái)，Key代表是計(jì)算節(jié)點(diǎn)處理的任務(wù)類型，Value是代表節(jié)點(diǎn)處理此類型任務(wù)所用的時(shí)間。