基于MPI的遙測(cè)源碼多站拼接并行化算法研究?

張志國(guó) 張慧娟 徐洪洲

（91550部隊(duì) 大連 116023）

1 引言

完整、無(wú)誤碼的遙測(cè)原始數(shù)據(jù)是進(jìn)行遙測(cè)事后數(shù)據(jù)處理的基礎(chǔ)。實(shí)際任務(wù)中，一臺(tái)套遙測(cè)設(shè)備因作用距離的限制，只能接收一段時(shí)間內(nèi)的遙測(cè)數(shù)據(jù)；受設(shè)備工作狀態(tài)、遙測(cè)傳輸信號(hào)穩(wěn)定性等因素影響，單臺(tái)遙測(cè)設(shè)備一般接收不到完整、無(wú)誤碼的遙測(cè)數(shù)據(jù)。為保證可靠性，在一個(gè)任務(wù)時(shí)段內(nèi)往往有多臺(tái)套遙測(cè)設(shè)備同時(shí)接收遙測(cè)數(shù)據(jù)。為得到一組完整的遙測(cè)數(shù)據(jù)，需要將多臺(tái)套遙測(cè)設(shè)備測(cè)到的遙測(cè)數(shù)據(jù)拼接組合。由于遙測(cè)數(shù)據(jù)量大，遙測(cè)源碼多站拼接工作需要進(jìn)行上千萬(wàn)點(diǎn)的數(shù)據(jù)比較和大量的磁盤(pán)I/O操作，因此遙測(cè)數(shù)據(jù)源碼拼接需要耗費(fèi)很長(zhǎng)的時(shí)間，目前此功能已成為制約遙測(cè)數(shù)據(jù)快速處理的瓶頸。為加快遙測(cè)數(shù)據(jù)處理速度、縮短遙測(cè)處理時(shí)間，迫切需要對(duì)遙測(cè)源碼拼接工作進(jìn)行優(yōu)化。目前遙測(cè)源碼拼接工作是在一臺(tái)計(jì)算機(jī)上進(jìn)行的，可以考慮將拼接作業(yè)分配到局域網(wǎng)內(nèi)的多臺(tái)計(jì)算上，使整個(gè)拼接工作實(shí)現(xiàn)并行化，效率將會(huì)得到很大的提升。文中先介紹MPI并行化基本概念，再闡述遙測(cè)源碼多站拼接并行化算法，并給出實(shí)例和結(jié)果分析。

2 MPI并行化概述

2.1 并行計(jì)算

所謂的并行計(jì)算（parallel computing），首先將任務(wù)進(jìn)行分解，細(xì)分為多個(gè)子任務(wù)，然后在并行機(jī)上將這些子任務(wù)分配給不同的處理器［1～4］。這些處理器之間通過(guò)相應(yīng)的技術(shù)手段進(jìn)行通信，并發(fā)地執(zhí)行子任務(wù)［7］。這樣可以充分地利用計(jì)算資源，提高求解速度，縮小求解應(yīng)用問(wèn)題規(guī)模。

為保障并行計(jì)算的成功進(jìn)行，以下三個(gè)基本條件是必備的［5，6］：

1）并行機(jī)。兩臺(tái)以上可以通過(guò)網(wǎng)絡(luò)互連，互通的處理機(jī)。

2）所要解決的問(wèn)題必須具備并行度［7］。也就是說(shuō)，應(yīng)用問(wèn)題能夠分解成多個(gè)子任務(wù)，這些子任務(wù)可以并發(fā)地執(zhí)行［8～9］。而并行算法的設(shè)計(jì)核心，就是將應(yīng)用問(wèn)題進(jìn)行拆分，分解為多個(gè)子任務(wù)同時(shí)執(zhí)行［10］。

3）并行編程。在并行編程開(kāi)發(fā)環(huán)境下，將原有串行程序改造為并行程序，從而實(shí)現(xiàn)應(yīng)用問(wèn)題的并行化求解。

2.2 MPI編程

MPI（message passing interface），從字面上理解是消息傳遞接口。它并非一種編程語(yǔ)言，而是一組具有近百個(gè)函數(shù)可供調(diào)用的編程模型。它提供的這些函數(shù)可以在C語(yǔ)言和Fortran中進(jìn)行調(diào)用，完成子任務(wù)進(jìn)程間的通信［11］。

MPICH是MPI最流行的非專利實(shí)現(xiàn)，由Ar?gonne國(guó)家實(shí)驗(yàn)室和密西西比州立大學(xué)聯(lián)合開(kāi)發(fā)，具有更好的可移植性［12］。MPICH的開(kāi)發(fā)與MPI規(guī)范的制定是同步進(jìn)行的，因此MPICH最能反映MPI的發(fā)展與變化。MPICH的主要特點(diǎn)是：開(kāi)源、高效、可移植性好、功能強(qiáng)大；支持多核、多程序多數(shù)據(jù)編程、對(duì)稱多處理系統(tǒng)、異構(gòu)集群系統(tǒng)和大規(guī)模并行計(jì)算系統(tǒng)。

