馮凌璇，林寶軍，，5，劉迎春，林 夏

（1.中國科學(xué)院空天信息創(chuàng)新研究院，北京 100094；2.中國科學(xué)院大學(xué)，北京 100049；3.中國科學(xué)院微小衛(wèi)星創(chuàng)新研究院，上海 201210；4.上海微小衛(wèi)星工程中心，上海 201210；5.上海科技大學(xué)，上海 201210）

隨著北斗三號全球?qū)Ш较到y(tǒng)的建成開通，北斗為全球提供高質(zhì)量的定位和授時功能。而導(dǎo)航衛(wèi)星的自主定軌能力直接影響系統(tǒng)的服務(wù)性能[1]。傳統(tǒng)的集中式定軌算法復(fù)雜度高，不適用于實時的應(yīng)用場景[2-3]。盡管分布式算法實時性好，但精度很難提高并且存在濾波發(fā)散的問題[4]。如何將集中式定軌算法應(yīng)用到衛(wèi)星上，國內(nèi)有許多討論[5-8]。但這些方法要么在精度上有所損失，要么受到星載計算機(jī)計算能力的限制。

由于單臺星載計算機(jī)性能有限[9]，利用集群并行化的方法是實現(xiàn)星上復(fù)雜軟件的一種可行方案。自主定軌算法這類科學(xué)應(yīng)用通常具有較優(yōu)的靜態(tài)劃分算法[10]。因此，該文提出一種集中式自主定軌算法的并行方案，在保證精度的同時有效減少單臺星載計算機(jī)的運算資源的消耗。

1 集中式自主定軌算法并行優(yōu)化方案

1.1 并行系統(tǒng)架構(gòu)

中科院北斗三號衛(wèi)星載有多臺星載計算機(jī)，分工處理星上各類應(yīng)用，星載計算機(jī)之間采用1553B總線通信。星載計算機(jī)集群的架構(gòu)如圖1 所示，屬于總線式集群，多個計算節(jié)點通過1553B 總線相連。

圖1 系統(tǒng)架構(gòu)

1553B 是一種在航空航天領(lǐng)域應(yīng)用廣泛的中央集權(quán)式總線協(xié)議[11]，總線的設(shè)計傳輸速率為1 Mb/s，總線上設(shè)備分為總線控制器（BC）、遠(yuǎn)程終端（RT）以及總線監(jiān)視器（BM）。星載計算機(jī)集群上的計算節(jié)點作為RT 掛載在總線上。

1.2 并行編程模型

并行編程模型是一組程序的抽象，它將應(yīng)用程序的并行行為配適到底層并行硬件[12]。在高性能計算機(jī)集群時代，MPI 一直是高性能計算領(lǐng)域中的一種標(biāo)準(zhǔn)實現(xiàn)方案[13]，但MPI 是為大規(guī)模具有高性能計算機(jī)的集群而設(shè)計的[14]，這些計算機(jī)通常擁有比星載計算機(jī)更加強(qiáng)大的處理器、更大的內(nèi)存空間以及更加靈活的網(wǎng)絡(luò)連接方式。因此，直接將MPI 遷移到現(xiàn)有的星載計算機(jī)集群上將會面臨巨大的挑戰(zhàn)。

針對現(xiàn)有1553B 連接的總線式星載計算機(jī)集群，該文基于MPI 原理設(shè)計了一種可以用于星上計算機(jī)集群的總線式消息傳遞式的并行編程模型——sMPI，可以實現(xiàn)多臺星載計算機(jī)之間的協(xié)同處理計算。該并行編程模型在星載計算機(jī)上實現(xiàn)了MPI 模型的大部分庫函數(shù)功能，向上層應(yīng)用提供通用的標(biāo)準(zhǔn)MPI 編程接口，支持C 語言的開發(fā)，便于開發(fā)者直接將地面程序移植到星載計算機(jī)上。

