基于GPU的非相干消色散算法*

托乎提努爾，張海龍，王 杰，冶鑫晨

(1. 中國(guó)科學(xué)院新疆天文臺(tái)，新疆 烏魯木齊 830011；2. 中國(guó)科學(xué)院射電天文重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210008；3. 國(guó)家天文科學(xué)數(shù)據(jù)中心，北京 100101)

宇宙空間中的星際介質(zhì)(Inter-Stellar Medium, ISM)[1]包含大量電離氣體云、中性塵埃粒子和自由電子等物質(zhì)。脈沖星信號(hào)在宇宙空間傳播時(shí)因?yàn)樾请H介質(zhì)色散的影響而降低速度，高頻無(wú)線電波傳播速度比低頻快，所以高頻和低頻電磁波到達(dá)射電望遠(yuǎn)鏡的時(shí)間不一致，脈沖星信號(hào)因此出現(xiàn)能量分散而使脈沖輪廓加寬，信噪比下降，甚至脈沖信號(hào)消失。

為了解決脈沖星信號(hào)色散問(wèn)題，天文學(xué)家研究了消除色散的方法[2-3]及高速消色散處理技術(shù)。利用多通道濾波器組[4]對(duì)脈沖星信號(hào)進(jìn)行通道劃分，生成多個(gè)窄帶信號(hào)，針對(duì)窄帶信號(hào)進(jìn)行時(shí)間延遲處理，每個(gè)通道延遲時(shí)間可以通過(guò)色散公式計(jì)算，最后將所有窄帶通道累加，獲得高信噪比的脈沖信號(hào)。

非相干消色散是脈沖星觀測(cè)數(shù)據(jù)處理中最常用的色散處理方法，具有實(shí)現(xiàn)簡(jiǎn)單、速度快、數(shù)據(jù)后期處理靈活等優(yōu)勢(shì)。在脈沖星搜尋中，隨著色散量(Dispersion Measure, DM)、數(shù)據(jù)通道及采樣數(shù)量的增加，非相干消色散算法的計(jì)算量迅速增加，通常的計(jì)算平臺(tái)難以實(shí)現(xiàn)脈沖星數(shù)據(jù)的實(shí)時(shí)處理。近年來(lái)，圖形處理器[5-6]的可編程能力及并行處理能力迅速提高，應(yīng)用范圍不斷擴(kuò)展，在中央處理器 + 圖形處理器混合計(jì)算系統(tǒng)中，圖形處理器的加入大大提高了整個(gè)系統(tǒng)的數(shù)據(jù)處理能力。高性能圖形處理器集群可提供強(qiáng)大的計(jì)算資源，能夠滿足海量天文數(shù)據(jù)實(shí)時(shí)處理的需求，從而解決脈沖星消色散算法計(jì)算量巨大、無(wú)法實(shí)時(shí)處理的問(wèn)題。

1 非相干消色散

非相干消色散算法根據(jù)色散公式計(jì)算每個(gè)通道的延遲時(shí)間，然后加上各個(gè)通道的延遲，并把所有通道疊加在一起，即可消除數(shù)據(jù)的色散影響。非相干消色散原理如圖1。

非相干消色散采用多通道濾波器組實(shí)現(xiàn)，消色散處理過(guò)程主要包括：(1)通道劃分，使用濾波器組把觀測(cè)的天文信號(hào)總帶寬分成若干個(gè)相互獨(dú)立的狹窄通道；(2)補(bǔ)充時(shí)間延遲，根據(jù)色散公式計(jì)算每個(gè)通道的時(shí)間延遲，按延遲進(jìn)行通道平移，將各個(gè)窄帶通道的脈沖信號(hào)在同一時(shí)刻對(duì)齊；(3)通道累加，將所有通道時(shí)間序列疊加在一起。

圖1 非相干消色散原理Fig.1 The principle of incoherent de-dispersion

圖1說(shuō)明了非相干消色散的處理過(guò)程。圖1(a)未進(jìn)行消色散，圖1(b)是消色散處理后的結(jié)果。從圖1可以看出，消色散前，通道累加之后脈沖寬度被展寬，輸出信號(hào)信噪比下降，消色散之后可以得到信噪比大幅提高的脈沖星輪廓。

非相干消色散已經(jīng)廣泛應(yīng)用于脈沖星、快速射電爆[7]搜尋。非相干消色散方法處理后的脈沖星數(shù)據(jù)，各個(gè)子通道內(nèi)的色散延遲依舊存在，不能得到脈沖星的真實(shí)輪廓，隨著頻譜通道數(shù)的增加，每個(gè)通道的帶寬變小，帶內(nèi)的色散效應(yīng)相應(yīng)降低，低頻信號(hào)f1和高頻信號(hào)f2在星際介質(zhì)中的傳播時(shí)間差為