主從（Master/Slave）模式是常用的MPI并行編程模式，它由運(yùn)行在主節(jié)點(diǎn)的主程序和多個(gè)運(yùn)行在子節(jié)點(diǎn)的子程序構(gòu)成。主進(jìn)程負(fù)責(zé)進(jìn)程初始化、任務(wù)分配、子結(jié)果收集、最終結(jié)果顯示等任務(wù)。子進(jìn)程負(fù)責(zé)主進(jìn)程任務(wù)數(shù)據(jù)接收、數(shù)據(jù)計(jì)算、結(jié)算結(jié)果提交等任務(wù)。主程序工作流程如下：1）初始化并行計(jì)算環(huán)境；2）數(shù)據(jù)劃分并進(jìn)行子節(jié)點(diǎn)任務(wù)分配；3）將數(shù)據(jù)和子計(jì)算任務(wù)發(fā)送到各個(gè)子計(jì)算節(jié)點(diǎn)；4）等待接收各子節(jié)點(diǎn)的計(jì)算結(jié)果；5）將各子節(jié)點(diǎn)的計(jì)算結(jié)果整合為一個(gè)完整結(jié)果，并顯示輸出。子程序工作流程如下：1）等待接收主進(jìn)程的計(jì)算數(shù)據(jù)；2）根據(jù)標(biāo)識(shí)識(shí)別出主進(jìn)程分配給本子進(jìn)程的任務(wù)，并進(jìn)行計(jì)算；3）將計(jì)算結(jié)果發(fā)送給主進(jìn)程。

3 遙測(cè)源碼多站拼接并行化方法

現(xiàn)有的遙測(cè)多站拼接串行算法如下：

1）分離提取遙測(cè)數(shù)據(jù)和時(shí)間，形成數(shù)據(jù)文件和時(shí)間文件，時(shí)間文件的一個(gè)時(shí)間點(diǎn)對(duì)應(yīng)數(shù)據(jù)文件的一個(gè)全幀數(shù)據(jù)。此步對(duì)所有測(cè)站數(shù)據(jù)（分別編號(hào)為D1，D2，D3，…，Dm）分別進(jìn)行；

2）找到所有測(cè)站接收的最早遙測(cè)數(shù)據(jù)時(shí)間T1及最晚接收的數(shù)據(jù)時(shí)間T2；

3）從T1開(kāi)始，以一幀的時(shí)間間隔為步長(zhǎng)，在所有測(cè)站中尋找在每個(gè)數(shù)據(jù)時(shí)間節(jié)點(diǎn)Tn對(duì)應(yīng)的完整遙測(cè)幀，直到T2結(jié)束；其中，在所有測(cè)站中尋找在每個(gè)數(shù)據(jù)時(shí)間節(jié)點(diǎn)Tn對(duì)應(yīng)的完整遙測(cè)幀需要進(jìn)行多次搜索和比較，其具體過(guò)程如下：（1）依次搜索D1，D2，D3，…，Dm在數(shù)據(jù)時(shí)間節(jié)點(diǎn)Tn對(duì)應(yīng)的遙測(cè)幀；（2）比較Tn對(duì)應(yīng)的遙測(cè)幀，取相同個(gè)數(shù)最多的遙測(cè)幀為T(mén)n點(diǎn)對(duì)應(yīng)的遙測(cè)幀加入到完整遙測(cè)幀序列。其中，（1）步搜索，每個(gè)測(cè)站數(shù)據(jù)最多需要進(jìn)行n次搜索，最少需要一次搜索；（2）步使用兩兩比較的方式，在測(cè)站數(shù)量m是2的幾何級(jí)數(shù)時(shí)，所有測(cè)站都相同的情況下需進(jìn)行次搜索；如有8個(gè)測(cè)站，所有測(cè)站在Tn節(jié)點(diǎn)都有遙測(cè)幀、且遙測(cè)幀相同時(shí)，需進(jìn)行4+2+1=7次比較；測(cè)站數(shù)據(jù)有異常情況導(dǎo)致數(shù)據(jù)幀不同的情況下，需進(jìn)行的比較次數(shù)要多于7次。在測(cè)站數(shù)量不是2的幾何級(jí)數(shù)時(shí)或者遙測(cè)幀有不相同的情況下，比較次數(shù)更多。（1）、（2）步驟中多次的搜索和比較，是導(dǎo)致遙測(cè)源碼拼接耗費(fèi)時(shí)間較長(zhǎng)的主要原因。

為了能夠使用MPI計(jì)算框架，需要對(duì)遙測(cè)源碼拼接算法進(jìn)行改進(jìn)：

第1）步，由于是對(duì)多個(gè)測(cè)站的遙測(cè)數(shù)據(jù)文件分別進(jìn)行處理，可以將作業(yè)分配到不同計(jì)算機(jī)上進(jìn)行；這一步有大量的I/O操作，計(jì)算機(jī)的I/O是瓶頸，通過(guò)多臺(tái)計(jì)算機(jī)并行處理；