在1553B 總線協(xié)議中，總線采用命令響應(yīng)方式實現(xiàn)系統(tǒng)通信[15]。命令字只能由BC 發(fā)出，而作為并行任務(wù)進(jìn)程執(zhí)行者的RT 沒有發(fā)送數(shù)據(jù)的主動權(quán)。這樣的總線結(jié)構(gòu)極大限制了任務(wù)進(jìn)程的靈活性。sMPI 通過合理設(shè)計數(shù)據(jù)幀格式實現(xiàn)了在BC 控制下的計算節(jié)點RT 之間的通信。BC 通過對總線上所有的RT 進(jìn)行輪詢實現(xiàn)消息的轉(zhuǎn)發(fā)。但是，若輪詢的周期過長，數(shù)據(jù)的發(fā)送則不能充分利用總線帶寬，總線吞吐率低；若輪詢周期過短，那么頻繁的總線中斷會影響單個節(jié)點的性能?？紤]到并行程序的數(shù)據(jù)交互具有很高的時間局部性，一旦發(fā)生數(shù)據(jù)交互，則很大可能伴隨著大量的數(shù)據(jù)交互。sMPI 通過式（1）來控制BC 的輪詢周期時間。當(dāng)有數(shù)據(jù)交互時就快速提高輪詢頻率，數(shù)據(jù)交互結(jié)束則緩慢降低輪詢頻率，在提高數(shù)據(jù)交互吞吐率的同時又避免了頻繁的中斷。

在實現(xiàn)過程中，輪詢周期時長的最小單位為1553B 總線的周期T1553，即Tmin，Tmax可取100 個總線周期時間。初始時，T0取Tmax。若上一輪詢周期不存在數(shù)據(jù)交換，下一輪詢周期Tn+1則在原Tn的基礎(chǔ)上加5T1553；若存在數(shù)據(jù)交換，Tn+1則取Tn的一半并取整。

1.3 并行算法描述

并行化前的串行集中式自主定軌使用推廣卡爾曼濾波算法，算法流程如圖2 所示，算法初始化后首先接收星間鏈路測距值，然后對整網(wǎng)衛(wèi)星根據(jù)動力學(xué)模型進(jìn)行軌道鐘差信息的預(yù)報，接著根據(jù)采集的測距值導(dǎo)出觀測值信息，最后完成當(dāng)前周期整網(wǎng)衛(wèi)星軌道鐘差信息的濾波更新。待整網(wǎng)衛(wèi)星軌道鐘差信息更新完畢后，算法生成各子衛(wèi)星星歷，下發(fā)于各子衛(wèi)星中。星上每隔一段時間執(zhí)行一次自主定軌算法，從而實現(xiàn)衛(wèi)星長時間的高精度自主定軌。

圖2 串行集中式自主定軌算法

在集中式自主定軌算法中，運算主要集中在軌道鐘差預(yù)報以及濾波更新這兩個模塊中。在串行算法中，軌道鐘差模塊每個周期算法需要對每一顆衛(wèi)星完成鐘差和軌道的預(yù)報，其過程由式（2）～（4）給出：

其中，Φ為轉(zhuǎn)移矩陣，P為協(xié)方差矩陣，Q為噪聲矩陣。因此，對于每顆衛(wèi)星而言，該部分的計算是一致且互不干擾的，易于并行化處理。而在濾波模塊，濾波過程由式（5）～（8）給出：

其中，H為觀測矩陣，Z為觀測量。在濾波模塊中，P為全局變量，包含了所有衛(wèi)星之間的協(xié)方差，但通過合理的劃分以及補償算法可以將這一全局矩陣劃分成若干子矩陣分散到不同節(jié)點中，在保證算法精度的同時極大提升算法效率。

考慮到這些算法的特征，集中式自主定軌的并行算法采用多進(jìn)程的方式將整網(wǎng)的衛(wèi)星和鏈路數(shù)據(jù)分散到集群的多個計算節(jié)點上同時進(jìn)行解算。