(1)

其中，c為光在真空中的傳播速度；e為電子電荷；D為色散量；m為電子質(zhì)量。D可表示為

(2)

其中，ne為電子密度；d為電磁波實(shí)際經(jīng)過(guò)的路徑。

脈沖星消色散處理中，一個(gè)頻率通道fchan相對(duì)于參考通道fref(通常是觀測(cè)帶寬中心頻率)的時(shí)間延遲可以根據(jù)色散量公式計(jì)算：

(3)

其中，KDM為色散量常數(shù)；D為觀測(cè)脈沖星信號(hào)的色散量，單位為cm-3·pc；頻率單位為MHz。色散量常數(shù)為

(4)

在觀測(cè)中，觀測(cè)頻率f往往遠(yuǎn)大于劃分的通道帶寬Δf，如果f? Δf時(shí)，頻率通道的延遲時(shí)間可以寫為

tDM=8.3×106DΔff-3ms ，

(5)

(5)式說(shuō)明通道帶寬和色散延遲時(shí)間成正比，為了得到更小的色散延遲，需要?jiǎng)澐趾芗?xì)的窄帶通道，盡量減小單通道信號(hào)帶寬。

2 非相干消色散算法的圖形處理器實(shí)現(xiàn)

圖形處理器是現(xiàn)代計(jì)算機(jī)中常見(jiàn)的設(shè)備，專為執(zhí)行復(fù)雜的數(shù)學(xué)計(jì)算而設(shè)計(jì)的一種高度并行化、多線程的多核處理器，可以高速實(shí)現(xiàn)圖形渲染?；趫D形處理器的通用計(jì)算技術(shù)已經(jīng)成為高性能并行計(jì)算領(lǐng)域的研究熱點(diǎn)。圖形處理器由于具備多個(gè)核心，更適合計(jì)算密集型數(shù)據(jù)。圖形處理器的內(nèi)核相當(dāng)于中央處理器的多個(gè)線程，這些線程可以并行運(yùn)行完成指定的計(jì)算任務(wù)，而且數(shù)值計(jì)算的速度遠(yuǎn)遠(yuǎn)優(yōu)于中央處理器。圖形處理器的線程結(jié)構(gòu)如圖2。

圖2 圖形處理器的線程結(jié)構(gòu)Fig.2 GPU thread structure

圖形處理器的開發(fā)使用統(tǒng)一計(jì)算設(shè)備架構(gòu)(Compute Unified Device Architecture, CUDA)[8]，它是一種由英偉達(dá)(NVIDIA)推出的通用并行計(jì)算平臺(tái)和編程模型，使圖形處理器能夠解決復(fù)雜的計(jì)算問(wèn)題。CUDA提供了硬件的直接訪問(wèn)接口，不依賴圖形應(yīng)用程序接口實(shí)現(xiàn)圖形處理器訪問(wèn)，在架構(gòu)上采用全新的計(jì)算體系結(jié)構(gòu)來(lái)使用圖形處理器提供的硬件資源。CUDA采用標(biāo)準(zhǔn)C語(yǔ)言的擴(kuò)展作為編程語(yǔ)言提供大量的高性能計(jì)算指令，能夠在圖形處理器強(qiáng)大的計(jì)算能力基礎(chǔ)上實(shí)現(xiàn)效率更高的密集數(shù)據(jù)計(jì)算算法。

本文分析和研究非相干消色散算法的結(jié)構(gòu)，把計(jì)算量大的任務(wù)部分映射到圖形處理器的多線程進(jìn)行處理。非相干消色散算法復(fù)雜度為O(NdNsNc)，其中，Nd為色散量總數(shù)；Nc為通道數(shù)；Ns為采樣數(shù)，算法數(shù)學(xué)模型計(jì)算量較大，但是通過(guò)圖形處理器可以得到很高的加速比。在算法中，對(duì)非相干消色散的色散量和時(shí)間維度進(jìn)行并行化，頻率通道累加采用串行的處理方法，即使用圖形處理器的單線程實(shí)現(xiàn)了Nc個(gè)通道的相加計(jì)算。在整個(gè)消色散過(guò)程中，中央處理器負(fù)責(zé)系統(tǒng)的初始化和輸入數(shù)據(jù)讀取，圖形處理器負(fù)責(zé)并行消色散處理，中央處理器接收消色散后的時(shí)間序列并輸出到數(shù)據(jù)文件。非相干消色散算法CUDA程序流程圖如圖3。

