采用MapReduce模型的甚長基線干涉測量并行處理方法

田斌,何強,王佳,鄭雨西

(1.西安交通大學電子與信息工程學院,710049,西安;2.西安衛星測控中心,710043,西安)

?

采用MapReduce模型的甚長基線干涉測量并行處理方法

田斌1,2,何強2,王佳2,鄭雨西2

(1.西安交通大學電子與信息工程學院,710049,西安;2.西安衛星測控中心,710043,西安)

針對傳統甚長基線干涉測量(very long baseline interferometry,VLBI)并行處理方法存在邏輯復雜、數據存儲和計算擴展性較差等缺點,基于MapReduce模型設計了一種VLBI觀測數據相關的并行處理方法。該方法采用模型周期作為數據并行處理基本單元,構建數據關聯算法分割觀測數據使各臺站同一模型周期數據對齊到同一波前,設計實現數據相關計算的Map過程,使用Reduce對各模型周期結果進行綜合處理以得到最終結果。實驗結果表明:該方法在積分周期包含的模型周期數量大于節點CPU核數時性能比傳統方式低25%左右,在積分周期包含的模型周期數量小于節點CPU核數時通常能提供更高的計算效率,并且能簡化VLBI并行相關處理的復雜度,具有更好的數據存儲和計算可擴展性。

甚長基線干涉測量;數據相關處理;并行處理;MapReduce模型

甚長基線干涉測量(very long baseline interferometry,VLBI)技術利用分布在不同地理位置的兩個或多個天線分別接收記錄同一空間目標發射的信號,經相關處理后獲取目標相對兩個測站天線的時延和時延率觀測量,轉化后得到目標視向相對于基線向量的角位置信息。VLBI自20世紀60年代問世以來,在射電天文大地測量等領域得到了廣泛的應用,特別是在此基礎上發展起來的差分單向測距測速、雙差分單向測距測速和同波束干涉測量等干涉測量技術,已成為深空探測器精密導航定位的主要技術手段,為各類深空探測任務的成功實施提供了可靠的技術保障。

近年來,隨著觀測臺站數目的增加,以及觀測帶寬的日益提高,對VLBI數據處理的要求越來越高,如何高速處理大量觀測數據是一個迫切需要解決的問題。VLBI處理的核心是數據相關處理,它是一種能夠高度并行的應用,具有數據密集和計算密集的雙重特征。首先,VLBI觀測設備采樣率很高,產生的數據量非常大。當前中國VLBI網有5個臺站,每個臺站8個通道,單個通道最大帶寬為8 MHz,采用2 bit量化時,其數據速率可達16 MB/s,5臺站總數據速率為80 MB/s。其次,相關處理使用快速傅里葉變換(fast Fourier transformation, FFT)將產生大量中間結果數據,例如對于通道數為C的M點輸入數據,在Linux 64位操作系統中使用雙精度復數數據類型,計算后的結果長度將擴展至原始數據的16MC倍。最后,相關處理中的條紋旋轉、FFT運算和叉乘等均涉及大量浮點運算,需要耗費很多CPU計算時間。對N臺站、M點數據的FFT變換,需要執行MN(5Nlog2M+2N+6.5)[1]次浮點運算。事實上,由于還需進行大量其他運算,實際計算量遠比該值大。

VLBI最初采用專用硬件處理機,但是隨著通用計算機性能的提高,使用軟件相關處理機處理數據成為當前流行的趨勢,DiFX[2]、Softc[3]、K5[4]和NRC[5]等軟件相關處理機就是典型代表。這些軟件相關處理機大都將處理數據集中存儲在存儲服務器上,采用消息傳遞接口(message passing intorface,MPI)或MPI+OpenMP等經典并行計算模式,能較好地進行數據并行處理工作,但是存在程序結構復雜、數據存儲和計算擴展性較差等缺點。

