大規模聯合平差中的方差分量估計并行設計

李 慶，劉 增

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

1 引言

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

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

2 方差分量估計原理

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

②平差求出第一次參數估值和殘差；

3 并行設計相關

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

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

圖1 串行、并行比較

4 聯合平差中的方差分量估計并行設計

①聯合平差的觀測量被分成了k類，我們把這k類相互獨立的觀測量的初始信息保存在k個不同的文件中，包括每一類觀測量的系數矩陣Ai、含有坐標近似值的自由項矩陣li、由單獨平差或經驗公式得到的初始權矩陣Pi以及該類觀測量的觀測總數mi。基于并行處理的思想，劃分k個任務，并行讀取每類觀測量的初始信息，并計算法方程系數矩陣Ni=和法向量Ui=

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

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

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