一種適用于GPU圖像處理算法的合并存儲結構*

左憲禹，張 哲，黃祥志，葛 強，張理濤，臧文乾

(1.河南省大數據分析與處理重點實驗室，河南 開封 475004; 2.河南大學計算機與信息工程學院數據與知識工程研究所，河南 開封 475004; 3.鄭州航空工業管理學院數學學院，河南 鄭州 450015; 4.中國科學院空天信息創新研究院，北京 100094;5.中科空間信息(廊坊)研究院，河北 廊坊 065000)

1 引言

由于硬件架構的特點，GPU (Graphics Processing Units)在大數據量、密集型計算方面具有較大優勢，因此被廣泛應用于圖像處理領域，以提高圖像處理算法的執行速度[1 - 3]。但是，由于GPU上的部分計算資源如顯存(Graphics Memory)容量等與CPU相比較小，而計算核心(Cores)數量與CPU相比則較充足，因此利用GPU進行加速的圖像處理算法必須依據硬件架構有針對性地設計算法流程，才能使GPU計算資源利用率最大化，取得較好的加速效果。

針對圖像處理算法的GPU并行加速問題，現有文獻提出了多種方法用以提高GPU資源利用率及加速效果。Luley等[4]利用CUDA(Compute Unified Device Architecture)編程模型的Hyper-Q特性和CUDA流(Stream)將數據傳輸與核函數執行操作進行重疊(Overlap)，以減少部分數據傳輸及核函數執行耗時。Pai等[5]則重點關注GPU硬件資源的更新升級對算法的影響，并提出了一種允許對GPU計算資源進行細粒度控制的彈性核函數策略，大大提高了程序的可擴展性及兼容性。沈夏炯等[2]針對遙感影像的特點，提出了對較大尺寸遙感影像進行分塊、分批次處理的方法，并取得了較好的加速效果。通過對GPU硬件架構的研究以及對基于GPU加速圖像處理算法類文獻的總結，可以發現基于GPU優化的圖像處理算法中影響加速性能提升的2個主要耗時因素是數據傳輸與核函數執行。為了進一步提高圖像處理算法的GPU加速效果，通常采用文獻[4]中提出的方法，利用CUDA流來重疊數據傳輸與核函數執行，以減少部分數據傳輸和核函數執行耗時。但是，對于數據傳輸與核函數執行操作之間的調用間隙問題、較小尺寸圖像的批量處理問題以及算法中包含較多輸入圖像，并對各輸入圖像分別執行無依賴性[2]處理步驟(本文將這類操作稱為算子)的情況，即使利用CUDA流對數據傳輸與核函數執行進行重疊，在執行性能方面仍存在可提升空間。

為了優化上述問題，本文以待處理圖像的存儲結構為切入點，對基于GPU加速的較小尺寸圖像的批量處理和包含較多算子操作的圖像處理算法中合并存儲結構對加速效果的影響進行了探討分析以及實驗驗證。本文對CUDA編程模型中CUDA流的優勢及其局限性分別進行了論述，并對數據傳輸與核函數執行在GPU上的執行過程進行了分析。根據分析結果以及現有基于GPU加速的圖像處理算法中存在的問題，本文提出了一種適用于GPU的圖像合并存儲結構CSS(Combined Storage Structure)，并對其有效性進行了理論分析。采用非合并存儲結構SEP(SEParate structure)和CSS結構分別實現了基于GPU加速的NDVI提取(Normalized Differential Vegetation Index)提取算法，并對其進行了實驗驗證，對實驗結果進行了歸納總結。

2 相關工作

本節首先對GPU工作隊列(即CUDA流)的優勢及其局限性進行分析；其次對CUDA編程模型中數據傳輸及核函數執行操作進行分解，并分析指出可優化部分；最后針對GPU硬件架構特性以及分析結果提出一種適用于GPU圖像處理算法的數據合并存儲結構，并對該結構在GPU上的有效性進行分析。

2.1 GPU工作隊列

利用GPU實現并行加速的圖像處理算法通常包含以下3個主要執行步驟：

(1)將輸入圖像從主機端(Host)內存傳輸至設備端(GPU)顯存。

(2)核函數在設備端(GPU)執行。

(3)將計算結果從設備端(GPU)顯存傳輸至主機端(Host)內存。

