基于CUDA異構并行加速的兩行根數算法的研究

馮　森

（中國礦業大學（北京），研究生院，北京　100083）

?

基于CUDA異構并行加速的兩行根數算法的研究

馮森

（中國礦業大學（北京），研究生院，北京100083）

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

關鍵詞：兩行根數；CUDA；并行計

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

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

本文利用CUDA并行異構方法對兩行根數算法進行并行加速改造，提高衛星位置和速度信息的計算速度顯得尤為必要。

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

傳統的CPU計算是串行計算。串行計算由一組離散的指令序列組成，在一個CPU上指令序列被一個一個的依次運行，并且在任何時間最多只有一個指令在運行。

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

圖1　CUDA架構數據處理流程

CUDA編程模型將CPU作為主機（Host），GPU作為協處理器或者設備（Device），它們協同工作，各司其職。CPU負責進行邏輯性強的事務處理和串行計算，GPU則專注于執行高度線程化的并行處理任務。運行在GPU上的CUDA并行計算函數稱為內核函數。一個內核函數并不是一個完整的程序，而是一個可以被GPU并行執行的計算任務。CUDA的線程模型，內核以線程網格（Grid）的形式組織，每個線程網格由若干個線程快（block）組成，而每個線程塊又由若干個線程（thread）組成。每個線程都有唯一的坐標，線程根據其所在的線程塊的塊號和塊內的線程號來訪問存儲區及互相通信。如圖2所示。

圖2　CUDA線程模型

2　兩行根數算法的并行加速改造

每一顆衛星的TLE軌道報的正文都是由兩行構成，格式如表1所示。其中，第0行是衛星名稱，第1行和第2行是標準的NORAD兩行根數軌道報格式。具體的兩行根數軌道參數描述如表2和表3所示。

表1　TERRA衛星TLE軌道根數參數

表2　TLE軌道參數第1行格式描述

表3　TLE軌道參數第2行格式描述

目前NORAD發布的 TLE計算衛星軌道的方法是采用SGP4/SDP4模型進行計算的，其算法流程如圖3所示。

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

圖3　SGP4/SDP4模型計算兩行根數算法流程

3　實驗測試結果

采用兩行根數部分數據進行測試，比較使用CUDA加速前和加速后的結果如圖4-5所示。由測試結果可知，使用CUDA并行加速之后的兩行根數計算效率大大提高，計算時間大約縮短了1/14。

圖4　CUDA并行加速改造前的計算時間

圖5　CUDA并行加速改造后的計算時間

4　結語

本文通過對基于CUDA并行加速改造的兩行根數算法的研究，探索了CUDA在航天領域的應用，解決了兩行根數計算效率問題。并行加速改造除了使用GPU外，還可以使用CPU多進程的方法進行并行計算，再結合CUDA編程模型，算法的計算時間將會進一步縮短，這可以作為以后的一個新的研究方向。

［參考文獻］

［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］韓潮，章仁為.利用雷達測高儀的衛星自主定軌［J］.宇航學報，1999（7）：1.

［6］楊維廉.關于衛星運動的交點周期［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

作者簡介：馮森（1986-），男，遼寧沈陽。