第2）步耗費(fèi)時(shí)間很少，不需要并行處理；

第3）步，是耗時(shí)最多的步驟，需對(duì)其算法進(jìn)行并行化改造，以提高計(jì)算效率。

（1）主控制節(jié)點(diǎn)將數(shù)據(jù)拼接工作盡量平均，可以通過(guò)時(shí)間段平均或者數(shù)據(jù)量平均等方法，分為多個(gè)子段，有幾個(gè)計(jì)算節(jié)點(diǎn)分幾個(gè)子段；

（2）每個(gè)計(jì)算節(jié)點(diǎn)并行對(duì)分到的子段進(jìn)行遙測(cè)源碼拼接；

（3）計(jì)算節(jié)點(diǎn)計(jì)算完成后，將計(jì)算結(jié)果反饋給控制節(jié)點(diǎn)，由主控制節(jié)點(diǎn)完成各個(gè)子段結(jié)果的拼接工作。

4 算例與分析

通過(guò)單機(jī)單核計(jì)算和多機(jī)并行化計(jì)算兩種方式，對(duì)某三次任務(wù)的遙測(cè)數(shù)據(jù)進(jìn)行了多站拼接的耗時(shí)測(cè)算，結(jié)果如表1～表3、圖1～圖3所示。

表1 6站每站100M拼接耗時(shí)

表2 6站每站200M拼接耗時(shí)

表3 6站每站400M拼接耗時(shí)

圖1 6站每站100M拼接耗時(shí)結(jié)果比對(duì)

圖2 6站每站200M拼接耗時(shí)結(jié)果比對(duì)

圖3 6站每站400M拼接耗時(shí)結(jié)果比對(duì)

從實(shí)驗(yàn)數(shù)據(jù)可知，在目前多站遙測(cè)體制條件下，并行算法基本上與測(cè)量站個(gè)數(shù)無(wú)關(guān)，只與單站數(shù)據(jù)大小、子節(jié)點(diǎn)數(shù)量正相關(guān)；理論上只要計(jì)算節(jié)點(diǎn)足夠，便可完成多站遙測(cè)體制下的數(shù)據(jù)拼接任務(wù)。

5 結(jié)語(yǔ)

針對(duì)當(dāng)前多站體制下遙測(cè)源碼拼接較慢，制約遙測(cè)數(shù)據(jù)快速處理的問(wèn)題，文中提出利用MPI并行計(jì)算框架，將遙測(cè)源碼拼接串行算法改進(jìn)為并行算法。算例結(jié)果表明，該方法能充分地利用局域網(wǎng)內(nèi)計(jì)算資源，大大提高了遙測(cè)源碼拼接速度，可以用于遙測(cè)事后數(shù)據(jù)快速處理。

［1］劉晶.基于PVM的并行計(jì)算［J］.廣東石油化工學(xué)院學(xué)報(bào)，2012（4）：34-35.

［2］楊忠志，張晶，劉翠，等.ABEEMσπ/MM模型中靜電相互作用能的并行化［J］.遼寧師范大學(xué)學(xué)報(bào)，2009（4）：457-461.

［3］曾芷德.對(duì)并行測(cè)試生成理論的一點(diǎn)綜述［J］.桂林電子工業(yè)學(xué)院學(xué)報(bào)，2000（4）：100-105.

［4］趙俊軍，劉士鋒，張直云.基于網(wǎng)絡(luò)分割技術(shù)的交通最短路徑應(yīng)用［J］.昆明冶金高等專科學(xué)校學(xué)報(bào)，2015（5）：60-64.

［5］李永兵.并行編程環(huán)境與工具［J］.長(zhǎng)治學(xué)院學(xué)報(bào)，2009（2）：41-43.

［6］廉燦國(guó)，李軍營(yíng)，王長(zhǎng)江，等.并行算法在彈道與諸元計(jì)算中的應(yīng)用［J］.彈箭與制導(dǎo)學(xué)報(bào)，2011（4）：162-164.

［7］龍柏.并行計(jì)算平臺(tái)上的數(shù)據(jù)索引技術(shù)研究［D］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2011：52-55.

［8］魏秋娟.網(wǎng)格環(huán)境下電力營(yíng)銷系統(tǒng)任務(wù)調(diào)度的研究［D］.北京：華北電力大學(xué)，2011：32-37.

［9］符丁，黃漢堂.基于本體和多Agent的面向任務(wù)協(xié)同編程［J］.計(jì)算機(jī)工程，2010（9）：47-49.

［10］張宇.對(duì)Linux集群在并行計(jì)算中的應(yīng)用研究［D］.廣州：中山大學(xué)，2009：45-56.

［11］趙少林.廣域網(wǎng)協(xié)議在HPC集群上的應(yīng)用分析［D］.鄭州：鄭州大學(xué)，2005：23-24.

［12］張偉.航空電子系統(tǒng)中的光纖通道技術(shù)研究［D］.西安：西北工業(yè)大學(xué)，2005：34-37.