采用SIMT結構GPU的二維離散哈爾小波變換的優化

李一芒，孫鳳全

(常州大學 機械工程學院，江蘇 常州 213000)

0 引言

與傅里葉變換相比，小波變換能夠通過低通濾波器和高通濾波器將圖像的基本信息與變化信息、邊緣信息分離開來，并且由于小波變換具有緊支撐的性質，即取值在某一區間內為常數，在此區間外為0，使得能量較為集中，能夠反映局部信息的變換，因此被應用于圖像處理領域。作者在研究夜間圖像檢測過程中，將小波變換應用于圖像融合，根據選擇小波變換的四項原則，即正交、線性相位、連續、緊支撐[1]，選擇了二維離散哈爾小波變換，但是在CPU環境下運行需要耗費大量資源，實時性存在問題，為方便后續研究，本文對GPU環境下的二維離散哈爾小波變換進行了研究。

GPU(graphic processing unit)最初是一種圖形處理器，后來根據人們的需要被用作并行計算的處理器，對于GPU下的小波變換已有許多，例如文獻[2]在偽代碼層面添加滑動窗口機制處理大數據流；文獻[3]將數據進行全局劃分，實現小波變換；文獻[4]通過改寫寄存器文件結構，提升SIMD結構數據處理速度；文獻[5]將MPI技術和GPU結合；文獻[6]將數據分成奇數塊和偶數塊進行處理；文獻[7]基于晶格結構提出了新的離散小波算法。本文采用了一種正在發展中的新架構SIMT(單指令多線程)，在它本身配套的CUDA C算法平臺上進行實現，將二維離散小波變換對應到線程，進行并行公式推導，并且通過調整GPU的邏輯布局、同步設置、內存優化，實現性能的提升，比SIMD架構GPU效率可提升16.3%，比CPU效率可提升51.1%。

1 相關理論基礎

計算機架構根據指令和數據進入CPU的方式分為單指令單數據(SISD)、單指令多數據(SIMD)、多指令單數據(MISD)、多指令多數據(MIMD)，其中SIMD、MIMD以及后來出現的SIMT就是GPU中的數據并行結構體系[8]。SIMT架構的概念最早由NVIDIA公司在2008年于文獻[9]中提出，SIMD架構是傳統的數據并行結構，區別如圖1所示。

圖1 SIMT架構與SIMD架構圖

如圖1(右)所示，在SIMD結構中，數據被打包成一個向量，具體的數量取決于有多少個SP(流處理器)，這就是GPU處理大量數據快的原因，也是并行計算[10]的基礎。但是并不是所有數據都適合向量化，為了追求速度，著色程序越來越長，并且因為向量化所產生的代碼量巨大，需要類似于內存對齊[11]這樣的操作，對編譯器的負荷巨大。

如圖1(左)所示，區別于SIMD結構GPU的是，在SIMT結構GPU中，多了線程的概念。將一個數據就存放在一個線程內，也就有了對應的地址，這樣就可以對單個數據進行操作，為了滿足并行的要求，SIMT將32個線程組合成一個線程束[12]。一個線程束里的數據同時只能響應一個命令，如果其中部分線程需要響應其他命令，那么這部分線程進入非活躍狀態，等活躍線程執行完再執行。這樣的執行方式從某方面來講和SIMD結構GPU將數據向量化存在相似[13]，因此SIMT結構是在SIMD的結構基礎上設計出來的。

圖2 GPU邏輯架構

SIMT結構對比SIMD結構的優勢在于不需要考慮數據向量化、內存對齊的事情，并且它最小并行的數據寬度為32，遠小于SIMD，所以它對于數據的處理更加高效且靈活，同時，指令和數據的調度編譯[14]工作更加簡單。在本文的實驗中，SIMT架構的GPU比SIMD架構的GPU快上19.5%。

2 SIMT結構下的小波變換

2.1 SIMT結構GPU的邏輯架構

SIMT結構以線程為基礎，統一的存在一個網格(grid)內，網格內包含若干線程塊(block)，線程塊內包含若干線程(thread)，每個線程都有一個輸入數據，這些線程會被分配相對應索引號，通過索引號可以操縱數據，GPU會根據網格和線程塊的維度分配相應維度坐標，類似于矩陣坐標。