圖3為并行集中式自主定軌的算法流程。并行算法通過數(shù)據(jù)分發(fā)、同步、收集來完成多進(jìn)程的協(xié)同處理。在初始化時，主進(jìn)程負(fù)責(zé)將整網(wǎng)衛(wèi)星數(shù)據(jù)劃分為若干子集并將衛(wèi)星初始化信息分發(fā)到各個進(jìn)程中；在每個算法周期內(nèi)，主進(jìn)程在完成鏈路測距值的采集后對鏈路數(shù)據(jù)進(jìn)行分發(fā)，鏈路根據(jù)兩端點衛(wèi)星是否均包含在同一衛(wèi)星子集中可分為域內(nèi)鏈路和域間鏈路；各進(jìn)程完成衛(wèi)星軌道鐘差預(yù)報后相互交換數(shù)據(jù)，進(jìn)行同步。

在智慧圖書館背景下，圖書館服務(wù)不僅要從館內(nèi)向館外拓展，而且要從被動等待向主動尋求轉(zhuǎn)變。圖書館服務(wù)的優(yōu)劣，有賴于圖書館員是否有敏銳的洞察力和非凡的創(chuàng)造力，是否能夠時刻關(guān)注用戶需求，了解如何利用新技術(shù)、建設(shè)新資源，最大程度地滿足用戶需求，提升服務(wù)質(zhì)量。這要求圖書館員不僅要有扎實的專業(yè)能力，而且要有執(zhí)著的服務(wù)信念。

圖3 并行集中式自主定軌算法

在最后的濾波更新模塊中，各進(jìn)程分別利用星間測量值與預(yù)報信息進(jìn)行卡爾曼濾波。在串行集中式自主定軌算法中，濾波過程（式（5）～（8））需要維護(hù)大小為(D×n)2的協(xié)方差矩陣P以及大小為NL×D×n的測量矩陣H，其中，D是狀態(tài)量的維數(shù)，NL是生成導(dǎo)出雙向測距值的數(shù)目。于是濾波過程涉及的高維矩陣乘法算法復(fù)雜度可達(dá)到O(n3×NL)。并行算法中，對原協(xié)方差矩陣取廣義對角，即每個進(jìn)程只需要維護(hù)(D×nm)2大小的協(xié)方差矩陣，其中nm為子進(jìn)程負(fù)責(zé)維護(hù)的衛(wèi)星數(shù)目。由于只保留協(xié)方差的廣義對角矩陣而舍棄了其他元素，因此相對串行算法，該并行方案會損失一定的精度。但另一方面，這樣可以極大地提高算法解算速度，并且損失的精度在一定限度內(nèi)是為工程所允許的。相對地，測量矩陣的計算與串行算法也有一些區(qū)別。在串行算法中，鏈路有測量矩陣以及噪聲，如式（9）：

由于并行算法對整網(wǎng)衛(wèi)星進(jìn)行了劃分，存在域內(nèi)鏈路和域間鏈路，域內(nèi)鏈路的兩端點衛(wèi)星都在同一進(jìn)程所計算的衛(wèi)星子集內(nèi)，測量矩陣及噪聲與串行算法一致；域間鏈路的兩端點衛(wèi)星中有一個端點衛(wèi)星不在衛(wèi)星子集內(nèi)，于是只需要更新子集內(nèi)的衛(wèi)星信息。測量矩陣及噪聲表示為：

2 地面集群仿真結(jié)果

地面仿真利用亞馬遜的EC2 構(gòu)建一個小型地面集群對并行方案進(jìn)行可行性分析以及規(guī)律探討。在所構(gòu)建的集群中，每一臺實例擁有一個有效核，每個核的有效進(jìn)程數(shù)為1，運行內(nèi)存為1 740 MB，最多有兩個網(wǎng)絡(luò)接口。地面仿真采用多進(jìn)程的方式，不同進(jìn)程運行在集群的不同實例上，進(jìn)程之間采用消息傳遞的方式進(jìn)行通信[16-19]。

