馮　森

（中國(guó)礦業(yè)大學(xué)（北京），研究生院，北京　100083）

?

基于CUDA異構(gòu)并行加速的兩行根數(shù)算法的研究

馮森

（中國(guó)礦業(yè)大學(xué)（北京），研究生院，北京100083）

摘要：隨著航天技術(shù)的迅速發(fā)展，宇宙中航天器越來越多，利用兩行根數(shù)（TLE）的數(shù)據(jù)對(duì)航天器的位置、運(yùn)行狀態(tài)、運(yùn)行軌道監(jiān)控分析判斷，防止航天器相互碰撞，顯得尤為重要。如果能減少兩行根數(shù)的計(jì)算時(shí)間，無疑會(huì)讓監(jiān)控更加實(shí)時(shí)，地面控制中心快速做出相應(yīng)操作。NVIDIA的CUDA并行計(jì)算編程架構(gòu)結(jié)合高性能計(jì)算顯卡（GPU）正是為了解決高性能計(jì)算問題而推出的，可以大幅縮短復(fù)雜計(jì)算的時(shí)間。文章研究了兩行根數(shù)算法的并行改造，利用CUDA并行架構(gòu)和GPU硬件作為CPU的協(xié)處理器，將兩行根數(shù)算法的計(jì)算時(shí)間大幅縮小，解決了兩行根數(shù)的計(jì)算時(shí)間問題。實(shí)驗(yàn)結(jié)果證明利用CUDA并行加速的兩行根數(shù)算法計(jì)算時(shí)間大幅減少，提高了計(jì)算效率。

關(guān)鍵詞：兩行根數(shù)；CUDA；并行計(jì)

兩行根數(shù)TLE（Two-Line Element）是北美防空司令部（NORAD，NorthAmerican Air Defense Command）基于一般攝動(dòng)理論生成的一組根數(shù)體系。它是由兩行具有特殊意義的數(shù)字和字母組成的，用來預(yù)報(bào)地球飛行器的位置和速度，對(duì)于定位空間衛(wèi)星具有很重要的作用，因此提高兩行根數(shù)的運(yùn)算速度有著十分重要的意義。SGP4（simplified general perturbations satellite orbit model 4）模型是由Ken Granford在1970年開發(fā)的，NO-RAD（美國(guó)北美空間防御司令部）基于SGP4算法開發(fā)了一種廣泛應(yīng)用于空間目標(biāo)軌道預(yù)報(bào)的軟件，它的輸入數(shù)據(jù)是兩行根數(shù)。將兩行根數(shù)代入SGP4模型，即可求出任意時(shí)刻空間目標(biāo)的位置和速度。1980年NO-RAD公布了針對(duì)兩行根數(shù)的SGP4模型程序代碼。

2007年NVIDIA 公司推出了一種通用并行計(jì)算架構(gòu)CUDA，該架構(gòu)使GPU能夠解決復(fù)雜的計(jì)算問題。它包含了CUDA指令集架構(gòu)以及GPU內(nèi)部的并行計(jì)算引擎。開發(fā)人員可以使用熟悉的C，C++，F(xiàn)ORTRAN等高級(jí)語言來編寫程序。 目前CUDA被廣泛應(yīng)用于石油勘測(cè)、流體力學(xué)模擬、分子動(dòng)力學(xué)仿真、生物計(jì)算、圖像處理、音視頻編解碼、航天等領(lǐng)域，在很多應(yīng)用中獲得了幾倍、幾十倍，乃至上百倍的加速比。

本文利用CUDA并行異構(gòu)方法對(duì)兩行根數(shù)算法進(jìn)行并行加速改造，提高衛(wèi)星位置和速度信息的計(jì)算速度顯得尤為必要。

1　CUDA并行加速改造原理介紹

傳統(tǒng)的CPU計(jì)算是串行計(jì)算。串行計(jì)算由一組離散的指令序列組成，在一個(gè)CPU上指令序列被一個(gè)一個(gè)的依次運(yùn)行，并且在任何時(shí)間最多只有一個(gè)指令在運(yùn)行。

并行計(jì)算可使用多個(gè)計(jì)算資源解決計(jì)算問題。并行計(jì)算的模塊可以被分為幾個(gè)離散的部分被同時(shí)運(yùn)行，每一部分包含一組指令序列在不同的處理期上同時(shí)運(yùn)行。采用并行計(jì)算需要具備兩個(gè)條件：擁有多個(gè)計(jì)算資源、問題可被分解為多個(gè)獨(dú)立的工作塊。由于同一時(shí)間有多個(gè)計(jì)算指令在運(yùn)行，因此解決問題的時(shí)間比串行計(jì)算更短。CUDA架構(gòu)數(shù)據(jù)處理流程如圖1所示。

圖1　CUDA架構(gòu)數(shù)據(jù)處理流程

CUDA編程模型將CPU作為主機(jī)（Host），GPU作為協(xié)處理器或者設(shè)備（Device），它們協(xié)同工作，各司其職。CPU負(fù)責(zé)進(jìn)行邏輯性強(qiáng)的事務(wù)處理和串行計(jì)算，GPU則專注于執(zhí)行高度線程化的并行處理任務(wù)。運(yùn)行在GPU上的CUDA并行計(jì)算函數(shù)稱為內(nèi)核函數(shù)。一個(gè)內(nèi)核函數(shù)并不是一個(gè)完整的程序，而是一個(gè)可以被GPU并行執(zhí)行的計(jì)算任務(wù)。CUDA的線程模型，內(nèi)核以線程網(wǎng)格（Grid）的形式組織，每個(gè)線程網(wǎng)格由若干個(gè)線程快（block）組成，而每個(gè)線程塊又由若干個(gè)線程（thread）組成。每個(gè)線程都有唯一的坐標(biāo)，線程根據(jù)其所在的線程塊的塊號(hào)和塊內(nèi)的線程號(hào)來訪問存儲(chǔ)區(qū)及互相通信。如圖2所示。