首先在中央處理器內(nèi)存中開辟緩沖區(qū)，寫入需要處理的數(shù)據(jù)。緩沖區(qū)暫存的采樣都存在一定的色散，因此，需要對(duì)各個(gè)頻率通道進(jìn)行位移和累加運(yùn)算，隨著時(shí)間延遲增大，通道位移也增大，低頻通道的位移量更大。為了減小中央處理器和圖形處理器之間頻繁的數(shù)據(jù)傳輸對(duì)算法計(jì)算性能的影響，在圖形處理器中設(shè)置全局內(nèi)存緩沖區(qū)，盡量把大量數(shù)據(jù)一次性復(fù)制過(guò)去，并且為寫入和讀取數(shù)據(jù)保留足夠的存儲(chǔ)空間。圖形處理器 kernel函數(shù)執(zhí)行過(guò)程中，使用共享內(nèi)存減小全局內(nèi)存的延遲，提高運(yùn)行速度。

圖3 非相干消色散CUDA程序流程圖Fig.3 Flow chart of CUDA program for incoherent de-dispersion

為了提高算法的并行化加速，將非相干消色散算法的計(jì)算分為兩部分，在中央處理器上執(zhí)行計(jì)算的第1部分所需的時(shí)間

tchan=4.15×103(f1-2-f2-2)，

(6)

其中，f1，f2的單位為MHz；tchan的計(jì)算與色散量無(wú)關(guān)，使用圖形處理器的常量?jī)?nèi)存存儲(chǔ)。在圖形處理器上執(zhí)行計(jì)算的第2部分所需的時(shí)間

(7)

其中，tsamp為采樣時(shí)間，單位為ms。

根據(jù)非相干消色散算法的特性，圖形處理器kernel函數(shù)中定義了兩個(gè)緩沖區(qū)：共享內(nèi)存和常量?jī)?nèi)存，其中共享內(nèi)存用于存儲(chǔ)積分運(yùn)算的結(jié)果，常量?jī)?nèi)存用于存儲(chǔ)DM_shift。為了加快通道累加，使用共享內(nèi)存隱藏全局內(nèi)存的訪問(wèn)延遲。一個(gè)線程塊里面的所有線程獲取色散量平移值，并且存儲(chǔ)到共享內(nèi)存。對(duì)于每一個(gè)色散量，在共享內(nèi)存中進(jìn)行積分運(yùn)算，并把消色散處理結(jié)果寫入圖形處理器的全局內(nèi)存。

3 實(shí)驗(yàn)分析

本次實(shí)驗(yàn)平臺(tái)使用Intel Xeon E5-1620，TITAN V，CUDA 10.0及Ubuntu 18.04。TITAN V是一款NVIDIA GeForce系列高端圖形處理器，擁有5 120個(gè)CUDA核，內(nèi)存訪問(wèn)帶寬為652.8 GB/s。

為了驗(yàn)證圖形處理器并行算法的性能，首先分別模擬生成了32、64、128、256、512及1 024通道脈沖星數(shù)據(jù)，其中心頻率為420 MHz，帶寬為6 MHz，采樣間隔時(shí)間為165 μs，脈沖星信號(hào)周期為0.1 s，然后將每一塊數(shù)據(jù)單獨(dú)讀取并加載到圖形處理器中進(jìn)行處理。實(shí)驗(yàn)結(jié)果如表1、表2、表3及表4。

表1 采樣數(shù)固定時(shí)非相干消色散處理時(shí)間(單位：s，采樣：131 072)

表2 采樣數(shù)固定時(shí)非相干消色散處理時(shí)間(單位：s，采樣：131 072)

表1、表2是在采樣數(shù)為131 072(單通道采樣)，通道和色散量都變化的情況下圖形處理器并行算法和中央處理器串行算法的非相干消色散處理消耗時(shí)間。從表中可以看出，當(dāng)通道數(shù)量固定時(shí)，隨著色散量的增加，圖形處理器和中央處理器的數(shù)據(jù)處理時(shí)間線性增加，圖形處理器的消色散處理時(shí)間遠(yuǎn)遠(yuǎn)少于中央處理器的；當(dāng)色散量固定時(shí)，隨著數(shù)據(jù)通道數(shù)量的增加，中央處理器和圖形處理器的處理時(shí)間增加，但是中央處理器的計(jì)算時(shí)間比圖形處理器大得多。

表3 通道數(shù)固定時(shí)非相干消色散處理時(shí)間(單位：s，通道：1 024)

表4 色散量固定時(shí)非相干消色散處理時(shí)間(單位：s，色散量：5 120)

表3是通道數(shù)為1 024、采樣數(shù)和色散量都變化的情況下，圖形處理器并行算法和中央處理器串行算法的非相干消色散處理消耗時(shí)間。當(dāng)采樣數(shù)固定時(shí)，隨著色散量的增加，圖形處理器和中央處理器的數(shù)據(jù)處理時(shí)間增加；當(dāng)色散量固定時(shí)，隨著采樣數(shù)的增加，并行和串行算法處理時(shí)間增加，但是，圖形處理器的計(jì)算時(shí)間少于中央處理器的，計(jì)算速度有幾百倍的差距。從表中可以看出，圖形處理器大大縮短了非相干消色散的執(zhí)行時(shí)間。