MapReduce是近年來隨著云計算興起的一種新型并行計算模型,被廣泛應用于海量數據的高速處理。與傳統并行方法相比,MapReduce通過采用一種稱為無依賴并行和串行同步的計算抽象,并在內部提供數據劃分、并行任務調度、通信、容錯和負載均衡等機制,實現了程序的自動并行處理,極大地降低了開發人員的難度,具有高可擴展性和高度并行性。本文基于云計算模型MapReduce提出和設計了一種稱為MR-VLBI的并行相關處理方法。

1 VLBI相關處理原理

VLBI的幾何原理如圖1所示[6-7]。假設空間目標發射的射頻信號為

s(t)=sB(t)ej2πφt

(1)

圖1 VLBI幾何原理圖

式中:sB(t)為帶寬為B的基帶信號;φ為射頻頻率。同一基線的兩測站同步接收的信號分別為(以測站1為參考)

s1(t)=sB(t)

(2)

s2(t)=sB(t-τg(t))ej2πf(t-τg(t))

(3)

式中:兩測站本振頻率都為f;τg(t)為目標相對兩測站的時延差,是數據處理時提取的觀測量。

按照進行傅里葉變換和乘法運算的順序,VLBI數據相關處理機被分為FX和XF兩種類型。XF型先按一條基線的兩個測站的觀測數據兩兩相乘,獲得互相關函數及干涉條紋,然后再進行傅里葉變換得到干涉條紋的功率譜;FX型是先對測站觀測數據進行傅里葉變換,然后再按各基線的兩測站數據進行相乘,獲得干涉條紋的功率譜[7]。雖然算法流程不一致,但是兩者獲得的最終結果是相同的。

圖2顯示了FX相關處理機的計算流程,采集信號vi(t)先后經歷整數比特時延補償、條紋旋轉、FFT、小數比特補償和互譜累加5個環節的處理。

圖2 FX型相關處理機的計算流程

整數比特時延補償利用先驗軌道預報模型對原始數據進行補償,目的是將兩路信號對準到同一波前,它是粗補償,只精確到采樣時間間隔(整數比特);條紋旋轉的目的是降低條紋頻率,消除相位因子;FFT的目的是對輸入的兩路信號進行FFT運算,將其從時域變換到頻域;小數比特補償是精補償,完成整數比特補償后剩余的時間誤差補償;互譜累加積分是為了提高信噪比,從而提高后續殘余時延、時延率提取的精度。

2 MR-VLBI算法設計

2.1 MR-VLBI處理框架

MapReduce的基本思想是將待處理的數據集分割成多個不相關的子集,每個子集分別由一個Map獨立操作以產生中間結果,然后這些中間結果通過Reduce歸約合并成最終結果[8]。Map和Reduce的模型分別為Map(k1,v1)→list(k2,v2)和Reduce(k2,list(v2))→list(v2)。其中,Map以鍵值對(k1,v1)為輸入,其操作后將產生一系列中間鍵值對list(k2,v2),該結果經內部排序會產生Reduce的輸入list(k2,list(v2)),Reduce函數合并所有具有相同key的list(v2)輸出最后的結果。

從并行方法的角度看,VLBI相關處理屬于數據并行。按照數據分解方式的不同,VLBI并行方式可分為基線并行、測站并行、通道并行和時間并行4類[9]。基線并行按照基線對觀測數據進行劃分,設置與基線數目相同的計算節點,每個節點只負責處理指定基線的數據;測站并行按照測站對觀測數據進行劃分,針對每個測站設立一個FFT計算節點,首先由它負責對該站觀測數據進行FFT,然后再將變換后的結果傳遞給相關節點進行互譜計算;通道并行按照通道對觀測數據進行劃分,每個計算節點僅負責處理某一通道所有測站觀測數據,不同通道數據由不同相關節點處理;時間并行按照時間對觀測數據進行劃分,每個計算節點負責處理某一時段的數據,各時間片數據由不同的節點處理。

