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

張志國 張慧娟 徐洪洲

（91550部隊 大連 116023）

1 引言

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

2 MPI并行化概述

2.1 并行計算

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

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

1）并行機。兩臺以上可以通過網絡互連，互通的處理機。

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

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

2.2 MPI編程

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

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

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

3 遙測源碼多站拼接并行化方法

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

1）分離提取遙測數據和時間，形成數據文件和時間文件，時間文件的一個時間點對應數據文件的一個全幀數據。此步對所有測站數據（分別編號為D1，D2，D3，…，Dm）分別進行；

2）找到所有測站接收的最早遙測數據時間T1及最晚接收的數據時間T2；

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

為了能夠使用MPI計算框架，需要對遙測源碼拼接算法進行改進：

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

第2）步耗費時間很少，不需要并行處理；

第3）步，是耗時最多的步驟，需對其算法進行并行化改造，以提高計算效率。

（1）主控制節(jié)點將數據拼接工作盡量平均，可以通過時間段平均或者數據量平均等方法，分為多個子段，有幾個計算節(jié)點分幾個子段；

（2）每個計算節(jié)點并行對分到的子段進行遙測源碼拼接；

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

4 算例與分析

通過單機單核計算和多機并行化計算兩種方式，對某三次任務的遙測數據進行了多站拼接的耗時測算，結果如表1～表3、圖1～圖3所示。

表1 6站每站100M拼接耗時

表2 6站每站200M拼接耗時

表3 6站每站400M拼接耗時

圖1 6站每站100M拼接耗時結果比對

圖2 6站每站200M拼接耗時結果比對

圖3 6站每站400M拼接耗時結果比對

從實驗數據可知，在目前多站遙測體制條件下，并行算法基本上與測量站個數無關，只與單站數據大小、子節(jié)點數量正相關；理論上只要計算節(jié)點足夠，便可完成多站遙測體制下的數據拼接任務。

5 結語

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

［1］劉晶.基于PVM的并行計算［J］.廣東石油化工學院學報，2012（4）：34-35.

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

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

［4］趙俊軍，劉士鋒，張直云.基于網絡分割技術的交通最短路徑應用［J］.昆明冶金高等專科學校學報，2015（5）：60-64.

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

［6］廉燦國，李軍營，王長江，等.并行算法在彈道與諸元計算中的應用［J］.彈箭與制導學報，2011（4）：162-164.

［7］龍柏.并行計算平臺上的數據索引技術研究［D］.合肥：中國科學技術大學，2011：52-55.

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

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

［10］張宇.對Linux集群在并行計算中的應用研究［D］.廣州：中山大學，2009：45-56.

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

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