網格的維度和線程塊的維度是由我們自行指定的，可從一維設置到三維，這里以二維結構來設置一個矩陣為例，則邏輯結構如圖2所示。

2.2 二維離散小波變換的并行公式推導

設圖像矩陣A中的元素為ai,j，βi,j、γi,j、δi,j、ζi,j分別為矩陣C、D、E、F的元素，則經過推導可得：

(1)

(2)

(3)

(4)

接下來根據式(1)～(4)將數據分配進線程。根據圖(2)可知,線程塊ID以列優先的方式分配，線程的ID以塊為單位，在每個塊中再按列優先分配ID，線程ID在其所在的塊內為獨有。矩陣的數據存儲進線程的時候不按塊為單位，根據全局的線程按照列優先進行存儲。設圖像矩陣AM×N中的元素為ai,j，線程矩陣中的元素為μi,j，BH×I的線程塊矩陣中的元素為νi,j，則推導可得：

ai=μi+H·νi

(5)

aj=μj+I·νj

(6)

在實際存儲形式中，數據按照一維數組的形式進行存儲，GPU在訪問全局內存[16]的時候也是直接訪問數據的全局內存索引，因此需要找到全局內存索引和矩陣坐標的關系，在這里要注意的是和矩陣數據存儲原則不同，全局內存索引的分配按照行優先原則而并非是列優先原則。設全局內存索引為S，根據式(5)、式(6)可推得全局內存索引和矩陣元素關系為：

S=ai+aj·M

(7)

首先按行方向對圖像矩陣的列進行變換，需要知道數據取出位置和數據存儲位置。設變換后數據取出位置的全局內存索引為SO1，SO2，根據式(7)可推得：

SO1=2ai+aj·M

(8)

SO2=2ai+aj·M+1

(9)

而數據的存儲位置由于式(8)、式(9)推導過程中為了先對應均值塊，使得有些索引超出了界限，而如果均值塊處理后的數據存儲位置索引按行方向只取前M/2個索引，而細節塊處理的數據存儲位置的索引由均值數據索引向右M/2個偏移量則可解決。設變換后數據存儲位置的全局內存索引為SI1，SI2則可推得：

SI1=S=ai+aj·M

(10)

SI2=ai+aj·M+M/2

(11)

其次按列方向對圖像矩陣的行進行變換，和列變換存儲位置相似，均值塊處理后的數據存儲位置索引按列方向只取前N/2個索引，細節塊處理的數據存儲位置索引由均值數據索引向右偏移M2/2個偏移量[17]。設變換后數據取出位置的全局內存索引為SO1，SO2，數據存儲位置的全局內存索引為SI1，SI2，則可推得：

SO1=2aj·M+ai

(12)

SO2=(2aj+1)·M+ai

(13)

SI1=S=ai+aj·M

(14)

SI2=S=ai+aj·M+M2/2

(15)

至此，完成了二維離散哈爾小波變換的并行公式推導。

3 GPU的進一步優化

3.1 更改尋址方式

由于在運行一個進程的時候，所需要的內存大小其實會超過實際的內存[18]大小，因此會通過分頁的方式，整合計算機的存儲資源，映射出一個超過物理內存大小的虛擬內存[19]，需要數據的時候通過頁和頁幀將數據調度進物理內存中進行操作。CPU與GPU傳輸數據也需要用到虛擬內存，其關系流程如圖3所示。

圖3 GPU與CPU數據流通流程圖

如圖3左所示，數據邏輯上存放于虛擬內存，通過虛擬地址將數據調度進入CPU的物理內存中，CPU和GPU的物理內存通過總線互聯傳遞數據，GPU再將數據存放于GPU的虛擬內存中，等到使用的時候進行調度，送入TPC(處理器)[20]中進行處理，經過ROP(顏色處理單元)輸出結果到GPU虛擬內存中，需要被傳輸的數據通過虛擬地址將數據調度進GPU物理內存，傳輸給CPU物理內存，再將數據存放進CPU虛擬內存中[21]。