這些模式都存在一些問題,例如基線并行會產生大量的數據存儲冗余和計算冗余,測站并行會因在節點間交換FFT產生的臨時結果而導致產生大量的數據傳輸,通道并行的調度邏輯則非常復雜。這4種類型都可映射到MapReduce模型中,但綜合比較起來,時間并行最為理想,它不會產生計算冗余,也不要求大量的數據交換。MR-VLBI采用了這種模式,其處理框架如圖3所示,包括數據分割、相關計算和結果綜合3個步驟。

圖3 MR-VLBI處理框架

數據分割按照時間將各臺站的觀測數據劃分成不相關的片段,奠定并行計算的基礎。當分割完成后,各臺站相同模型周期的數據將被輸入到同一個相關計算處理單元,也即相關計算Map,進行觀測信號的相關處理,計算將產生各基線在該模型周期上的分段結果。最后,所有分段計算輸出結果輸入到結果綜合Reduce,進行綜合處理產生最終結果。

2.2 數據分割

對于MR-VLBI,數據分段可以采用積分周期、模型周期或FFT周期為劃分單元。積分周期是相關處理中進行積分運算的最小時間段,模型周期是對時延模型進行校正的最小時間間隔,FFT周期是進行FFT計算的數據長度。模型周期長度=模型周期時間×采樣頻率,而積分周期則包含積分周期時間/模型周期時間個模型周期。從提高并行度、降低通信開銷和實現負載均衡的角度考慮,MR-VLBI采用模型周期為數據分割單元。

VLBI相關處理以同一時刻各測站觀測數據為輸入,但是由于時延的存在,各站采集到的數據并沒有對齊到同一波前,使得各測站數據的各個模型周期并不是起始于文件中的同一位置,因而它不適合采用MapReduce中通常的按照數據長度連續分割的方法,需要自定義數據分割方法。

MR-VLBI數據分割需要在各站觀測數據文件中對齊同一模型周期的起始位置。一個模型周期對應的數據可由四元組表示,而這4個屬性是數據分割算法需要確定的。其中,ID是模型周期序號,按照1,2,…,N的順序遞增,通過其值可確定該模型周期的開始時刻;File是對應的數據文件對象;O是從文件中讀取數據的起始偏移位置;L是模型周期對應的數據長度,由運行參數決定。分割的核心在于確定各測站數據每個模型周期的偏移位置,所有臺站模型周期的偏移位置O可按下式計算得出

Ocurr=(δcurr-δlast)SB-Olast

Olast=Ocurr+L

(4)

式中:δcurr和δlast分別為當前和上一模型周期整數比特時延補償值;S為信號采樣頻率;B為比特量化位數;B和S都是設備觀測參數。

一路信號在某個模型周期的時延補償為

τ=α0+α1τ1+α2τ2+…

(5)

式中:αi(i=0,1,2,…,r)為數據處理前給定的時間延遲模型的多項式系數。可將τ分為整數比特部分τ1和小數比特部分τ2兩部分

τ=τ1+τ2

τ1=NT

τ2=τ-[τ1×S]/S

(6)

式中:T=1/S為采樣時間間隔;N表示整數。

根據式(5)和式(6)可計算出i和j兩路輸入信號的整數比特補償值τi1和τj1。按照補償信號路數的不同,時延補償可分為基線時延和地心時延兩類。基線時延只對兩路輸入信號中的一路進行補償,在計算偏移位置時,取δi=0和δj=τj1-τi1。地心時延對兩路信號都進行時延補償,令δi=τi1和δj=τj1。

在分割完成后,待處理數據將轉換成包含M×N個分片的集合{Sij|i∈M,j∈N},M為測站數量,N為模型周期數量。該集合中同一模型周期的數據分片形成鍵值對,它是相關計算Map過程的輸入,鍵j為模型周期的序號,值{Sij|i∈M}是第j個模型周期各測站數據集合。

2.3 相關計算Map

相關計算Map用于實現各臺站數據的相關處理,它按照條紋旋轉、FFT、小數比特補償和互譜累加積分的順序對輸入數據進行處理。

對信號進行條紋旋轉,就是用理論條紋相位θ(t)進行補償,即

u(t)=w(t)e-jθ(t)

