王建偉 程傳錄 趙 輝 馮在梅 劉曉云 田 婕 馬潤霞

1 自然資源部大地測量數(shù)據(jù)處理中心，西安市友誼東路334號，710054 2 自然資源部第一航測遙感院，西安市友誼東路334號，710054

大規(guī)模GNSS網(wǎng)作為實現(xiàn)高精度位置服務(wù)的重要基礎(chǔ)設(shè)施，在國家和地區(qū)坐標(biāo)參考框架建立與維持、實時定位、災(zāi)害防御、板塊運動分析等多個領(lǐng)域得到廣泛應(yīng)用。參考站數(shù)量的不斷增加使得大規(guī)模GNSS網(wǎng)運算量劇增，傳統(tǒng)串行解算方式時效性較差，難以滿足當(dāng)前需要。由于GNSS數(shù)據(jù)處理技術(shù)難度高、專業(yè)性強、軟件開發(fā)周期長，因此利用并行計算技術(shù)對已有的通用高精度GNSS軟件進(jìn)行并行化改造成為一種高效化、實用化的選擇。

目前，國內(nèi)學(xué)者在大規(guī)模GNSS網(wǎng)快速解算方面已取得一些研究成果[1-5]。在云計算方面，李林陽[6]針對未來云化和微服務(wù)等應(yīng)用場景，采用云計算技術(shù)對大規(guī)模全球GNSS網(wǎng)數(shù)據(jù)進(jìn)行高效處理。在多節(jié)點分布式計算方面，陳正生等[7]利用Bernese軟件分布式處理引擎BPE及已有的并行計算函數(shù)庫等，實現(xiàn)大規(guī)模GNSS網(wǎng)數(shù)據(jù)的快速處理；白帆等[8]分別利用Spark大數(shù)據(jù)集群和Hadoop平臺技術(shù)，基于GAMIT軟件實現(xiàn)大規(guī)模GNSS網(wǎng)子網(wǎng)級分布式處理。在單節(jié)點并行計算方面，崔陽等[9]基于共享內(nèi)存多核系統(tǒng)優(yōu)勢，從數(shù)據(jù)并行和任務(wù)并行兩方面實現(xiàn)大規(guī)模GNSS網(wǎng)抗差估計的并行化，從而提高解算的時效性。

相較于共享內(nèi)存模型，分布式內(nèi)存模型具有各節(jié)點數(shù)據(jù)傳輸高延遲、進(jìn)程通信開銷大等缺點，使得上述基于GAMIT軟件的子網(wǎng)級粗粒度并行解算時效性的提升十分有限。目前，GAMIT軟件官方尚未提供并行處理引擎，針對該軟件的并行化研究進(jìn)展相對遲緩。因此，本文基于GAMIT/GLOBK軟件及共享內(nèi)存模型，從時間和空間兩個維度研究大規(guī)模GNSS網(wǎng)基線的并行解算方法。

1 概 述

1.1 并行

根據(jù)費林分類法，計算機(jī)體系結(jié)構(gòu)共有4種類型，即單指令流單數(shù)據(jù)流(SISD)、單指令流多數(shù)據(jù)流(SIMD)、多指令流單數(shù)據(jù)流(MISD)和多指令流多數(shù)據(jù)流(MIMD)。上述4種類型分別對應(yīng)串行、數(shù)據(jù)并行、任務(wù)并行、任務(wù)和數(shù)據(jù)并行(圖1)。

圖1 費林分類法Fig.1 Flynn’s Taxonomy

并行計算是時間資源最大化的一種嘗試，具體可通過多線程(multi-thread)或多進(jìn)程(multi-process)方式來實現(xiàn)。利用進(jìn)程池(process pool)技術(shù)來優(yōu)化和管理進(jìn)程活動，可實現(xiàn)進(jìn)程的重用以減少創(chuàng)建進(jìn)程的額外開銷，從而提高并行系統(tǒng)的性能。

1.2 并行計算模型

并行計算模型是硬件和內(nèi)存體系結(jié)構(gòu)的一個抽象。根據(jù)阿姆達(dá)爾定律，針對一個并行計算問題，假設(shè)程序串行部分所占百分比為α，則n個處理器的加速比S(n)為：

(1)