從上述步驟可知，數據傳輸與核函數執行操作是基于GPU的并行優化算法中必不可少的2個重要步驟。由于核函數執行操作通常在算法執行總耗時中占據較大比重，所以在現有的大部分文獻中，重點關注如何對GPU核函數執行部分進行優化。即根據算法本身特性及GPU計算架構的特點來設計性能最優的核函數，從而達到較好的加速效果。此外，針對GPU數據傳輸耗時的優化方法比如零拷貝(Zero-Copy)[6]和Overlap[7]等的應用也取得了一定的加速效果。Zero-Copy是一種將主機端分配的鎖頁內存(Pinned Memory)映射到GPU顯存地址空間的方法，GPU可在需要該內存中數據時自動通過PCI-E總線訪問主機端內存中的數據，而不必手動將數據提前傳輸至GPU顯存。但是，由于所需數據并沒有緩存到GPU顯存中，所以每次訪問該數據都需要重新獲取，因此只適用于數據量較小或數據訪問次數較少的情況。Overlap則是利用CUDA流[3,7-9]實現不同GPU工作隊列的并發執行。不同型號GPU通常擁有數量不等的可連接硬件工作隊列上限，并可以進行顯式設置，而邏輯工作隊列(即CUDA流)則沒有固定數量限制。通過將邏輯工作隊列映射到不同硬件工作隊列，可以重疊數據傳輸與核函數執行操作，在支持Hyper-Q特性的GPU上還可以達到核函數執行之間的重疊，從而減少部分程序執行耗時。如圖 1所示，當批量處理6幅圖像時，可以將每幅圖像的處理操作分配到1個單獨的CUDA流上，在計算資源充足的情況下，數據傳輸與核函數以及不同流上核函數的執行時間軸會出現重疊，從而獲得較高的并行度與較好的加速效果。

Figure 1 Timeline of CUDA streams that executed concurrently圖1 CUDA流并發執行時間軸

雖然CUDA流在邏輯上是相互獨立且可并發執行的GPU工作隊列，但將邏輯工作隊列(即CUDA流)映射到硬件工作隊列時會受到硬件計算資源方面的限制。GPU中包含較多的計算核心(Cores)，主要分為SP(Stream Processor)和SM(Stream Multi-processor)，多個SP可組成1個SM，每個GPU硬件工作隊列包含至少1個SM。當多個邏輯工作隊列映射到同1硬件工作隊列時，這些邏輯工作隊列將會采取分時復用的方式執行。因此，即使創建多個邏輯工作隊列，但當硬件工作隊列不足以同時執行全部邏輯工作隊列時，邏輯上并行執行的工作隊列在物理上仍是串行執行的。如圖 2a所示，假定GPU硬件資源僅支持同時執行3個硬件工作隊列，即使創建邏輯上可并行執行的6個邏輯工作隊列，但未搶占到硬件工作隊列所有權的邏輯工作隊列不得不進行等待，圖2a所示邏輯工作隊列執行時間軸對應的硬件工作隊列執行時間軸如圖 2b所示。此外，在每個硬件工作隊列上需要串行執行的操作中，數據傳輸與數據傳輸之間以及核函數執行與數據傳輸之間存在調用間隙。在這種情況下，算法的實際執行情況并沒有達到圖 1所示的理想效果。

Figure 2 Logical work queue and hardware work queue圖2 邏輯工作隊列與硬件工作隊列

2.2 數據傳輸與核函數執行

由GPU硬件架構及CUDA編程模型的特性可知，每次調用數據傳輸及核函數執行操作都需要對GPU設備進行初始化，即存在固定代價，如DMA引擎設定、起始地址和目標地址的設定、核函數發射等，且固定代價耗時隨設備端操作被調用次數的增加而增加。

CUDA編程模型中主機端與設備端之間單次數據傳輸操作耗時計算方法如式(1)所示。

Ttotal=Tinit+Tcopy

(1)

其中，Tinit是每次數據傳輸執行前的設備初始化耗時，包括前面提到的DMA引擎設定、起始地址設定等，因此為固定代價；Tcopy為數據拷貝耗時，隨拷貝數據量的大小而變化，為非固定代價；Ttotal則代表單次數據傳輸操作的總耗時。

核函數執行操作耗時如式(2)所示：

KTtotal=KTinit+KTlaunch+KTcompute

(2)

其中，KTinit為每次核函數執行操作的初始化耗時，KTlaunch為核函數發射耗時，KTcompute為核函數訪存與計算耗時，KTtotal則代表單次核函數執行操作的總耗時。