θ(t)=2πfδ

(7)

式中:f為本振頻率。對于基線時延,在對第i路信號進行時延補償后,只需對另一路(第j路)信號使用整數比特補償時延δj進行條紋旋轉。對于地心時延模式,兩路信號均需進行條紋旋轉操作。

對輸入信號u(t)使用FFT將其從時域變換到頻域,得到頻譜表示為

(8)

實際運算中,FFT采用的是有限長度的離散數據。輸入信號ui(t)和uj(t)分別以FFT點數為一個單元進行FFT計算,FFT點數根據計算要求的頻率分辨率來確定。

由于信號是以數字信號記錄的,小數比特時延補償無法在時域內用類似整數比特數據移位的方法完成,其處理將在頻域內完成

V(f)=V0(f)ejfτ2

(9)

互譜累加積分操作將第i路信號每個數據單元的復數數據點與第j路信號相應的數據單元的共軛復數數據點按照下式兩兩對應相乘

(10)

在相關計算完成后,將輸出結果鍵值對。p為第j個模型周期對應的積分周期序號,Rjk為第k條基線第j個模型周期的處理結果。

2.4 結果綜合Reduce

結果綜合Reduce以一個積分周期的所有模型周期計算結果集合為輸入,其中Ip為第p個積分周期包含的模型周期,B表示所有相關臺站組成的基線集合。MapReduce運行框架將匯集具有相同積分周期序號的相關計算Map輸出結果,結果綜合模塊對這些輸入數據進行加工,產生時延、時延率、條紋和條紋率等結果。

3 性能測試

本文在hadoop 2.4.1基礎上開發了MR-VLBI程序,相關計算Map和結果綜合Reduce模塊采用C++實現,其余部分使用Java語言編寫。此外,本文還開發了串行及基于文獻[9]MPI+Pthreads方法的并行VLBI處理程序(根據該方法實現了并行執行邏輯,但是采用的數據處理算法與串行和MR-VLBI相同)。

本文實驗環境由10個Slave節點組成,每節點配置4路AMD Opteron 6212 @ 2.70 GHz CPU,64 GB內存,1 TB硬盤,單節點具有32核,總共320核。在此平臺上,當將數據復制參數設為2時,可提供5 TB的存儲空間。即使將該參數增大,例如設置為5(考慮到數據冗余和可靠性等因素,很少有實際系統將該參數設置大于5),也可提供2 TB的存儲空間。

在相同參數設置下,使用MR-VLBI、串行和MPI+Pthreads對同一觀測數據進行處理得到的結果完全相同。圖4給出了使用MR-VLBI處理嫦娥三號任務2013-12-04T09:00對標校射電源1226+023觀測數據的殘余時延結果,其方差為0.025。該數據由佳木斯—喀什基線組成,時長30 min,數據總大小26.8 GB。計算采用積分周期59.965 44 s,模型周期0.156 16 s。

圖4 殘余時延處理結果

圖5給出了在上述參數下串行程序、MR-VLBI和MPI+Pthreads方式的平均運行時間。其中,后兩者都使用了10個計算節點。相對于串行程序,MR-VLBI的效率有很大提升,其加速比達到了100.5。但是,與MPI+Pthreads方式相比,其計算效率有一定差距,運行時間為后者的1.25倍左右。通過分析日志,其效率較差的原因在于MR-VLBI的任務調度開銷較高。系統將所有Map任務調度完畢需要花費30 s左右,但是對那些較早調度運行的Map任務,其執行時間與MPI+Pthreads方式相差無幾。

圖5 串行、MPI+Pthreads和MR-VLBI運行時間對比

圖6給出了模型周期為0.156 16 s,采用不同數據復制策略和節點個數時MR-VLBI的運行時間。從該結果可以看出,MR-VLBI的性能隨著節點數的增多呈線性上升的趨勢,但是它對數據復制策略不敏感。

圖6 不同系統參數下MR-VLBI的運行時間對比