圖2　CUDA線程模型

2　兩行根數(shù)算法的并行加速改造

每一顆衛(wèi)星的TLE軌道報(bào)的正文都是由兩行構(gòu)成，格式如表1所示。其中，第0行是衛(wèi)星名稱，第1行和第2行是標(biāo)準(zhǔn)的NORAD兩行根數(shù)軌道報(bào)格式。具體的兩行根數(shù)軌道參數(shù)描述如表2和表3所示。

表1　TERRA衛(wèi)星TLE軌道根數(shù)參數(shù)

表2　TLE軌道參數(shù)第1行格式描述

表3　TLE軌道參數(shù)第2行格式描述

目前NORAD發(fā)布的 TLE計(jì)算衛(wèi)星軌道的方法是采用SGP4/SDP4模型進(jìn)行計(jì)算的，其算法流程如圖3所示。

整個(gè)算法計(jì)算量最大的地方在于n次for循環(huán)對(duì)循環(huán)體的計(jì)算，每次SGP4/SDP4模型的計(jì)算之間數(shù)據(jù)耦合度為0，所以這個(gè)算法適合使用CUDA并行模型進(jìn)行加速改造。改造的方法如下：（1）首先將CPU中兩行根數(shù)的計(jì)算數(shù)據(jù)傳入GPU中。（2）在GPU中啟動(dòng)N個(gè)線程對(duì)應(yīng)并行計(jì)算N次for循環(huán)中的SGP4/SDP4模型計(jì)算處理。（3）等待所有GPU線程計(jì)算完成后，將計(jì)算結(jié)果傳送給CPU，繼續(xù)算出位置和速度信息的處理。（4）最終算出衛(wèi)星的速度和位置。

圖3　SGP4/SDP4模型計(jì)算兩行根數(shù)算法流程

3　實(shí)驗(yàn)測(cè)試結(jié)果

采用兩行根數(shù)部分?jǐn)?shù)據(jù)進(jìn)行測(cè)試，比較使用CUDA加速前和加速后的結(jié)果如圖4-5所示。由測(cè)試結(jié)果可知，使用CUDA并行加速之后的兩行根數(shù)計(jì)算效率大大提高，計(jì)算時(shí)間大約縮短了1/14。

圖4　CUDA并行加速改造前的計(jì)算時(shí)間

圖5　CUDA并行加速改造后的計(jì)算時(shí)間

4　結(jié)語

本文通過對(duì)基于CUDA并行加速改造的兩行根數(shù)算法的研究，探索了CUDA在航天領(lǐng)域的應(yīng)用，解決了兩行根數(shù)計(jì)算效率問題。并行加速改造除了使用GPU外，還可以使用CPU多進(jìn)程的方法進(jìn)行并行計(jì)算，再結(jié)合CUDA編程模型，算法的計(jì)算時(shí)間將會(huì)進(jìn)一步縮短，這可以作為以后的一個(gè)新的研究方向。

［參考文獻(xiàn)］

［1］KELSO TS.Two-Line Element Set Format［EB/OL］.http：//celestrak.com/columns/v04 n03/FAQ01.

［3］B.Wun，J.Buhler， and P.Crowley.Exploiting Coarse Grained Parallelism to Accelerate Prote in Motif Finding with a Network Processor［C］//PACT 2005： In Proceedings of International Conference on Parallel Architectures and Compilation Techniques，2005.

［4］Zhiyi Yang， Yating Zhu， Yong Pu.Parallel Image Processing Based on CUDA［C］//CSSE2008： proceeding of 2008 International Conference on Computer Science and SoftwareEngineering，2008.

［5］韓潮，章仁為.利用雷達(dá)測(cè)高儀的衛(wèi)星自主定軌［J］.宇航學(xué)報(bào)，1999（7）：1.

［6］楊維廉.關(guān)于衛(wèi)星運(yùn)動(dòng)的交點(diǎn)周期［J］.航天器工程，1997（3）：33-34.

Research on Heterogeneous Parallel CUDA Accelerated Two Lines of the Number of Algorithm

Feng Sen
（Graduate School， China University of Mining （Beijing）， Beijing100083， China）

Abstract：With Space Technology rapid development， more and more spacecraft in the universe using two lines of the number （TLE）data on the spacecraft's position， running， running track monitoring analysis and judgment to prevent aerospace collide with each other，it is particularly important. If you can reduce the number of computing time two lines， no doubt will make more real-time monitoring， the ground control center to quickly make the appropriate action. NVIDIA CUDA parallel computing architecture with high-performance computing programming graphics card （GPU） in order to solve the problem and the introduction of high-performance computing， complex calculations can signifcantly shorten the time. In this paper， the number two lines parallel transformation algorithm using CUDA parallel hardware architecture and GPU as a CPU coprocessor， will significantly reduce the number of two-line computing time algorithm to solve the problem of computing time two rows of the number. Experimental results show that the use of CUDA parallel acceleration of the number of two-line algorithm reduces computational time and improve effciency.

Key words：two lines of the number; CUDA; parallel computing

作者簡(jiǎn)介：馮森（1986-），男，遼寧沈陽。