仿真數(shù)據(jù)集一共包含24 顆MEO 軌道衛(wèi)星，一個地面錨固站以及它們之間的240 條測距值，算法周期為300 s，測距精度為0.1 m。定軌精度通常由用戶測距誤差URE（User Range Error）來表示。表1 給出了不同計算節(jié)點數(shù)下30 天內(nèi)平均URE 誤差以及平均每周期運算時間的仿真結(jié)果。其中，p為計算節(jié)點數(shù)，即并行度。當(dāng)p=1 時，為集中式定軌算法，p=24時，為傳統(tǒng)的分布式定軌算法。

表1 計算節(jié)點數(shù)p和平均URE誤差以及平均每個周期運算時間的關(guān)系

分析并行度（計算節(jié)點數(shù)）p對算法精度的影響。從表1 中可以發(fā)現(xiàn)盡管并行算法的計算精度相對于原始的串行算法有一定損失，但若并行度控制在一定限度內(nèi)時，并行算法的URE 誤差遠(yuǎn)低于分布式定軌算法。例如，當(dāng)計算節(jié)點數(shù)為3 時，30 天的平均URE 誤差僅為0.142 25 m，遠(yuǎn)低于分布式算法約0.9 m 的平均URE 誤差。而計算性能方面，并行算法的計算性能卻遠(yuǎn)高于原始的串行算法。計算節(jié)點數(shù)和加速比及平均URE 誤差關(guān)系如圖4 所示。

圖4 計算節(jié)點數(shù)和加速比及平均URE誤差關(guān)系

從圖4 可以看出，當(dāng)并行度不大于3 時，計算性能的提升明顯，當(dāng)p大于3 時，由于通信成本增加等因素，加速比反而逐漸降低。由于算法中不可并行部分以及通信成本的存在，一味地增加計算節(jié)點數(shù)并不能獲得更高的計算加速比。在達(dá)到一定閾值時，增加節(jié)點數(shù)不能獲得更好的計算性能。

地面集群的仿真結(jié)果驗證了集中式定軌算法的并行優(yōu)化方案是可行的，并且給出了不同并行度下算法精度和計算性能的規(guī)律，為并行算法在星載計算機(jī)集群上的實際應(yīng)用提供預(yù)估和參考。

3 星載計算機(jī)集群仿真結(jié)果

基于1.1 節(jié)中描述的星載計算機(jī)集群架構(gòu)構(gòu)建仿真系統(tǒng)。該集群是一個同構(gòu)計算機(jī)集群，集群中最多可以有3 個節(jié)點提供計算力，每一個計算節(jié)點均由龍芯1E+龍芯1F 處理器組成。龍芯1E 和1F 均為中科龍芯公司設(shè)計的宇航級抗輻照芯片[16]：1E 處理器作為節(jié)點的中央處理器，是一臺單核處理器，采用雙發(fā)射五級流水，主頻為33 MHz，運行內(nèi)存為128 MB，負(fù)責(zé)節(jié)點上應(yīng)用程序的處理；龍芯1F 是龍芯1E 處理器的配套IO 橋芯片，在節(jié)點中主要負(fù)責(zé)外圍的通信。并行算法應(yīng)用到星載計算機(jī)集群的映射通過sMPI并行編程模型實現(xiàn)，集群中每個計算節(jié)點上運行一個進(jìn)程，進(jìn)程之間采用消息傳遞的方式共享數(shù)據(jù)。

