集中式自主定軌算法在星載計算機集群上的并行實現

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

（1.中國科學院空天信息創新研究院，北京 100094；2.中國科學院大學，北京 100049；3.中國科學院微小衛星創新研究院，上海 201210；4.上海微小衛星工程中心，上海 201210；5.上海科技大學，上海 201210）

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

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

1 集中式自主定軌算法并行優化方案

1.1 并行系統架構

中科院北斗三號衛星載有多臺星載計算機，分工處理星上各類應用，星載計算機之間采用1553B總線通信。星載計算機集群的架構如圖1 所示，屬于總線式集群，多個計算節點通過1553B 總線相連。

圖1 系統架構

1553B 是一種在航空航天領域應用廣泛的中央集權式總線協議[11]，總線的設計傳輸速率為1 Mb/s，總線上設備分為總線控制器（BC）、遠程終端（RT）以及總線監視器（BM）。星載計算機集群上的計算節點作為RT 掛載在總線上。

1.2 并行編程模型

并行編程模型是一組程序的抽象，它將應用程序的并行行為配適到底層并行硬件[12]。在高性能計算機集群時代，MPI 一直是高性能計算領域中的一種標準實現方案[13]，但MPI 是為大規模具有高性能計算機的集群而設計的[14]，這些計算機通常擁有比星載計算機更加強大的處理器、更大的內存空間以及更加靈活的網絡連接方式。因此，直接將MPI 遷移到現有的星載計算機集群上將會面臨巨大的挑戰。

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

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

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

1.3 并行算法描述

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

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

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

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

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

考慮到這些算法的特征，集中式自主定軌的并行算法采用多進程的方式將整網的衛星和鏈路數據分散到集群的多個計算節點上同時進行解算。

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

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

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

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

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

2 地面集群仿真結果

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

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

表1 計算節點數p和平均URE誤差以及平均每個周期運算時間的關系

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

圖4 計算節點數和加速比及平均URE誤差關系

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

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

3 星載計算機集群仿真結果

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

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

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

4 結束語

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

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