表4是色散量為5 120、采樣數(shù)和通道數(shù)都變化的情況下，圖形處理器并行算法和中央處理器串行算法的非相干消色散處理消耗時(shí)間。當(dāng)采樣數(shù)固定時(shí)，隨著通道數(shù)的增加，圖形處理器和中央處理器的數(shù)據(jù)處理時(shí)間增加；當(dāng)通道數(shù)固定時(shí)，隨著采樣數(shù)的增加，并行和串行算法處理時(shí)間增加。在通道數(shù)或采樣數(shù)變化的情況下，圖形處理器的運(yùn)算時(shí)間均小于中央處理器，且消耗時(shí)間差距明顯。

和中央處理器相比，圖形處理器非相干消色散的數(shù)據(jù)處理能力達(dá)到幾百倍的加速比，具有顯著的加速優(yōu)勢(shì)。圖形處理器并行算法的加速比性能如圖4、圖5及圖6。

圖4 采樣數(shù)為131 072時(shí)圖形處理器算法加速比Fig.4 GPU algorithm speed-up when the number of samples is 131 072

圖5 色散量為5 120時(shí)圖形處理器算法加速比Fig.5 GPU algorithm speed-up when the number of DMs is 5 120

圖4是采樣數(shù)為131 072、通道數(shù)和色散量均變化的情況下，圖形處理器并行算法的加速比。從圖中可以看出，隨著色散量的增加，并行算法的加速比提高。當(dāng)色散量個(gè)數(shù)為2 560時(shí)，TITAN V的加速比最高(即達(dá)到中央處理器速度的538倍)，然后加速比開始下降。如圖4，通道數(shù)量越多，圖形處理器算法的加速比越大，加速性能越好。當(dāng)通道數(shù)為1 024時(shí)加速比最高，當(dāng)通道數(shù)為32時(shí)加速比最小。

圖5是色散量為5 120、通道數(shù)和采樣數(shù)都變化的情況下，圖形處理器并行算法的加速比。從圖中可以看出，隨著采樣數(shù)的增加，并行算法的加速比有所下降，但算法加速高達(dá)550多倍。當(dāng)通道數(shù)為1 024時(shí)，TITAN V達(dá)到最高的加速比。當(dāng)通道數(shù)為1 024、采樣數(shù)為8 192時(shí)，圖形處理器并行算法的速度是中央處理器串行算法的780多倍。

圖6 通道數(shù)為1 024時(shí)圖形處理器算法加速比Fig.6 GPU algorithm speed-up when the number of channels is 131 072

圖6是通道數(shù)為1 024、采樣數(shù)和色散量都變化的情況下，圖形處理器并行算法的加速比。從圖中可以看出，色散量個(gè)數(shù)對(duì)圖形處理器非相干消色散算法加速比影響最大。隨著色散量的增加，圖形處理器并行算法的加速比迅速提高。如圖6，色散量個(gè)數(shù)越大，計(jì)算消耗時(shí)間越多，當(dāng)色散量為5 120時(shí)加速比最大。

實(shí)驗(yàn)結(jié)果表明，采樣數(shù)、通道數(shù)及色散量個(gè)數(shù)都是影響圖形處理器算法加速性能的關(guān)鍵因素。非相干算法執(zhí)行過(guò)程中，圖形處理器展示了強(qiáng)大的并行化處理優(yōu)勢(shì)，節(jié)省了大量重復(fù)計(jì)算時(shí)間，提升了算法的計(jì)算效率。

4 總 結(jié)

本文研究基于圖形處理器的非相干消色散算法，提出了相關(guān)算法的圖形處理器并行化加速方案，分析了算法的密集型計(jì)算部分，研究了圖形處理器多線程任務(wù)分配、管理及存器層次的優(yōu)化方法，提高了圖形處理器資源利用率，顯著提升了算法的計(jì)算性能。在圖形處理器算法的實(shí)現(xiàn)過(guò)程中，我們深入分析了影響并行算法性能的主要因素，優(yōu)化了CUDA程序，大大減少了算法執(zhí)行的時(shí)間，圖形處理器消色散算法加速比接近700倍，解決了算法在中央處理器上計(jì)算量巨大、無(wú)法實(shí)時(shí)處理的問(wèn)題，通過(guò)實(shí)驗(yàn)分析算法的數(shù)據(jù)處理時(shí)間和加速比，驗(yàn)證了并行算法性能。