大規(guī)模聯(lián)合平差中的方差分量估計并行設計

李 慶，劉 增

（信息工程大學，鄭州 450001）

1 引言

在大規(guī)模GNSS觀測網(wǎng)進行獨立網(wǎng)平差及與其它觀測網(wǎng)進行聯(lián)合平差的過程中，一般根據(jù)測量條件的不同將整網(wǎng)分成若干子網(wǎng)，各子網(wǎng)先進行單獨平差消除子網(wǎng)內(nèi)部以及子網(wǎng)之間的粗差［1，2］，而后是子網(wǎng)間的系統(tǒng)性差異。系統(tǒng)性差異體現(xiàn)在函數(shù)特性和隨機特性兩個方面，消除隨機特性的系統(tǒng)性差異通常采用方差分量估計的方法。方差分量估計需要大量法方程系數(shù)矩陣求逆和矩陣相乘計算，傳統(tǒng)聯(lián)合平差中的方差分量估計效率將會非常低。為提高傳統(tǒng)網(wǎng)平差解算效率，對于高性能計算技術的研究成了近幾年的熱點，由于高性能計算技術的本質(zhì)是并行計算，將傳統(tǒng)的GNSS數(shù)據(jù)處理模型分解并設計合理的并行算法是實現(xiàn)GNSS數(shù)據(jù)快速處理的首要問題［3］。

本文基于方差分量估計原理和以任務劃分為基本模式的并行算法，結合已有的大型矩陣高效計算方法，設計了大型聯(lián)合平差中的并行方差分量估計的基本流程，理論上提高了硬件資源的利用率和參數(shù)估計效率。

2 方差分量估計原理

平差的數(shù)學模型包括函數(shù)模型和隨機模型，函數(shù)模型是描述平差問題中觀測量與觀測量之間、觀測量與未知參數(shù)之間相互關系的函數(shù)表達式，隨機模型是描述觀測誤差的一些隨機特征，在平差中主要指觀測值的數(shù)學期望和方差［4］。雖然觀測值的權可以由一些經(jīng)驗公式確定，但往往不具備普適性，所以常采用對隨機模型進行驗后估計的方法。隨機模型的驗后估計，其基本思想是先對各類觀測量定初權、進行預平差、利用預平差后得到的信息、主要是各類觀測值的改正數(shù)V，依據(jù)一定的原則對各類觀測值的驗前方差和協(xié)方差作出估計，依此定權［5］。方差分量估計是利用驗后方差重新定權的，最常用的是Helmert方差分量估計法。對于k類觀測量相互獨立的情況，有嚴密公式得到相應的方差分量估值［1］：

②平差求出第一次參數(shù)估值和殘差；

3 并行設計相關

設計并行的第一步就是將問題分解成多個任務。一個任務是一個指令序列，并且作為一個小組一起操作，這個小組相當于一個算法或者程序的某個邏輯部分［6］。即任務的劃分體現(xiàn)了算法設計者對問題的思考。但是任務和執(zhí)行線程絕不是一對一的關系。如對于k類觀測量的k個系數(shù)矩陣Ai、自由項矩陣li、權矩陣Pi分別建立的法方程法矩陣Ni=和法向量Ui=A將每一個建立過程視為一個任務執(zhí)行，并不會需要k個線程同時運行。因為每類觀測量的觀測個數(shù)各不相同，相應所需的任務時間花費也不相同?，F(xiàn)階段基于任務的編程方法考慮的主要是任務調(diào)度中負載平衡的問題。負載平衡（Loadbalance），即指有效地在各處理單元間分配任務，當一個設計能夠平衡處理單元間的計算負載時，它的執(zhí)行效率要高于處理單元間計算負載不平衡的情況［6］。獲得一個最佳動態(tài)調(diào)度可以采取工作竊取 （work stealing）的策略，在任務執(zhí)行開始時，把任務分布到各個線程上，每一個線程有自己的工作隊列。當工作隊列為空時，線程將隨機從其它線程的任務隊列中竊取工作，如圖1所示。

圖1中，6個待執(zhí)行的任務通過4個線程并行執(zhí)行完成。若串行運行任務，完成的總時間等于6個任務分別執(zhí)行的時間之和，而采取并行執(zhí)行的方式，完成的總時間僅為任務E執(zhí)行的時間，大大提高了任務執(zhí)行效率。任務調(diào)度器會自動根據(jù)所有可用的邏輯內(nèi)核嘗試對任務進行負載均衡，在幕后使用工作竊取隊列找到一個最合適的線程，并將任務加入隊列中［3］，避免出現(xiàn)部分線程執(zhí)行大多數(shù)任務而其它線程處于閑置狀態(tài)的情況。

圖1 串行、并行比較

4 聯(lián)合平差中的方差分量估計并行設計

①聯(lián)合平差的觀測量被分成了k類，我們把這k類相互獨立的觀測量的初始信息保存在k個不同的文件中，包括每一類觀測量的系數(shù)矩陣Ai、含有坐標近似值的自由項矩陣li、由單獨平差或經(jīng)驗公式得到的初始權矩陣Pi以及該類觀測量的觀測總數(shù)mi?；诓⑿刑幚淼乃枷耄瑒澐謐個任務，并行讀取每類觀測量的初始信息，并計算法方程系數(shù)矩陣Ni=和法向量Ui=

②對各個任務組的法方程系數(shù)矩陣Ni和法向量Ui進行總法方程的并行累加計算，得到聯(lián)合平差的總法方程系數(shù)矩陣N和法向量U。

③第三步的計算有兩種方案。方案一：劃分k個任務，利用緩存的各類觀測量的法方程信息，并行組成法方程，解算參數(shù)和需要的殘差向量Vi；方案二：直接利用第二步得到的總法方程系數(shù)矩陣和法向量結果，組成法方程，解算總的殘差向量V，其分量即為所需要的各類觀測量的殘差向量。兩種方案在解算法方程時，都涉及大型矩陣的相乘和求逆，可以采用文獻［7］研究的并行矩陣分塊乘法和法方程系數(shù)矩陣的Cholesky分塊分解并行求逆方法，不僅可降低存儲對內(nèi)存的要求，也有效提高了計算效率。

⑤按方差分量估計解算方差估值分量的公式分別在k個任務里組成方程，利用這k個任務返回的結果并行解算方程組。由于觀測量分類個數(shù)k不會太大，故解這k個方程對整體解算效率影響不大。