基于GPU通用計(jì)算的并行算法和計(jì)算框架的實(shí)現(xiàn)

朱宇蘭

泉州醫(yī)學(xué)高等專科學(xué)校，福建泉州362000

?

基于GPU通用計(jì)算的并行算法和計(jì)算框架的實(shí)現(xiàn)

朱宇蘭

泉州醫(yī)學(xué)高等?？茖W(xué)校，福建泉州362000

摘要：GPU通用計(jì)算是近幾年來(lái)迅速發(fā)展的一個(gè)計(jì)算領(lǐng)域，以其強(qiáng)大的并行處理能力為密集數(shù)據(jù)單指令型計(jì)算提供了一個(gè)絕佳的解決方案，但受限制于芯片的制造工藝，其運(yùn)算能力遭遇瓶頸。本文從GPU通用計(jì)算的基礎(chǔ)——圖形API開(kāi)始，分析GPU并行算法特征、運(yùn)算的過(guò)程及特點(diǎn)，并抽象出了一套并行計(jì)算框架。通過(guò)計(jì)算密集行案例，演示了框架的使用方法，并與傳統(tǒng)GPU通用計(jì)算的實(shí)現(xiàn)方法比較，證明了本框架具有代碼精簡(jiǎn)、與圖形學(xué)無(wú)關(guān)的特點(diǎn)。

關(guān)鍵詞：GPU通用計(jì)算；并行計(jì)算；計(jì)算框架

GPU通用計(jì)算技術(shù)作為一種新興的計(jì)算技術(shù)正在處理器架構(gòu)的領(lǐng)域掀起一場(chǎng)不小的革命。由于不同計(jì)算核心之間相互配合的效率問(wèn)題、散熱問(wèn)題、成本問(wèn)題等對(duì)于GPU的計(jì)算能力都形成了限制。GPU通用計(jì)算的出現(xiàn)在一定程度上解決了這個(gè)問(wèn)題，不同于CPU的單核或多核架構(gòu)，GPU的架構(gòu)是天生眾核的，即使是消費(fèi)級(jí)的低端顯卡，其中的處理器核心數(shù)目也是成千上萬(wàn)的。通常通過(guò)使用圖形API來(lái)發(fā)揮GPU的強(qiáng)大并行計(jì)算能力，這種計(jì)算需要有極為扎實(shí)的圖形學(xué)功底，因此需要對(duì)OpenGL或DirectX有很深厚的認(rèn)識(shí)。這在很大程度上限制了GPU通用計(jì)算的發(fā)展速度。

1　并行計(jì)算框架的設(shè)計(jì)

1.1計(jì)算過(guò)程設(shè)計(jì)

GPU通用計(jì)算的關(guān)鍵在于通過(guò)紋理映射實(shí)現(xiàn)科學(xué)計(jì)算。紋理映射在原有的圖形渲染管線中的作用是通過(guò)為多邊形貼圖的方式實(shí)現(xiàn)逼真的效果，這是一種不需要增加模型復(fù)雜度就能提升渲染真實(shí)感的一種搞笑的做法。而GPU通用計(jì)算正式利用了GPU對(duì)于紋理映射操作處理高效的特點(diǎn)，使用紋理存儲(chǔ)和輸出數(shù)據(jù)，使用紋理映射的過(guò)程來(lái)實(shí)現(xiàn)科學(xué)計(jì)算［1］。

在GPU中，紋理是以緩存的形式存在的，GPU實(shí)現(xiàn)了紋理坐標(biāo)的差值、轉(zhuǎn)換和采樣的過(guò)程。紋理的處理是并行計(jì)算框架的關(guān)鍵，在本文描述的并行框架中，計(jì)算將圍繞著紋理映射展開(kāi)［2］。GPU通用計(jì)算技術(shù)的實(shí)現(xiàn)憑借的是GPU圖形流水線強(qiáng)大的大規(guī)模并行處理能力，海量的頂點(diǎn)流經(jīng)相同的流水線成為屏幕上的像素。根據(jù)本文的設(shè)計(jì)，計(jì)算框架的計(jì)算過(guò)程大致可描述為如下5個(gè)步驟。