從式(1)可以看出，加速比S(n)與處理器個數(shù)n呈正相關(guān)，即加速比會隨處理器個數(shù)的增加而增大，但最大值不會超過1/α。由古斯塔夫森定律可知：

S(n)=n-α(n-1)

(2)

古斯塔夫森定律表明，對于一個并行計算問題，首先設(shè)置并行解決一個問題所允許的時間，再根據(jù)時間來確定問題的規(guī)模。

目前使用最廣泛的并行計算模型主要包括共享內(nèi)存、分布式內(nèi)存/消息傳遞、大規(guī)模并行處理(massively parallel processing，MPP)、工作站集群等。不同于分布式內(nèi)存，共享內(nèi)存具有虛擬內(nèi)存數(shù)量較多、所有處理器可以同等地訪問該內(nèi)存中的數(shù)據(jù)和指令、不存在消息交換、無需花費較長時間來進(jìn)行消息傳遞等優(yōu)點，因此該模型下的并行計算加速比及資源利用率最高。

2 大規(guī)模GNSS網(wǎng)并行解算設(shè)計

本文基于共享內(nèi)存體系結(jié)構(gòu)和GAMIT/GLOBK軟件，首先利用進(jìn)程池技術(shù)分別設(shè)計大規(guī)模GNSS網(wǎng)在時間(多時段)和空間(多子網(wǎng))兩個維度下的數(shù)據(jù)并行(SIMD)算法，然后將二者融合，設(shè)計時空一體化的雙層并行解算策略。并行算法設(shè)計的核心是任務(wù)的等價分解與解算結(jié)果的有機(jī)組合，具體包括任務(wù)分解、任務(wù)分配、映射和組合4個步驟。

2.1 GAMIT/GLOBK數(shù)據(jù)處理

GAMIT由多個功能不同的模塊組成，主要包括數(shù)據(jù)準(zhǔn)備和數(shù)據(jù)處理2大部分。數(shù)據(jù)處理部分包括生成參考軌道(ARC)、計算殘差和偏導(dǎo)數(shù)(MODEL)、周跳探測與修復(fù)(AUTCLN)、最小二乘平差(SOLVE)等模塊。這些模塊既可以獨立運行，也可以通過批處理命令聯(lián)合在一起運行，共同完成高精度GNSS數(shù)據(jù)處理和分析全過程。GAMIT軟件一次只能解算一個時段的同步觀測站數(shù)據(jù)，單時段基線解算流程如圖2所示。GLOBK是一個卡爾曼濾波器，可以對GAMIT的基線結(jié)果進(jìn)行網(wǎng)平差處理。GLOBK主要由globk、glred和glorg三種模塊組成，分別用于時間域和空間域的數(shù)據(jù)合并、重復(fù)性分析、求解最佳坐標(biāo)等操作，GLOBK平差流程如圖3所示。GAMIT/GLOBK按照特定的項目目錄結(jié)構(gòu)進(jìn)行數(shù)據(jù)處理。

圖2 GAMIT基線解算流程Fig.2 Flowchart of GAMIT baseline solution

圖3 GLOBK網(wǎng)平差流程Fig.3 Flowchart of GLOBK adjustment

2.2 多時段并行解算設(shè)計

GAMIT/GLOBK軟件以時段為基本計算單元，先依次進(jìn)行基線解算，再將GAMIT基線解算結(jié)果h文件作為GLOBK的輸入文件進(jìn)行平差處理。將一個大規(guī)模GNSS網(wǎng)多時段串行解算任務(wù)分解為多個單時段并行的子任務(wù)同時進(jìn)行解算，從而大幅提高基線解算效率。在并行計算過程中，所有子任務(wù)通過共享內(nèi)存來訪問公共數(shù)據(jù)(如tables文件)，通過進(jìn)程池加鎖機(jī)制來確保數(shù)據(jù)的安全性。待所有基線解算的子任務(wù)完成后，關(guān)閉主進(jìn)程鎖，統(tǒng)一進(jìn)行GLOBK網(wǎng)平差。

設(shè)計算機(jī)核心數(shù)為C，大規(guī)模GNSS網(wǎng)時段數(shù)為N，進(jìn)程池大小為P(最佳進(jìn)程數(shù))，則有：

(3)

2.3 多子網(wǎng)并行解算設(shè)計