這種模式會產生一些不必要的開銷，可以看到在這過程中數據在被不停的復制、映射，而這些是由于尋址方式造成的，因為host端與device端開辟的空間地址不統一，互相不能直接進行數據的存取，所以本文在這里采用虛擬內存統一尋址的方式，使得GPU虛擬內存和CPU虛擬內存的虛擬地址統一，此時GPU就可以直接從CPU的物理內存中取用數據了，簡化了代碼，減少了不必要開銷，便于后續處理。

3.2 調整邏輯布局

要找到能夠處理大分辨率數據速度最快的邏輯布局，就必須從數據在SIMT結構GPU中被處理的底層邏輯上去尋找，否則每一個邏輯布局都去嘗試根本就是無法做到的。數據的存儲在實際的硬件中是以一維的方式存儲的，但是SM(流式多處理器)處理數據的最小執行單元并不是線程，在數據處理的過程中，線程束才是SM中基本的執行單元。當一個內核被啟動時，網格塊中的線程塊會被分配到某一個SM上，這些線程塊里的線程就會分成多個線程束，在一個線程束中，所有被分配到線程上的數據都會執行這一個線程束被分配到的指令，目前每個線程數是以32個線程為一組的，一個線程束就能夠同時對32個數據執行同一個命令，而在命令分配的時候，多個線程束會分配到同一個命令，同時，一個命令最小能夠處理的數據只有32個，也使得在實際的并行處理中能夠更加的靈活，這就是SIMT結構GPU性能更加優越的原因。

而線程束的存在使得數據處理速度變快的同時，也會帶來一個問題，同一個線程束內的32個線程在每個周期內必須執行相同的指令，如果產生了沖突，例如一個線程束內的16個線程需要執行某一條指令，另外16個線程需要執行另一條指令，此時，線程束會先選擇其中的一條指令進行處理，同時禁用不執行這個命令的其他線程，這樣就會產生線程束分化，而這些被禁用的線程依舊在消耗寄存器資源，就會使得數據處理速度下降，線程束分化的越嚴重，性能下降越大，并行性削弱也越嚴重。

要避免線程束分化，除了在偽代碼層面要避免之外，在構建邏輯布局的時候就要合理，并且邏輯布局中的線程數量越多，會增加數據處理的速度。因此，在嘗試建立不同的邏輯布局時，應該根據線程束的特性來構建網格塊和線程塊的維度，而這只是建立在理論上，在實際的處理過程中，理論上性能優越的邏輯布局可能會由于多方面因素影響使得數據處理速度達不到期望值。例如，理論上線程數量越大的邏輯布局應當能夠提升數據處理速度，但是在實際操作過程中，一個512×512的圖片應用線程塊為64×1，網格塊16×1 024的邏輯布局時，不僅在處理速度上沒有線程塊為16×1，網格塊16×512的邏輯布局塊，還出現了數據處理不完全的情況，導致圖片數據重建出來之后有些部分還是原圖片。這一現象在大量的實驗中間歇性的出現在邏輯布局的線程數遠超過圖片像素的情況下，并且當邏輯布局的維度出現奇數，例如線程塊為35×1，網格塊15×1 024這樣的布局時，這樣的現象出現的次數變得更加頻繁。

因此，需要通過大量的實驗找出能夠提升大分辨率圖像數據處理速度的，并且是通用的邏輯布局，同時還要避免為了追求處理速度而不斷增加線程數量，從而導致數據處理不完全的邏輯布局。而為了避免上文線程束分化的問題，將線程塊和網格塊的橫坐標方向維度定為了16、32、64、128，同時，為了提升數據處理速度，要盡量的增加邏輯布局中的線程數量，在實際的實驗過程中，將網格塊的縱坐標維度和圖像的分辨率大小保持一致的時候數據的處理速度比較塊，并且不會出現數據處理不完全的情況。表1挑選了對于不同的邏輯布局下處理一份完整的圖像數據的實驗中，比較有代表性的實驗數據。

表1 不同邏輯布局下數據處理時間 ms