1.1.1將輸入寫入到紋理并行計(jì)算框架最終是通過(guò)CPU來(lái)進(jìn)行調(diào)度的，得到的結(jié)果也需要由CPU從內(nèi)存中獲得，因此不同于傳統(tǒng)圖形流水線輸出到屏幕，在計(jì)算框架中，需要將渲染的結(jié)果輸出到顯存，在這里我們采用紋理作為接受輸出的載體，具體的實(shí)現(xiàn)技術(shù)是通過(guò)幀緩存將紋理鏈接起來(lái)［3］。1.1.2設(shè)置投影與視圖矩陣在三維渲染的過(guò)程中，投影與視圖矩陣用于實(shí)現(xiàn)模型的位移、旋轉(zhuǎn)、縮放，以及控制攝像機(jī)的屬性。其硬件實(shí)現(xiàn)的實(shí)質(zhì)是通過(guò)這兩個(gè)矩陣將輸入的頂點(diǎn)坐標(biāo)進(jìn)行仿射變換，從而達(dá)到具有遮擋和近大遠(yuǎn)小關(guān)系的逼真效果。而對(duì)并行計(jì)算而言，每個(gè)像素的值是不具有圖像意義的實(shí)際數(shù)據(jù)。是不能對(duì)其任意縮放和位移的。因此，我們?cè)谶@里需要使用正交投影。將投影平面的長(zhǎng)寬分別設(shè)置為目標(biāo)紋理的長(zhǎng)寬，將視圖矩陣設(shè)置為單位矩陣。

1.1.3視口設(shè)置視口即在Open GL中定義的觀察模型的窗口，同時(shí)也是投影平面上的可見(jiàn)部分。在三維渲染的過(guò)程中，視口的大小可以理解為一個(gè)房間窗口的大小，無(wú)論窗口是什么樣子的，看到的外面的風(fēng)景都是真實(shí)的，但是在通用計(jì)算中，視口無(wú)論放大還是縮小都會(huì)使數(shù)據(jù)失真。視口必須設(shè)置為與紋理圖等大小，且必須與投影平面對(duì)齊。視口設(shè)置的API為gl View Port（0，0，width，height），該接口的作用是設(shè)置與投影平面對(duì)齊且等大的視口［4］。

1.1.4繪制矩形實(shí)現(xiàn)計(jì)算繪制一個(gè)與紋理圖等大小的矩形，四個(gè)頂點(diǎn)的紋理坐標(biāo)分別設(shè)置為紋理的四個(gè)頂點(diǎn)，即（0，0），（0，1），（1，1），（1，0）。由于矩形的大小與貼圖完全相同，這也就保證了紋理圖中的每個(gè)像素都得到了覆蓋，映射的比例是1：1，這種映射的方式等同于數(shù)據(jù)的復(fù)制，在接下來(lái)的過(guò)程中，紋理中的每個(gè)像素會(huì)被讀取到流水線的入口，進(jìn)入頂點(diǎn)著色器，繼而為每個(gè)片段著色為對(duì)應(yīng)的像素。在這里我們既可以使用單位化的紋理坐標(biāo)。即取值在0～1之間的紋理坐標(biāo)，可以使用非單位化的紋理坐標(biāo)，根據(jù)GPU支持情況的不同可以自行選擇。

1.1.5讀回?cái)?shù)據(jù)經(jīng)過(guò)繪制過(guò)程之后，渲染的結(jié)果就已經(jīng)存儲(chǔ)在了顯存的紋理之中，這時(shí)可以通過(guò)gl Read Buffer、gl Read Pixel等函數(shù)將數(shù)據(jù)讀回內(nèi)存。本文描述的計(jì)算框架中將會(huì)封裝讀取數(shù)據(jù)的步驟，如果計(jì)算的結(jié)果不是最終結(jié)果，紋理即可以作為中間變量繼續(xù)參與下一步的計(jì)算，如果紋理已經(jīng)是最終結(jié)果，則可以通過(guò)框架的輸出函數(shù)予以取回。