GAMIT/GLOBK軟件是基于全基線網(wǎng)解的雙差模型。雙差網(wǎng)解法的計算時間會隨站點數(shù)量的增加呈幾何級數(shù)增大(n3)，普通計算機(jī)往往受限于性能瓶頸，難以在短時間內(nèi)完成大量基線解算任務(wù)。因此，基于雙差網(wǎng)解模型處理大規(guī)模GNSS網(wǎng)時，國際上比較通用的做法是首先進(jìn)行分區(qū)、分子網(wǎng)計算，然后進(jìn)行綜合處理。子網(wǎng)劃分時，選取較為穩(wěn)定的一定數(shù)量站點作為子網(wǎng)公共基準(zhǔn)點，以保證各子網(wǎng)間解算結(jié)果的連續(xù)性。后續(xù)處理流程與多時段并行解算設(shè)計類似，在此不作贅述。

同樣，設(shè)計算機(jī)核心數(shù)為C，大規(guī)模GNSS網(wǎng)劃分的子網(wǎng)數(shù)為M，進(jìn)程池大小為P(最佳進(jìn)程數(shù))，則有：

(4)

2.4 時空一體化雙層并行解算

融合多時段與多子網(wǎng)并行2種算法，構(gòu)建基于共享內(nèi)存模型的時空一體化雙層并行算法，實現(xiàn)大規(guī)模GNSS網(wǎng)同時在時間域(時段)和空間域(子網(wǎng))兩個維度上的并行化處理，使得數(shù)據(jù)處理任務(wù)完成前，任意時刻計算機(jī)所有CPU核心均被充分利用，大幅提升基線解算的時效性及CPU利用率。

設(shè)計算機(jī)邏輯核數(shù)為C，任務(wù)總數(shù)為N，最佳進(jìn)程數(shù)為P，則有以下2種可能性。

1)不指定并行度。若本地計算機(jī)專門進(jìn)行大規(guī)模GNSS網(wǎng)數(shù)據(jù)處理，為了最大限度地挖掘該計算機(jī)的算力、提高計算機(jī)的利用率，此時設(shè)計的最佳進(jìn)程數(shù)P的計算公式同式(3)、(4)。

2)指定并行度S。由于本地計算機(jī)可能會處理大規(guī)模GNSS網(wǎng)數(shù)據(jù)工作外的其他任務(wù)，為了兼顧二者各自算力的需要，此時設(shè)計的最佳進(jìn)程數(shù)P的計算公式為：

(5)

時空一體化雙層并行解算設(shè)計架構(gòu)如圖4所示。

圖4 時空一體化雙層并行解算設(shè)計架構(gòu)Fig.4 The designed architecture of spatio-temporal integration two-layer parallel solution

3 算例分析

3.1 加速比與效率測試

1)測試數(shù)據(jù)。本文收集區(qū)域內(nèi)821個基準(zhǔn)站(含IGS站)2021年doy60～90的觀測數(shù)據(jù)，并將GNSS網(wǎng)劃分為20個子網(wǎng)，編號為NT01～20，共組成620個時段的基線解算任務(wù)。

2)分析對比指標(biāo)。本文擬采用加速比Sp和效率Ep分析對比指標(biāo)。Sp可反映并行系統(tǒng)或并行程序的時效性和加速效果，Ep可用來衡量并行系統(tǒng)設(shè)備的利用率，即單位處理器的加速效果：

(6)

(7)

式中，T1為任務(wù)在單處理器下的運行時間，Tp為任務(wù)在p個處理器并行系統(tǒng)中的運行時間。

3)測試硬件情況?；贕AMIT/GLOBK軟件，利用時空一體化雙層并行算法對該大規(guī)模GNSS網(wǎng)進(jìn)行數(shù)據(jù)處理時效性測試。測試使用的工作站硬件配置見表1。

表1 工作站硬件配置

3.2 結(jié)果分析

對測試結(jié)果進(jìn)行正確性檢驗及統(tǒng)計分析。經(jīng)測試，并行解算結(jié)果與傳統(tǒng)串行模式結(jié)果一致。分別計算每個并行度(即進(jìn)程數(shù))下對應(yīng)的加速比Sp、效率Ep、單時段等價串行平均用時以及單時段實際平均用時(表2、圖5～7)。其中，單時段等價串行平均用時為每個并行度下實際總用時與總時段數(shù)的比值，單時段實際平均用時為每個并行度下所有時段實際總用時的平均值與總時段數(shù)的比值。每個并行度下各項指標(biāo)分別獨立測試3次，最終取3次測試結(jié)果的平均值。