星載計算機(jī)集群仿真所采用的測試數(shù)據(jù)集與地面仿真數(shù)據(jù)集相同，表2 給出了不同數(shù)目的衛(wèi)星和鏈路下，并行算法平均每周期運算時間以及運行內(nèi)存的占用情況。從表2 可知，與串行算法相比，并行算法有效地降低了單臺星載計算機(jī)的運行負(fù)載壓力，包括CPU 資源消耗以及運行內(nèi)存消耗。當(dāng)衛(wèi)星數(shù)為24 顆時，算法加速比可以達(dá)到1.94，單臺計算機(jī)節(jié)約了50%的運行內(nèi)存。并且，隨著衛(wèi)星數(shù)目的增加，通信消耗的占比逐漸減少，加速比得到明顯提升，當(dāng)衛(wèi)星總數(shù)達(dá)到48 顆，鏈路數(shù)達(dá)到928 條時，加速比達(dá)到了2.82，單臺計算機(jī)的運行內(nèi)存減少了55%。當(dāng)衛(wèi)星總數(shù)達(dá)到72 顆時，盡管運算時間從2 383 s降低到742 s，加速比達(dá)到3.20，但依舊超出了運算周期300 s 的限制。因此，對于更多的衛(wèi)星和鏈路，3 臺星載計算機(jī)的計算能力仍是有限的。另一方面，若采用更多的計算節(jié)點參與運算，星上通信開銷將會成為另一瓶頸，因此，該并行方案對于中等規(guī)模的衛(wèi)星和鏈路數(shù)據(jù)較為實用。若想擴(kuò)展應(yīng)用到更大規(guī)模的數(shù)據(jù)，參考地面集群的仿真結(jié)果則需要更多計算節(jié)點的參與，同時需要高速通信協(xié)議的配合。

表2 串行算法和并行算法效率對比

4 結(jié)束語

該文針對傳統(tǒng)串行集中式自主定軌算法提出了一種并行算法，并利用所設(shè)計的輕量級并行編程模型sMPI 在總線式星載計算機(jī)集群上實現(xiàn)了整網(wǎng)24顆MEO 衛(wèi)星自主定軌。以24 顆衛(wèi)星為例，當(dāng)星載計算機(jī)集群中有3 個節(jié)點參與計算時，30 天平均URE誤差為0.142 25 m，僅為分布式算法URE 誤差的15.8%。在保證定軌精度的同時，并行優(yōu)化算法顯著降低了星載計算機(jī)的負(fù)荷。在以龍芯1E 為主處理器的集群上的仿真結(jié)果顯示，當(dāng)衛(wèi)星數(shù)為24 時，3 個節(jié)點的加速比達(dá)到了1.94，平均19.738 s 就能生成整網(wǎng)軌道和鐘差結(jié)果，單臺星載計算機(jī)可減少約50%的內(nèi)存占用。

面對中等規(guī)模的衛(wèi)星數(shù)據(jù)，并行的集中式自主定軌算法在星載計算機(jī)集群上的表現(xiàn)良好，但面對衛(wèi)星數(shù)量更多以及更加復(fù)雜的衛(wèi)星網(wǎng)絡(luò)，該文星載計算機(jī)集群架構(gòu)依舊不能滿足計算力需求。限制星載計算機(jī)集群性能的一方面是集群中計算節(jié)點的數(shù)目以及單臺性能，另一方面是節(jié)點之間的通信開銷。根據(jù)地面仿真數(shù)據(jù)結(jié)果，通過增加計算節(jié)點數(shù)的辦法可以進(jìn)一步提升計算性能，但由于算法中不可并行部分以及通信成本的存在，在節(jié)點數(shù)達(dá)到一定閾值之后，增加節(jié)點數(shù)不再能獲得更高的計算加速比。因此，對于更多衛(wèi)星和鏈路的大規(guī)模星座，在現(xiàn)有數(shù)目的星載計算機(jī)節(jié)點不能滿足定軌計算需求的情況下，可以通過適當(dāng)增加集群中計算節(jié)點數(shù)目的方式來解決，甚至可以考慮利用多顆衛(wèi)星上的若干臺計算機(jī)進(jìn)行并行解算，或者采用高速通信協(xié)議來降低集群的通信成本開銷。