1.2GPU存儲(chǔ)接口設(shè)計(jì)

框架的存儲(chǔ)結(jié)果是通過(guò)對(duì)顯存的紋理進(jìn)行封裝來(lái)實(shí)現(xiàn)的。紋理可以理解為一張查找對(duì)應(yīng)顏色的取色板，通過(guò)頂點(diǎn)的紋理坐標(biāo)既可以從紋理中找到對(duì)應(yīng)的像素顏色。紋理在顯存中的存儲(chǔ)格式與幀緩存是類似的，都是由離散的像素構(gòu)成。由于紋理坐標(biāo)都是經(jīng)過(guò)差值計(jì)算得到的，因此取到的顏色并非離散，而是通過(guò)周圍像素差值得到的或者是采用最鄰近元素得到的［5］。將紋理看做是連續(xù)的數(shù)組更為恰當(dāng)，二維坐標(biāo)是在實(shí)數(shù)域內(nèi)定義的。

紋理坐標(biāo)分為單位化與未單位化兩種。單位化的紋理坐標(biāo)范圍在0～1之間，這樣即使在渲染的時(shí)候不知道紋理的大小也能夠正確的指定出正確的紋理坐標(biāo)。但是對(duì)于GPU通用計(jì)算而言，這種做法卻打破了紋理作為數(shù)據(jù)存儲(chǔ)容器本身的便利性。因此，本框架在對(duì)存儲(chǔ)單元的封裝中為用戶提供了非單位化的數(shù)據(jù)存取接口，用戶可以直接通過(guò)數(shù)據(jù)的下標(biāo)訪問(wèn)到紋理中的特定數(shù)據(jù)。

1.3框架管理接口設(shè)計(jì)

除了函數(shù)與存儲(chǔ)單元這兩個(gè)計(jì)算用單元之外，還會(huì)有一些其他的輔助部分用于框架的實(shí)現(xiàn)與運(yùn)行，由于傳統(tǒng)的GPU通用計(jì)算中需要有大量的功過(guò)用于圖形API的初始化，兼容性檢查，Open GL對(duì)象的生成、管理與刪除等工作，所以框架管理類是非常必要的設(shè)計(jì)［6］。

表1　框架管理類接口列表Table 1 Interface list of framework management class

2　并行計(jì)算框架的實(shí)現(xiàn)

2.1GPU函數(shù)的實(shí)現(xiàn)

計(jì)算單元的功能類似于CPU程序里面的函數(shù)，不同的是，這里的計(jì)算單元是完全并行計(jì)算，并且在GPU上運(yùn)行的。由于其與Open GL中Shader的相關(guān)性。確定Gpu Function的輸入與輸出。由于圖形管線的末端是FBO，最后的計(jì)算結(jié)果是作為一張二維紋理貼圖的形式從FBO上讀取出來(lái)的，因此，在這里我們限定Gpu Function的輸出是一個(gè)二維數(shù)組［7］。由于二維數(shù)組和三維數(shù)組的實(shí)質(zhì)是紋理貼圖，根據(jù)GPU的限制，使用的最大數(shù)組數(shù)目是8個(gè)，因?yàn)橛?jì)算的中間結(jié)果作為GPU中的存儲(chǔ)是不會(huì)與內(nèi)存發(fā)生交換而耗費(fèi)時(shí)間的。因此這里應(yīng)該通過(guò)多次的計(jì)算來(lái)達(dá)到相同的目的。為了使GPU函數(shù)的運(yùn)算過(guò)程更加類似于CPU，并且減少誤操作的概率，Gpu Function的賦值操作是在實(shí)際運(yùn)算之前發(fā)生的。用戶可以在計(jì)算之前的任何時(shí)間為Gpu Function添加參數(shù)。但實(shí)際賦值過(guò)程會(huì)與運(yùn)算緊鄰發(fā)生。這里是通過(guò)為Gpu Function添加了參數(shù)隊(duì)列實(shí)現(xiàn)的。

2.2存儲(chǔ)單元的實(shí)現(xiàn)

