李 慶，劉 增

（信息工程大學(xué)，鄭州 450001）

1 引言

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

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

2 方差分量估計(jì)原理

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

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

3 并行設(shè)計(jì)相關(guān)

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

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

圖1 串行、并行比較

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

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

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

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

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