集中式自主定軌算法在星載計(jì)算機(jī)集群上的并行實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

1.2 并行編程模型

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

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

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

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

1.3 并行算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 串行算法和并行算法效率對(duì)比

4 結(jié)束語

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

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