為了盡可能避免出現(xiàn)圖形學(xué)中的內(nèi)容，本框架將存儲(chǔ)結(jié)構(gòu)由傳統(tǒng)的紋理封裝為與CPU數(shù)組具有相似特性的GPU數(shù)組，分為GPU二維數(shù)組（Gpu Array2D）類以及GPU三維數(shù)組（Gpu Array3D）兩個(gè)部分，這兩個(gè)部分都繼承自GPU數(shù)組（Gpu Array）類。Gpu Array實(shí)質(zhì)是對(duì)紋理存儲(chǔ)單元的封裝。包含一個(gè)GLuint類型的變量textureId。該變量是在Gpu Array實(shí)例化的初期賦值的，其值代表了對(duì)應(yīng)紋理的紋理Id。

2.3框架管理器的實(shí)現(xiàn)

計(jì)算框架的封裝是整個(gè)實(shí)現(xiàn)過(guò)程最核心的部分，計(jì)算框架管理類是控制整個(gè)計(jì)算框架的核心，計(jì)算框架的管理是通過(guò)Framework Manager類來(lái)實(shí)現(xiàn)的。該類的實(shí)現(xiàn)借鑒了Open GL狀態(tài)機(jī)的實(shí)現(xiàn)方式，對(duì)其內(nèi)部的資源進(jìn)行統(tǒng)一的管理。Framework Manager類包含一個(gè)Gpu Object指針類型的數(shù)組［8］。Gpu Object類是所有在該框架中適用的類的基類，在該框架中實(shí)現(xiàn)的所有的類都是從Gpu Object類派生而來(lái)的。該類的結(jié)構(gòu)如下所示：

Class Gpu Object；

public：static const int Gpu Class Serial Id=0；

public：int Gpu Object Serial Number；

該類包含兩個(gè)主要屬性，分別為靜態(tài)整型常量Gpu Class Serial Id以及整數(shù)類型屬性Gpu Object Serial Number。

3　體渲染在框架上的實(shí)現(xiàn)

體渲染是一種將離散的三維數(shù)據(jù)集投影到二維平面的繪制技術(shù)。選用該算法對(duì)框架的實(shí)現(xiàn)進(jìn)行驗(yàn)證，運(yùn)行的過(guò)程中，GPU充當(dāng)?shù)氖遣⑿袛?shù)據(jù)處理的角色，計(jì)算得到的結(jié)果通過(guò)寫入到文件來(lái)呈現(xiàn)。典型的三維數(shù)據(jù)是CT或者核磁共振得到的一組二維切面圖像，這種三維數(shù)據(jù)的渲染可以通過(guò)提取等值曲面渲染的方式或者是直接渲染體素的方式渲染。其中，Ray-casting算法是體渲染最簡(jiǎn)單的實(shí)現(xiàn)方法，目標(biāo)圖像的每一個(gè)像素都作為一道垂直于平面的射線穿透體素?cái)?shù)據(jù)。在穿透體素?cái)?shù)據(jù)的過(guò)程中，射線會(huì)累積體素的顏色信息，并累加，最終成為該點(diǎn)的顏色信息。如圖1既是高質(zhì)量體渲染得到的人顱骨體素信息的渲染效果。

通過(guò)使用本文設(shè)計(jì)實(shí)現(xiàn)的框架來(lái)實(shí)現(xiàn)光線投射算法的體渲染。使用GPU三維數(shù)組來(lái)存儲(chǔ)體素?cái)?shù)據(jù)，使用GPU二維數(shù)組來(lái)存儲(chǔ)視線方向以及遍歷的步長(zhǎng)數(shù)據(jù)，單獨(dú)開(kāi)辟一個(gè)GPU二維數(shù)組用于存儲(chǔ)計(jì)算結(jié)果。在GPU上完成體素?cái)?shù)據(jù)的累積操作。并將最終結(jié)果顯示出來(lái)。

3.1生成渲染數(shù)據(jù)