根據表1可以看出，不同的邏輯布局對于不同分辨率圖片的處理速度提升效果不一樣，對于256×256的圖片，線程塊為64×1，網格塊16×1 024的邏輯布局的線程數量不是最多的，卻是數據處理速度最快的，但是這種大線程量的邏輯布局并不適合256×256分辨率的圖片，因為在實際的處理過程中出現了數據處理不完全的情況。結合數據處理速度和數據處理完整度，線程塊為16×1，網格塊16×256的邏輯布局是最適合256×256分辨率的圖片的。同時可以看出，隨著圖像分辨率的增大，線程塊為64×1，網格塊16×1 024的邏輯布局的數據處理速度一直是比較快的，雖然在實際處理過程中應用在小分辨率圖像上時會出現數據處理不完全的狀況，但是應用在大分辨率圖像的處理過程中，數據處理速度是最快的，并且也不會出現數據處理不完全的情況，因此，通過大量的實驗之后，本文對于大分辨率圖像的處理應用線程塊為64×1，網格塊16×1 024的邏輯布局。

3.3 數據分割及改變數據同步方式

與CPU的同步特性不同，核函數的調用與主機是異步的，當完成核函數調用的指令之后，會立即返回，不管運算是否完成，因此CUDA有一個專門的函數是等核函數執行完再進行下一步運算。

基于不同的同步特性，在進行圖像的小波變換處理時，通常情況下是將所有數據全部進行小波變換行處理之后，再進行小波變換列處理，接著將處理完成的數據取出進行需要的圖像重建之類的工作。這樣的方法在圖像數據量較小的情況下是沒有問題的，但是在圖像數據量比較大的時候，就會拖慢數據處理速度。為了改進這個缺點，提高數據處理效率，對這個同步過程進行了分析。這個過程簡單來看就是取出數據、行方向變換、列方向變換、圖像重建四步，而根據GPU處理數據的速度來看，等待數據全部處理完成再進行下一步是比較浪費資源的，這也是在處理大分辨率數據時速度會比較慢的原因，因此，在這里進行了一個數據的分割之后再進行處理，具體流程為：取出第一份數據進行并行計算，在完成第一份數據的并行行計算后，對第一份數據進行并行列計算的同時，取出第二份數據進行并行行計算；在第一份數據完成并行列計算后，將數據放入上文提到的虛擬地址當中；CPU從虛擬地址中取出第一份數據進行圖像重建等操作的同時，第二份數據完成并行行計算，開始進行并行列計算。循環這個過程直到所有數據完成處理。

對于圖像數據的分割，需要注意的是在分割的時候是否會造成圖像數據的損壞，造成圖像特征信息的丟失。本文對圖像數據進行分割的時候只是為了將大量數據分成幾份，使得每次處理的數據量減小，從而加快數據處理速度，因此這里的分割只是數據量上的分割，不會造成信息的損壞以及特征的丟失問題。將圖像數據分割不同的份數時，會獲得不同的運行效率，也會出現不同的問題，而根據上文確定的二維線程塊邏輯布局，如果分割出的數據量是2的偶數倍的時候應當獲得最大的運行效率，如果分割出的數據量是2的奇數倍的時候則有可能會出現運行效率反而降低的情況。因此，在同一個硬件基礎上，本文將不同分辨率圖像各自分成不同的份數，進行對比實驗，如表2所示。

表2 不同分辨率下切割成不同份的數據處理時間 ms

根據表2可以看出，圖像分辨率較小的圖片，由于本身的數據處理時間就比較小，因此這種切割數據，改變同步方式的方法的提升效果并不是很明顯，只有根據減少的時間相對于原始處理時間的比例可以看出還是有些較好的提升效果的。隨著圖片分辨率的提高，原始處理時間基數的增大，效果也變得逐漸明顯，而比較1 024×1 024和2 048×2 048兩個分辨率的實驗結果可以看出，分辨率越大，提升效果雖然越大，可是相對于原始處理速度，提升的幅度在降低，不過提升的幅度也能達到22%，所以切割數據的方法效果還是較為顯著的。