表2 不同并行度測試結(jié)果

圖5 不同并行度總用時Fig.5 The total time of different parallelisms

圖6 不同并行度Sp與EpFig.6 The Sp and Ep of different parallelisms

圖7 單時段等價串行與單時段實際平均用時Fig.7 The equivalent serial average time and actual average time of single period

由表2和圖5可知，時空一體化雙層并行算法可大幅提升大規(guī)模GNSS網(wǎng)基線解算的時效性，基線解算總用時可從傳統(tǒng)單進(jìn)程(即單窗口)模式的28.56 d最大縮短至1～2 d。隨著并行度的不斷增加，基線解算總用時大幅減小，并最終趨于一個相對平穩(wěn)的數(shù)值。其中，當(dāng)并行度為24時，基線解算總用時達(dá)到拐點(即總用時變化率轉(zhuǎn)折點)1.60 d，當(dāng)并行度超過24后，總用時減少量不明顯；當(dāng)并行度達(dá)到測試工作站邏輯核數(shù)48時，基線解算總用時達(dá)到最小值1.47 d。由圖6可知，基于時空一體化雙層并行算法的加速比Sp與并行度總體呈正相關(guān)，當(dāng)并行度為1～24時，Sp呈線性增加，加速效果十分顯著；當(dāng)并行度為24時，Sp達(dá)到拐點(即加速比增長率轉(zhuǎn)折點)17.89，之后加速效果不再明顯；當(dāng)并行度為48時，Sp達(dá)到最大值19.39，充分驗證了時空一體化并行算法的高時效性和先進(jìn)性。

結(jié)合圖6和圖7可知，基于時空一體化雙層并行算法的效率Ep與并行度呈負(fù)相關(guān)，即單位處理器的加速效果會隨并行度的增加而減小。這是因為在共享內(nèi)存模型下，隨著并行度增大，創(chuàng)建進(jìn)程的系統(tǒng)開銷，如內(nèi)存分配、I/O操作、任務(wù)調(diào)度等也隨之增加，在一定程度上會抑制并行計算帶來的性能優(yōu)勢，導(dǎo)致單位處理器整體利用率相對變小，從而使得大規(guī)模GNSS網(wǎng)單個時段的用時不斷增加。由此可見，并行度并非越大越好，需同時考慮Sp與Ep兩個因素。由于并行計算的拐點可兼顧Sp與Ep，因此在實際應(yīng)用中宜選擇拐點值作為時空一體化雙層并行算法的最佳進(jìn)程數(shù)，這樣既能大幅提高基線解算的時效性，又能充分提升系統(tǒng)設(shè)備的利用率。

4 結(jié) 語

1)時空一體化雙層并行算法可大幅提升大規(guī)模GNSS網(wǎng)的基線解算效率。在測試環(huán)境下，時空一體化雙層并行算法的最大加速比高達(dá)19.39，相較于傳統(tǒng)串行處理模式，其基線解算周期從28.56 d最大縮短至1～2 d，進(jìn)一步驗證了該并行算法的優(yōu)越性和高時效性。

2)在并行系統(tǒng)算法設(shè)計時，應(yīng)合理兼顧加速比與效率目標(biāo)，并行系統(tǒng)的拐點可作為并行度設(shè)計的一項重要參考指標(biāo)。

將本文研究成果作為算子部署在大數(shù)據(jù)環(huán)境中，利用云計算資源按需擴(kuò)充、彈性配置、快速部署等優(yōu)勢，能更好地發(fā)揮其超算能力，優(yōu)化資源配置，降低投入成本。本文設(shè)計的時空一體化雙層并行算法主要針對大規(guī)模GNSS網(wǎng)在單節(jié)點多核環(huán)境下的基線解算場景，為充分發(fā)揮多節(jié)點集群協(xié)同作業(yè)的算力優(yōu)勢，基于分布式系統(tǒng)的多節(jié)點多核并行算法將成為下一步的研究重點。