經(jīng)體渲染Ray-casting算法的原理可知，算法需要有兩個(gè)Gpu Array來(lái)存儲(chǔ)數(shù)據(jù)，分別為用于存儲(chǔ)計(jì)算結(jié)果的GPU二維數(shù)組Gpu Array 2D指針類型的變量g Arr Out，以及用于存儲(chǔ)計(jì)算結(jié)果的GPU三維數(shù)組Gpu Array3D指針類型的變量g Arr VT。

渲染數(shù)據(jù)存儲(chǔ)在二進(jìn)制的文件“backpack8.raw”中，該文件內(nèi)部由一組連續(xù)的8位整數(shù)構(gòu)成的，每個(gè)數(shù)據(jù)代表一個(gè)體素的灰度值。體素?cái)?shù)據(jù)的規(guī)格是512*512*373，可以理解為使用分辨率為512*512的掃描設(shè)備進(jìn)行了373次分層掃描，得到的數(shù)據(jù)組成了體素?cái)?shù)據(jù)，文件大小為93.25 MB。體素?cái)?shù)據(jù)文件的讀取是通過(guò)標(biāo)準(zhǔn)C++庫(kù)進(jìn)行的，使用二進(jìn)制方式讀取，讀取的數(shù)據(jù)存儲(chǔ)在一個(gè)byte數(shù)組里。數(shù)組的空間是在文件讀取結(jié)束之后動(dòng)態(tài)申請(qǐng)的，其長(zhǎng)度為文件中體素的個(gè)數(shù)*4，這是因?yàn)樽罱K在存儲(chǔ)為BMP圖像時(shí)需要有RGBA分量。

3.2創(chuàng)建并行計(jì)算函數(shù)

體渲染并行計(jì)算的算法大致是這樣的，輸出數(shù)組中的每個(gè)元素，根據(jù)自己所在的線程的Id編號(hào)GPU_FUNCTION_ID_X與GPU_FUNCTION_ID_Y分別到傳入的三維數(shù)組里面查找XY坐標(biāo)與之對(duì)應(yīng)的元素，并根據(jù)Z坐標(biāo)從小到大的順序，對(duì)其灰度根據(jù)一定的規(guī)則進(jìn)行疊加，將結(jié)果寫入輸出數(shù)組中。

3.3框架初始化

需要?jiǎng)?chuàng)建一個(gè)EurekaFramework：：FrameworkManager對(duì)象framework_manager以及一個(gè)EurekaFramework：：GpuFunction指針對(duì)象func。通過(guò)調(diào)用framework_manager的init（）方法實(shí)現(xiàn)框架的初始化。對(duì)于GPU數(shù)組類數(shù)據(jù)需要調(diào)用方法AssignValue來(lái)進(jìn)行初始化，具體代碼如下所示：

3.4計(jì)算過(guò)程

首先使用框架管理器為func創(chuàng)建對(duì)象，然后通過(guò)func加載并行計(jì)算函數(shù)代碼，最后對(duì)函數(shù)進(jìn)行參數(shù)設(shè)置并計(jì)算，具體代碼如下所示：

3.5讀回?cái)?shù)據(jù)

計(jì)算完成后將g Arr Out中的數(shù)據(jù)讀取到內(nèi)存通過(guò)一個(gè)圖像函數(shù)類寫入到BMP文件中既可以看到渲染結(jié)果。渲染結(jié)果如圖所示。

圖1　顱骨體素信息渲染效果Fig.1 Rendering effects of voxel information in skull

圖2　圖像函數(shù)在BMP文件中渲染結(jié)果Fig.2 Rendering effects of image function in BMPfiles

3.6結(jié)果分析

對(duì)于同一種算法，同樣使用圖形API的方法進(jìn)行了實(shí)現(xiàn)，經(jīng)過(guò)與使用并行框架的代碼進(jìn)行對(duì)比可以發(fā)現(xiàn)，使用框架的代碼量?jī)H僅為圖形API代碼量的一半左右。并且在整段代碼中并沒(méi)有任何關(guān)于OpenGL的代碼出現(xiàn)。這樣的設(shè)計(jì)對(duì)于從未使用過(guò)圖形API的用戶來(lái)講是一種極大的便利。相對(duì)于傳統(tǒng)圖形API的算法，框架的算法更加類似于CPU的多線程算法，用戶不需要去理解繁瑣的圖形管線設(shè)計(jì)，更免去了根據(jù)管線特性設(shè)計(jì)并行計(jì)算算法的麻煩。