比較1 024×1 024和2 048×2 048兩個大分辨率下不同切割份數的效果可以看出，隨著切割份數的增多，數據的處理時間不斷減小，但是并不是切割份數越多越好，從表2中可看到切割成6份時的處理時間不僅沒有減少，反而多于切割成4份時的處理時間，切割成10份的處理時間多于切割成8份的處理時間，因此，將數據切割成2的偶數倍份數是比較合理的，通過對比實驗可以得出，切割成8份是效果最好的。

4 實驗結果及分析

對于不同的環境，將數據分割所帶來的處理速度的提升幅度是一致的，因此只要比較一份完整的數據在哪種環境下處理速度最快，那么將數據分割后的數據處理速度也一定是最快的，因此，本文在CPU環境、SIMD結構的GPU、SIMT結構的GPU下分別對不同分辨率的同一張圖片，對二維離散哈爾小波變換的運行時間進行了對比試驗。這里所用的CPU芯片型號為AMD Ryzen 7 5800H，SIMD架構的顯卡型號為AMD的Radeon RX 6000，SIMT架構的顯卡型號為NVIDIA的GeForce RTX 3060，表3列出了不同分辨率在不同環境中的速度，以及是否經過優化的速度。

表3 不同分辨率下的小波變換運行時間 ms

單獨從小波變換的運行時間來看，從表3中可以看出，圖片在小分辨率時，CPU環境下最快運行速度和GPU是相差不大的，隨著分辨率的增大，GPU的優勢越來越明顯，而優化后的GPU程序相對于CPU在2 048×2 048時提升幅度最大，為90.3%，相對于原始GPU程序的提升保持在40%以上，從架構上來看，SIMT架構的GPU比SIMD架構的GPU最大快19.5%左右。

考慮到整個過程是包含圖像數據的讀取、GPU加載數據時間、小波變換計算時間以及內存讀取結果并重建成圖像的時間。因此表4比較了CPU環境下最快運行速度的運算以及GPU環境下最快運行速度的情況。

算上總體時間后，在圖片分辨率大于512×512之后，GPU的優勢就已經體現的較為明顯，分辨率大于1 024×1 024之后，SIMT架構的GPU的優勢也展現出來了，根據表4的數據，SIMT架構對比SIMD架構的提升幅度最大為16.3%。SIMT架構GPU對比CPU最大提升幅度為51.1%，提升幅度沒有只計算小波變換時間的幅度大，因為GPU計算是有部分操作要先在CPU里做，提升的只有數據送進GPU里之后的運行速度，從時間上來看，已經能夠達到實時處理的目的。

表4 不同尺寸的整體運行時間 ms

5 結束語

針對大分辨率圖像處理實時性不足的問題，本文通過GPU有大量可編程核心的特點，采用了SIMT結構的GPU對小波變換進行并行公式推導，通過大量的實驗，找出了SIMT結構GPU下，對于大分辨率圖像處理速度最快，并且不會出現數據處理不完全情況的邏輯布局，在這種邏輯布局下，進一步的將數據分割，改變了數據處理的同步方式，通過實驗對比得出，針對大分辨率圖像，將數據分割成8份是處理速度最快的，同時改變了內存的尋址方式，通過虛擬尋址進一步提高了數據處理速度，并簡化了偽代碼，在整體上提高了小波變換的運行效率。同時，實驗通過對一份完整的大分辨率圖像數據，比較了CPU環境下的串行算法和SIMT、SIMD架構的GPU環境下的并行算法以及優化后的算法，表明了在小波變換計算的效率上，隨著分辨率的增加，SIMT結構GPU相對于CPU效率最大可到90.3%，SIMT比SIMD架構的GPU效率高19.5%，優化后的程序比優化前的效率隨著分辨率增大最大可提升47.4%。在整個完成過程，包含了數據讀取、數據加載、小波變換以及內存讀取并重建圖像的時間上，SIMT結構GPU相對于CPU效率提升最大可到51.1%，SIMT比SIMD架構的GPU效率高16.3%，表明了SIMT結構GPU具有優越性，并且達到了實時處理的目的，同時，本方法也可移植于同類問題。