MR-VLBI采用模型周期作為并行計算單元,而MPI+Pthreads方式采用雙層并行結構,節點間采用積分周期,節點內部使用模型周期,這一差異使兩者具有不同的負載均衡能力。因為模型周期粒度較小,而且其數量通常較多,MR-VLBI能在全局計算資源上進行良好的負載均衡,但對MPI+Pthreads方式,當積分周期包含的模型周期數量少于節點CPU核數時,節點上的每個核并不能都分配到計算任務,會形成一定程度的閑置,使計算效率降低。

圖7和圖8分別示意了積分周期為59.965 44 s、模型周期取不同值時,MR-VLBI和MPI+Pthreads的運行時間和它們實際運行的并行任務數量。當模型周期較大時,例如7.495 68 s和3.747 84 s,MR-VLBI具有更快的運算速度,因為此時它具有更多的并發任務,但是隨著模型周期的逐漸減小,MPI+Pthreads的運行效率越來越高,此時其并行任務數量隨著積分周期包含模型周期個數的增加而增多,從而能更充分地利用CPU資源提高計算速度。

圖7 不同模型周期時MR-VLBI和MPI+Pthreads方式運行時間對比

圖8 不同模型周期時MR-VLBI和MPI+Pthreads方式的任務數量

4 結 論

VLBI相關處理具有數據密集和計算密集的雙重特征,對其進行高速處理是一個亟需解決的問題。本文基于云計算模型MapReduce提出和設計了一種稱為MR-VLBI的并行處理方法,雖然其運行效率相對于傳統并行處理方式并不是完全領先,例如在積分周期包含的模型周期數量多于節點CPU核數時的性能就要差一些,但是它具備邏輯簡單、實現容易、擴展性強和負載均衡能力強等傳統方式所缺乏的一系列優點,因而具有良好的應用前景。

目前,MapReduce實現技術有了新發展,出現了例如Spark等具有更高性能的框架,未來將它們應用到MR-VLBI中,會進一步提高和改善系統的運行效率。

[1]韓松濤, 唐歌實, 劉成軍, 等.VLBI并行處理方式比較分析 [J].遙測遙控, 2013, 34(1):29-33.HAN Songtao, TANG Geshi, LIU Chengjun, et al.Analysis on parallel processing of VLBI [J].Journal of Telemetry, Tracking, and Command, 2013, 34(1):29-33.

[2]DELLER A, TINGAY S J, BAILES M, et al.DiFX:a software correlator for very long baseline interferometry using multiprocessor computing environments [J].Publications of the Astronomical Society of the Pacific, 2007, 119(853):318-336.

[3]LOWE S T.Softc:an operational software corelator [C]∥Proceedings of the International VLBI Service for Geodesy and Astrometry 2004 General Meeting.Washington, DC, USA:NASA, 2004:191-194.

[4]MACHIDA M, ISHIMOTO M, TAKASHIMA K, et al.K5/VSSP data processing system of small cluster computing at Tsukuba VLBI correlator, NASA/CP-2006-214140 [C]∥ Proceedings of the IVS 2006 General Meeting.Washington, DC, USA:NASA, 2006:117-126.

[5]ZHENG Weimin, ZHANG Dong.Parallel algorithm of VLBI software correlator under multiprocessor environment [C]∥Proceedings of the SPIE 15th International Symposium on Multispectral Image Processing and Pattern Recognition.Bellingham, WA, USA:SPIE, 2007:15-22.

[6]李元飛, 鄭為民.VLBI數據軟件相關處理方法研究 [J].中國科學院上海天文臺年刊, 2004, 25:150-158.LI Yuanfei, ZHENG Weimin.VLBI very long baseline interferometry data simulation algorithms study [J].Annals of Shanghai Observatory Academia Sinica, 2004, 25:150-158.

[7]錢志瀚, 李金嶺.甚長基線干涉測量技術在深空探測中的應用 [M].北京:中國科學技術出版社, 2012:46-48.