與數據傳輸操作的初始化耗時Tinit類似，KTinit為每次核函數執行操作的固定代價，而KTlaunch則隨核函數發射次數的增加而增加，同樣可看作固定代價。KTcompute與核函數取指和訪存次數密切相關，因此為非固定代價。

綜上可知，數據傳輸及核函數執行操作的耗時與其被調用次數緊密相關。當調用次數減少時，操作的固定代價、調用間隙以及執行過程中的非固定代價也會隨之減少，即被調用次數的減少會帶來相應的性能提升。因此，可考慮將較小尺寸的待處理圖像進行合并，進而將數據傳輸及核函數執行操作進行合并，減少操作的調用次數。

2.3 圖像合并存儲結構

在圖像處理領域中，通常將圖像視為數字矩陣傳輸至GPU顯存中進行處理[10,11]。因此，本文提出一種適用于GPU的圖像合并存儲結構(CSS)，如圖 3所示。利用CSS可以將具有相同類型、相同算子、相同或不同大小的圖像進行合并存儲、傳輸及計算。

Figure 3 Combined storage structure of images圖3 圖像合并存儲結構

如前文所述，每次GPU數據傳輸操作都存在固定代價。Tinit在每次數據傳輸操作調用前都會執行，即屬于固定代價且不隨傳輸數據量的大小而改變。而Tcopy不屬于固定代價，因此隨傳輸數據量的增加而增加。當將多次數據傳輸操作進行合并時，固定代價會隨之減少。分別采用SEP與CSS的多次GPU數據傳輸操作總耗時計算方法如式(3)所示：

(3)

其中，n表示待傳輸數據(圖像)的個數；Tinit為單次數據傳輸的初始化操作固定代價；i表示待傳輸的第i個圖像數據；Tcopy(i)則代表數據i的拷貝耗時。由式(3)可以看出，采用CSS結構可以節省數據傳輸操作中的Tinit固定代價，且節省的固定代價大小隨數據傳輸操作合并數量的增加而增加。

GPU核函數執行過程中通常包含較多訪存操作。CUDA編程模型訪存操作采用內存事務(Transaction)[12]的方式實現，而內存事務執行次數與數據在顯存中的分布情況緊密相關。CUDA單次內存事務緩存粒度通常是128字節，即每次緩存連續的128字節數據進緩存區，內存事務操作示意如圖 4所示。由圖 4可知，當將SEP結構的數據合并為CSS結構時，2次內存事務操作也可隨之進行合并。因此，在某些情況下，采用CSS結構可以減少部分內存事務的執行次數。

Figure 4 Transactions of CUDA memory access圖4 CUDA內存事務訪問

此外，當采用CSS結構將待處理圖像進行合并后，GPU算子核函數也可隨之進行合并。如式(4)所示，采用CSS結構后，KTinit固定代價減少，取指次數及內存事務執行次數也有所減少：

(4)

其中，n表示核函數調用次數，通常為待處理數據的個數；Δ為核函數及內存事務的加速比率，Δ≤1，是性能影響因子，隨具體的數據分布情況及GPU硬件資源而變化；i表示待處理圖像數據；KTcompute(i)則表示針對數據i的核函數執行耗時。由式(4)可知，采用CSS結構可以有效減少部分固定代價耗時，提升核函數的執行性能。

綜上所述，利用CSS結構對輸入圖像進行合并可節省GPU數據傳輸及核函數執行操作部分的固定代價及非固定代價，帶來執行性能的提升。且隨著待處理圖像合并數量的增加，帶來的性能提升效果也更顯著。根據上述分析結果，可對GPU算法執行情況進行模擬：假設GPU硬件資源在物理上僅支持2個硬件工作隊列并行執行，當對6幅圖像進行批量處理時，分別采用SEP與CSS結構的GPU算法模擬執行時間軸如圖 5所示。

Figure 5 Timeline for simulation execution圖5 模擬執行時間軸

由式(3)和式(4)可知，采用CSS結構能夠有效減少操作調用間隙及部分固定代價。在圖 5所示的模擬執行時間軸中，采用CSS結構的數據傳輸時間為采用SEP結構等量數據傳輸的時間總和，核函數執行時間為采用SEP結構核函數執行時間的總和，并未考慮固定代價的減少。即便如此，從模擬時間軸上仍可看出CSS結構在加速效果方面取得了一定的提升。

