大規模GNSS網多進程并行解算研究

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

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

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

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

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

1 概 述

1.1 并行

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

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

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

1.2 并行計算模型

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

(1)

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

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

(2)

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

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

2 大規模GNSS網并行解算設計

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

2.1 GAMIT/GLOBK數據處理

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

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

圖3 GLOBK網平差流程Fig.3 Flowchart of GLOBK adjustment

2.2 多時段并行解算設計

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

設計算機核心數為C，大規模GNSS網時段數為N，進程池大小為P(最佳進程數)，則有：

(3)

2.3 多子網并行解算設計

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

同樣，設計算機核心數為C，大規模GNSS網劃分的子網數為M，進程池大小為P(最佳進程數)，則有：

(4)

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

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

設計算機邏輯核數為C，任務總數為N，最佳進程數為P，則有以下2種可能性。

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

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

(5)

時空一體化雙層并行解算設計架構如圖4所示。

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

3 算例分析

3.1 加速比與效率測試

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

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

(6)

(7)

式中，T1為任務在單處理器下的運行時間，Tp為任務在p個處理器并行系統中的運行時間。

3)測試硬件情況。基于GAMIT/GLOBK軟件，利用時空一體化雙層并行算法對該大規模GNSS網進行數據處理時效性測試。測試使用的工作站硬件配置見表1。

表1 工作站硬件配置

3.2 結果分析

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

表2 不同并行度測試結果

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

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

4 結 語

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

2)在并行系統算法設計時，應合理兼顧加速比與效率目標，并行系統的拐點可作為并行度設計的一項重要參考指標。

將本文研究成果作為算子部署在大數據環境中，利用云計算資源按需擴充、彈性配置、快速部署等優勢，能更好地發揮其超算能力，優化資源配置，降低投入成本。本文設計的時空一體化雙層并行算法主要針對大規模GNSS網在單節點多核環境下的基線解算場景，為充分發揮多節點集群協同作業的算力優勢，基于分布式系統的多節點多核并行算法將成為下一步的研究重點。