4　總結(jié)

針對(duì)類似于體渲染這類的計(jì)算密集行應(yīng)用，使用GPU通用計(jì)算技術(shù)是良好的解決方案。但是頻

繁使用到的大量圖形API操作是一般人很難接近這個(gè)領(lǐng)域。基于上述問(wèn)題，提出了創(chuàng)建通用計(jì)算框架這一解決方案。通用計(jì)算框架需要滿足適用范圍廣，不依賴于特定的顯卡品牌，使用時(shí)不涉及圖形學(xué)知識(shí)的特點(diǎn)。通過(guò)與CPU普通運(yùn)算的對(duì)比，抽象出了GPU通用計(jì)算框架應(yīng)該具有的功能與計(jì)算的流程，通過(guò)體渲染的實(shí)例闡述了框架的使用過(guò)程，并通過(guò)代碼的對(duì)比證明了框架具有代碼結(jié)構(gòu)清晰，簡(jiǎn)潔，與圖形API無(wú)關(guān)的特點(diǎn)。

參考文獻(xiàn)

［1］Yuan ZY，Si WX，Liao XY，et al. Parallel computing of 3D smoking simulation based on OpenCL heterogeneous platform［J］. Journal of Supercomputing，2012，61（1）：84-102

［2］Wang L，Kaufman A. Importance Driven Automatic Color Design for Direct Volume Rendering［J］. Computer graphics forum，2012，31（3）：1305-1344

［3］安吉爾.交互式計(jì)算機(jī)圖形學(xué)——基于OpenGL的自頂向下方法［M］.第4版.北京：清華大學(xué)出版社，2007

［4］Slowinski R，Zopounidis C，Dimitras AI. Rough Set Predictor of Business Failure［J］. Soft Computing in Financial Engineering，2014，5（8）：402-424

［5］張奇，李珂，劉旭東，等.基于平衡點(diǎn)計(jì)算的感應(yīng)電機(jī)端口受控哈密頓控制策略［J］.山東大學(xué)學(xué)報(bào)：工學(xué)版，2015，45（1）：70-75

［6］李瑞霞，劉仁金，周先存.基于哈希表的MapReduce算法優(yōu)化［J］.山東大學(xué)學(xué)報(bào)：理學(xué)版，2015（7）：66-70

［7］賴特，利普恰克，黑內(nèi)爾.OpenGL超級(jí)寶典［M］.第5版.北京：人民郵電出版社，2012

［8］張舒，褚艷利.GPU高性能運(yùn)算之CUDA［M］.北京：水利水電出版社，2010

Parallel Algorithm Based on General Purpose Computing on GPU and the Implementation of Calculation Framework

ZHU Yu-lan

Quanzhou Medical College，Quanzhou 362000，China

Abstract：GPGPU（General Purpose Computing on Graphics Processing Unit）is a calculation mothed that develops quiet fast in recent years，it provide an optimal solution for the intensive data calculation of a single instruction with a powerful treatment，however it is restricted in CPU making process to lead to entounter the bottleneck of hardware manufacture. This paper started from GPGPU by Graphics API to analyze the featuers，progress and characteristics of GPU parallel algorithm and obtained a set of computing framework to demonstrate it by an intensive line calculation and compared between the traditional GPU and the parallel computing framework to turn out to show that there was a simplified code and had nothing to do with graphics.

Keywords：General Purpose Computing on Graphics Processing Unit（GPGPU）；parallel computing；computing framework

中圖法分類號(hào)：TN202

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1000-2324（2016）03-0473-04

收稿日期：2015-03-20修回日期：2015-04-28

作者簡(jiǎn)介：朱宇蘭（1979-），女，碩士，講師，主要研究方向?yàn)樗惴ㄔO(shè)計(jì)與分析、網(wǎng)絡(luò)管理與安全. E-mail：zhu@163.com