3 實驗對比

3.1 實驗環境

本文實驗環境采用的CUDA版本為9.2，GPU采用NVIDIA GeForce GTX 1060，該GPU搭載了6 GB全局顯存，1 280個CUDA計算核心(Cores)，最高時鐘頻率可達1.67 GHz。本文測試所用圖像為GF1衛星拍攝的遙感影像數據，并根據實驗需求將其裁剪為4000×4000像素的規整大小。測試算法為NDVI提取算法。NDVI是被用來描述植被數量、生長情況和覆蓋狀況等的指標，可以大致反映出植被信息，在遙感影像信息提取中應用廣泛[10,13]。其計算方法如式(5)所示：

NDVI=(NIR-RED)/(NIR+RED)

(5)

其中，NIR和RED分別代表遙感影像的近紅外波段和可見光紅外波段的光譜反射率。

3.2 實驗結果及分析

為了驗證不同圖像合并數量對加速性能的影響，分別采用SEP與CSS結構對數量為8,16,32,64和128的5組單個大小均為4000×4000像素的遙感影像數據在單流和多流情況下進行實驗。

基于SEP與CSS結構實現的NDVI提取算法單流實驗結果如圖 6所示，實驗執行時間軸示意可參見圖 5所示的模擬執行時間軸。由圖 6可知，在單流的情況下，采用CSS結構的NDVI提取算法執行耗時皆少于采用SEP結構的NDVI提取算法的，與式(3)和式(4)的分析結果一致。

Figure 6 Test results of single stream圖6 單流實驗結果

當利用GPU進行批量圖像處理時通常采用CUDA流進行優化，多流的優勢及其局限性已在前文中進行了討論。為了測試CSS結構在多流上的應用，本文實驗將GPU硬件工作隊列最大可連接數(即可并行執行硬件工作隊列數)限制為4，采用同樣的5組數據進行實驗，將每組數據平均分配到每個硬件工作隊列中，并利用CSS結構將其合并。多流情況下的實驗執行時間軸可參見圖 5，實驗結果如圖 7所示。

Figure 7 Test results of multiple streams圖7 多流實驗結果

由圖 7可知，多流情況下采用SEP與CSS結構的算法執行耗時均少于圖 6所示的單流情況下的算法執行耗時，表明多流具有更好的加速效果。與單流情況相比，多流情況下采用CSS結構的NDVI提取算法與采用SEP結構的NDVI提取算法相比取得了更好的執行性能。且隨著圖像合并數據的增加，采用CSS結構所取得的加速效果與采用SEP結構所取得的加速效果相比有更大的提升。

綜上所述，單流和多流情況下采用CSS結構實現的NDVI提取算法執行性能均優于采用SEP結構實現的NDVI提取算法的，這證明了所提CSS結構在GPU上的有效性。在多流情況下，采用CSS結構獲得的加速效果更加明顯，且隨著圖像合并數量的增加，加速效果也隨之提升，顯示了CSS結構的可擴展性。

4 結束語

由于GPU顯存容量的限制，部分基于GPU實現的圖像處理算法通常需要對輸入的較大尺寸圖像進行分塊、分批次處理。但是，針對利用GPU加速較小尺寸圖像批量處理的研究則較少，通常采用循環復用方法進行處理，存在GPU資源利用率較低等問題。本文從基于GPU實現的圖像處理算法的存儲結構出發，通過對CUDA編程模型在執行過程中的2個主要耗時操作進行分析，提出了一種適用于GPU圖像處理算法的合并存儲結構。并以基于GPU實現的NDVI提取算法為例，對多組圖像進行批量NDVI提取實驗，驗證了所提存儲結構在GPU上的有效性及可擴展性。

從本文實驗結果可知，所提的CSS結構在GPU上的適用性、有效性及可擴展性均得到了驗證。由于本文實驗僅考慮了存儲結構對執行時間的影響，且實驗中采用的算法為復雜度較低的點運算算法，因此所取得的加速效果并不十分顯著，但為GPU圖像處理的優化研究提供了新的思路及理論證明。下一步工作將對本文方法做進一步實驗及完善，針對CSS結構在不同情況下的合并策略及其瓶頸問題進行研究，并以本文方法為基礎嘗試提出一個基于GPU的遙感影像動態劃分(分割/合并)處理模型。