[8]DEAN J, GHEMAWAT S.MapReduce:simplified data processing on large clusters [C]∥Proceedings of the 6th Symposium on Operating Systems Design and Implementation.Berkeley, CA, USA:USENIX, 2004:137-150.

[9]張冬.集群環境下的VLBI軟件相關處理方法研究 [D].上海:中國科學院上海天文臺, 2007.

[本刊相關文獻鏈接]

崔繼岳,梅魁志,劉冬冬.面向OpenCL的Mali GPU仿真器構建研究.2015,49(2):20-24.[doi:10.7652/xjtuxb201502 004]

袁通,劉志鏡,劉慧,等.多核處理器中基于MapReduce的哈希劃分優化.2014,48(11):97-102.[doi:10.7652/xjtuxb2014 11017]

張虹,鄭霄,趙丹.GPU加速竇房結計算機仿真的實現及優化.2014,48(7):60-64.[doi:10.7652/xjtuxb201407011]

史椸,耿晨,齊勇.一種具有容錯機制的MapReduce模型研究與實現.2014,48(2):1-7.[doi:10.7652/xjtuxb201402001]

熊金波,姚志強,馬建峰,等.云計算環境中的組合文檔模型及其訪問控制方案.2014,48(2):25-31.[doi:10.7652/xjtuxb201402005]

田樂,陳庶樵,黃慧群,等.利用域轉換的三態內容尋址存儲器報文分類算法.2013,47(10):97-102.[doi:10.7652/xjtuxb201310017]

鮑軍鵬,宋楠,陶斌.依賴知識的服務組合算法.2013,47(8):1-6.[doi:10.7652/xjtuxb201308001]

張保,董小社,白秀秀,等.CPU-GPU系統中基于剖分的全局性能優化方法.2012,46(2):17-23.[doi:10.7652/xjtuxb 201202004]

唐軼軒,吳俊敏,陳國良,等.并行片上網絡仿真器ParaNSim的設計及性能分析.2012,46(2):24-30.[doi:10.7652/xjtuxb201202005]

張保,曹海軍,董小社,等.面向圖形處理器重疊通信與計算的數據劃分方法.2011,45(4):1-4.[doi:10.7652/xjtuxb 201104001]

劉洋,趙慧,尹興良,等.線性檢測中的最優空時編碼設計與分析.2011,45(2):59-63.[doi:10.7652/xjtuxb201102012]

韋遠科,趙銀亮,宋少龍,等.面向片上多核處理器的推測多線程機制下的獨立棧模型.2010,44(12):10-15.[doi:10.7652/xjtuxb201012003]

李遠成,趙銀亮,陰培培,等.一種應用代價評估的推測多線程路徑預測方法.2010,44(12):22-27.[doi:10.7652/xjtuxb 201012005]

(編輯 武紅江)

A Parallel Processing Approach of Very Long Baseline Interferometry Using MapReduce

TIAN Bin1,2,HE Qiang2,WANG Jia2,ZHENG Yuxi2

(1.School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China; 2.Xi’an Satellite Control Center, Xi’an 710043, China)

A VLBI parallel processing approach based on MapReduce is proposed to solve such problems in traditional VLBI parallel processing patterns as logic complexity, poor data storage and computing scalability.Model periods are used as primary data processing units, and a related data splitting method is constructed to align each model period’s data of every station.A data correlation mapping is designed and the final correlation results are obtained by using Reduce to synthesize each model period’s processing result.Experimental results show that the efficiency of the new approach is about 25% lower than traditional ways when the number of model periods in an integration period is larger than CPU cores, but it provides better performance when the number of model periods in an integration period is less than CPU cores.Also the approach reduces the complexity of VBLI parallel processing and provides good data storage and computing scalability.

very long baseline interferometry; data correlation; parallel processing; MapReduce

2014-09-13。 作者簡介:田斌(1971—),男,在職碩士生,西安衛星測控中心研究員。

時間:2015-03-04

http:∥www.cnki.net/kcms/detail/61.1069.T.20150304.1653.003.html

10.7652/xjtuxb201504010

TP311

A

0253-987X(2015)04-0061-06