肖 漢，郭寶云，李彩林，周清雷

（1.鄭州師范學(xué)院 信息科學(xué)與技術(shù)學(xué)院，鄭州 450044；2.山東理工大學(xué) 建筑工程學(xué)院，山東 淄博 255000；3.鄭州大學(xué) 信息工程學(xué)院，鄭州 450001）

0 概述

傳遞閉包運(yùn)算在圖論、網(wǎng)絡(luò)、計(jì)算機(jī)形式語(yǔ)言、語(yǔ)法分析以及開(kāi)關(guān)電路中的故障檢測(cè)和診斷領(lǐng)域都有著廣泛的應(yīng)用價(jià)值［1-2］。根據(jù)定義，關(guān)系傳遞閉包的計(jì)算是通過(guò)多次進(jìn)行集合復(fù)合運(yùn)算完成，運(yùn)算量很大。同時(shí)，假如二元關(guān)系在某種情況下發(fā)生了改變，其中的某些序偶增加或減少，需要按照原方法將變化的二元關(guān)系重新計(jì)算來(lái)得到新關(guān)系的傳遞閉包，運(yùn)算量則進(jìn)一步增大［3-5］。這樣容易造成大量數(shù)據(jù)無(wú)法實(shí)時(shí)處理，最終使整個(gè)應(yīng)用系統(tǒng)處理的時(shí)間增加，因此如何快速有效地處理傳遞閉包問(wèn)題成為了一個(gè)急需解決的問(wèn)題［6-7］。

開(kāi)展傳統(tǒng)的利用CPU 集群的高性能計(jì)算是解決大規(guī)?？茖W(xué)計(jì)算問(wèn)題的常用方法，然而集群的并行計(jì)算性能對(duì)于CPU 的更新?lián)Q代的依賴性很大。由于CPU 芯片單位面積內(nèi)的晶體管集成度越來(lái)越高，散熱和能耗問(wèn)題凸顯，致使提升CPU 的速度放緩，發(fā)展陷入瓶頸［8-10］。為了更快地增強(qiáng)計(jì)算能力，計(jì)算機(jī)硬件設(shè)計(jì)的異構(gòu)化的趨勢(shì)越發(fā)明顯［11-12］。由若干不同架構(gòu)的CPU 處理器和協(xié)處理器共同工作，通用計(jì)算處理器與多個(gè)加速器設(shè)備互連構(gòu)成的異構(gòu)計(jì)算系統(tǒng)逐漸成為主流［13-14］。

開(kāi)放式計(jì)算語(yǔ)言（Open Computing Language，OpenCL）是一個(gè)面向異構(gòu)硬件平臺(tái)的、免費(fèi)的、開(kāi)放的行業(yè)標(biāo)準(zhǔn)。遵循OpenCL 規(guī)范的不同架構(gòu)的硬件，提供需要的編譯和運(yùn)行平臺(tái)，就能夠在OpenCL 平臺(tái)上開(kāi)發(fā)普適的應(yīng)用系統(tǒng)，為多核CPU、CPU+GPU、DSP 和多GPU 等異構(gòu)計(jì)算提供良好的研發(fā)平臺(tái)［15-16］。

本文基于開(kāi)放式計(jì)算語(yǔ)言平臺(tái)，提出一種基于CPU+GPU 的高效傳遞閉包并行算法，并采用具有可移植性的OpenCL 架構(gòu)來(lái)實(shí)現(xiàn)該算法。對(duì)在不同數(shù)據(jù)集下和不同體系結(jié)構(gòu)下的算法和加速比進(jìn)行分析。

1 相關(guān)研究

近年來(lái)，很多學(xué)者對(duì)傳遞閉包運(yùn)算進(jìn)行了研究。文獻(xiàn)［17］用一階有界傳遞閉包模糊邏輯來(lái)刻畫(huà)模糊有窮自動(dòng)機(jī)。文獻(xiàn)［18］研究了稠密圖條件下采用XHop 方法，對(duì)傳遞閉包進(jìn)行高壓縮比存儲(chǔ)和有效查詢的算法。文獻(xiàn)［19］提出改進(jìn)的傳遞閉包求解方法，并在傳遞閉包改進(jìn)的求解方式基礎(chǔ)上，設(shè)計(jì)了傳遞閉包的增量式更新方法。文獻(xiàn)［20］證明只要函數(shù)在Jensen 的J層次結(jié)構(gòu)的某個(gè)多項(xiàng)式級(jí)別中是統(tǒng)一可行的，則相對(duì)于函數(shù)參數(shù)的傳遞閉包，其在任意集上是安全遞歸的。文獻(xiàn)［21］提出改進(jìn)的Floyd-Warshall算法，其中最耗時(shí)的部分（描述程序循環(huán)中自相關(guān)的傳遞閉包）是通過(guò)依賴距離向量計(jì)算，減少了傳遞閉包計(jì)算時(shí)間。文獻(xiàn)［22］基于程序依賴圖的傳遞閉包，提出一種在瓦片內(nèi)生成具有任意順序循環(huán)的并行代碼的方法。文獻(xiàn)［23］使用循環(huán)嵌套依賴圖的傳遞閉包來(lái)執(zhí)行原始矩形瓦片的校正，生成并行無(wú)同步代碼。文獻(xiàn)［24］通過(guò)應(yīng)用依賴圖的傳遞閉包，提出生成Nussinov RNA 折疊算法的并行代碼的加速因子。文獻(xiàn)［25］通過(guò)MPI 并行化實(shí)現(xiàn)了Warshall 方法，進(jìn)而快速求取了關(guān)系R的傳遞閉包R+。

文獻(xiàn)［26］通過(guò)向量化方法將循環(huán)結(jié)構(gòu)并行化，實(shí)現(xiàn)了傳遞閉包并行算法。文獻(xiàn)［27］在二叉樹(shù)并行計(jì)算模型上，實(shí)現(xiàn)了一種基于MPI 的傳遞閉包并行算法。文獻(xiàn)［28］通過(guò)實(shí)現(xiàn)傳遞閉包并行算法，提高了在圖形和高維數(shù)據(jù)中挖掘中心對(duì)象算法的收斂性。文獻(xiàn)［29］利用MPI 提出了基于VLSI 的傳遞閉包并行算法。文獻(xiàn)［30］通過(guò)合并Dijkstra 單源最短路徑方法中的貪婪技術(shù)的特征和傳遞閉包屬性來(lái)找到所有點(diǎn)對(duì)最短路徑，并在MapReduce 平臺(tái)上實(shí)現(xiàn)了ex-FTCD 算法。

綜上所述，目前大部分研究工作是通過(guò)優(yōu)化算法本身從而實(shí)現(xiàn)對(duì)傳遞閉包算法的快速計(jì)算，有些則利用傳統(tǒng)的向量化和CPU 集群的MPI 并行計(jì)算方式設(shè)計(jì)傳遞閉包算法。但是，性能加速效果在這些相關(guān)研究中表現(xiàn)的均不明顯。同時(shí)，算法研究和平臺(tái)設(shè)計(jì)局限于單一類型，對(duì)于多算法和多平臺(tái)的系統(tǒng)性能評(píng)估不多。本文將根據(jù)傳遞閉包算法特性和OpenCL 架構(gòu)的特征，研究異構(gòu)協(xié)同計(jì)算下的傳遞閉包并行算法，以及在多種計(jì)算平臺(tái)上算法的性能移植。

2 傳遞閉包算法

2.1 OpenCL 異構(gòu)編程模型

OpenCL 是一種面向開(kāi)放的、通用并行編程的、跨平臺(tái)的行業(yè)標(biāo)準(zhǔn)，軟件開(kāi)發(fā)人員可以方便地將CPU、GPU和其他各類計(jì)算設(shè)備接入系統(tǒng)計(jì)算［31-32］。OpenCL 標(biāo)準(zhǔn)是編程語(yǔ)言與編程框架的集合體，人們可以基于硬件抽象層API和面向數(shù)據(jù)的異構(gòu)編程環(huán)境進(jìn)行OpenCL系統(tǒng)的開(kāi)發(fā)和優(yōu)化應(yīng)用。OpenCL 框架主要由OpenCL平臺(tái)層、OpenCL 運(yùn)行時(shí)環(huán)境和OpenCL 編譯器3 個(gè)部分組成［33-35］。平臺(tái)層允許用戶收集可用的OpenCL 設(shè)備信息。開(kāi)發(fā)者可以查詢特定設(shè)備的詳細(xì)資料，比如緩存大小、存儲(chǔ)器結(jié)構(gòu)、核心數(shù)量等。OpenCL Runtime提供了管理設(shè)備存儲(chǔ)器、運(yùn)行kernel、在設(shè)備與主機(jī)之間傳輸數(shù)據(jù)等一系列API［36-39］。OpenCL 編譯器創(chuàng)建包含OpenCL kernel 的可執(zhí)行程序，把kernel 編譯成設(shè)備能夠識(shí)別的代碼。

2.2 算法定義

圖的傳遞閉包可以采用布爾矩陣的平方法計(jì)算。首先假定A是一個(gè)m點(diǎn)有向圖的m×m的布爾鄰接矩陣，當(dāng)且僅當(dāng)有向圖中從頂點(diǎn)i到頂點(diǎn)j之間有一條邊時(shí)，矩陣元素aij為1。然后利用矩陣乘法對(duì)布爾矩陣的傳遞閉包A+求解［40-41］。設(shè)I是單位矩陣，大小為m×m的關(guān)系矩陣為B=A∪I。使矩陣B的第i行上的元素與矩陣B的第j列上的元素按順序分別相乘再相加，得到新的關(guān)系矩陣B的第i行第j列的元素（關(guān)系矩陣B在不斷更新），即B的定義如下：

得到新的關(guān)系矩陣B重復(fù)上一步進(jìn)行循環(huán)，即依次計(jì)算，即執(zhí)行p＜logam次，得到布爾矩陣的傳遞閉包A+［42-44］。由此可知，算法的時(shí)間復(fù)雜性在最壞的情況下為O(m3logam)，當(dāng)m非常大時(shí)，該算法運(yùn)算將非常耗時(shí)［45］。

2.3 算法的并行特征分析

算法的可并行性高低與算法自身存在的數(shù)據(jù)依賴性有關(guān)。如果算法運(yùn)算前后依賴性越強(qiáng)，則算法的可并行性就越低，反之，如果算法運(yùn)算前后依賴性越弱，則算法的可并行性就越高，算法并行化后進(jìn)行并行計(jì)算的性能就會(huì)越好。圖1 所示是一個(gè)有向圖的傳遞閉包算法的可并行性分析。

圖1 有向圖Fig.1 Directed graph

根據(jù)圖1 的5 個(gè)頂點(diǎn)的有向圖表示出布爾矩陣Aij，計(jì)算布爾矩陣Aij的閉包(Aij)÷過(guò)程如下：

在(Aij)÷的計(jì)算過(guò)程中可以發(fā)現(xiàn)，每一計(jì)算步驟中的任意一個(gè)元素的計(jì)算過(guò)程與其他元素計(jì)算互不影響，相互之間并沒(méi)有依賴性。因此，可以在計(jì)算某一個(gè)元素值時(shí)，同時(shí)對(duì)其他元素值進(jìn)行運(yùn)算。結(jié)合OpenCL 的計(jì)算模型，將每個(gè)元素的計(jì)算過(guò)程放入工作項(xiàng)中，每個(gè)工作項(xiàng)計(jì)算得出相應(yīng)元素的結(jié)果。若矩陣中每個(gè)元素計(jì)算結(jié)束，則本次計(jì)算結(jié)束，如果需要繼續(xù)迭代，則再次重復(fù)以上過(guò)程。

3 傳遞閉包算法并行映射模型

3.1 并行算法

有向圖布爾矩陣A的傳遞閉包可以利用B=(A+I)的自乘logam次得到。設(shè)定工作空間中的工作組和工作項(xiàng)排成m×m的二維陣列，即其坐標(biāo)為(tx，ty)。每個(gè)工作組用數(shù)組as和數(shù)組bs存儲(chǔ)矩陣B中相應(yīng)子矩陣，Pvalue 保存的是每次子矩陣計(jì)算之后得到的值，數(shù)組C為每次計(jì)算完成之后最終數(shù)據(jù)。傳遞閉包并行算法描述如算法1 所示。

3.2 并行算法整體并行化思路

基于OpenCL 的傳遞閉包并行執(zhí)行流程如圖2所示。

圖2 傳遞閉包并行算法實(shí)現(xiàn)流程Fig.2 Implementation procedure of transitive closure parallel algorithm

傳遞閉包并行算法執(zhí)行過(guò)程如下：

1）在主機(jī)端根據(jù)對(duì)應(yīng)的頂點(diǎn)數(shù)，初始化布爾矩陣A，并保存初始化后的布爾矩陣。

2）初始化OpenCL 平臺(tái)。

3）創(chuàng)建上下文，并在目標(biāo)設(shè)備上創(chuàng)建命令對(duì)象。為了協(xié)調(diào)內(nèi)核計(jì)算，在上下文和計(jì)算設(shè)備之間利用clCreateCommandQueue 命令建立一個(gè)邏輯鏈接。

4）讀入源程序文件，并創(chuàng)建和編譯程序?qū)ο蟆８鶕?jù)上下文中的設(shè)備特性，利用運(yùn)行時(shí)編譯系統(tǒng)構(gòu)建程序?qū)ο蟆?/p>

5）設(shè)置存儲(chǔ)器對(duì)象和數(shù)據(jù)傳輸。在全局內(nèi)存中創(chuàng)建buffer 存儲(chǔ)器對(duì)象，然后將存儲(chǔ)器訪問(wèn)任務(wù)加入到命令隊(duì)列，最后通過(guò)clCreateBuffer 將布爾矩陣A、B從CPU 端隱式地傳輸?shù)皆O(shè)備端的全局內(nèi)存中。

6）建立內(nèi)核對(duì)象。在指定的一個(gè)內(nèi)核對(duì)象中將內(nèi)核參數(shù)和內(nèi)核函數(shù)通過(guò)clCreateKernel 封裝進(jìn)來(lái)。

7）設(shè)置需要傳遞的內(nèi)核對(duì)象參數(shù)。

8）創(chuàng)建kernel 函數(shù)，調(diào)度kernel 執(zhí)行。

9）循環(huán)調(diào)用kernel 函數(shù)對(duì)數(shù)據(jù)進(jìn)行相應(yīng)的處理，計(jì)算矩陣乘積大小。

10）將顯存端完成運(yùn)算任務(wù)后的結(jié)果復(fù)制到主機(jī)端內(nèi)存，并且釋放設(shè)備端顯存空間，將最終的計(jì)算結(jié)果保存到對(duì)應(yīng)的文件中。

3.3 算法的并行方案設(shè)計(jì)

在設(shè)計(jì)傳遞閉包并行算法時(shí)，矩陣乘法的并行計(jì)算采用了工作項(xiàng)分塊的方法實(shí)現(xiàn)，計(jì)算原理如圖3 所示。工作組中的每個(gè)工作項(xiàng)讀取矩陣B中的一行和矩陣B中的一列，將行、列中對(duì)應(yīng)元素相乘之后再相加，得到新矩陣B的對(duì)應(yīng)位置元素值，即每個(gè)工作項(xiàng)對(duì)應(yīng)計(jì)算新矩陣B中的一個(gè)元素。以上操作循環(huán)經(jīng)過(guò)p＜logam次后得到有向圖的傳遞閉包A+的形式矩陣。

圖3 傳遞閉包算法中的矩陣相乘Fig.3 Matrix multiplication in the transitive closure algorithm

按照相互之間無(wú)重疊的劃分原則，整個(gè)矩陣B將被劃分成若干個(gè)計(jì)算區(qū)域。計(jì)算區(qū)域可作為一個(gè)基本處理單位，由工作組處理。文中采用二維工作空間進(jìn)行設(shè)計(jì)，從數(shù)據(jù)層面上看，每個(gè)工作組在x，y方向上的維度均為BLOCK_SIZE。工作空間在x、y方向上共有個(gè)工作組，每個(gè)工作組中執(zhí)行了BLOCK_SIZE×BLOCK_SIZE 個(gè)工作項(xiàng)。

矩陣乘法中每一對(duì)元素間的乘-加計(jì)算由一個(gè)工作項(xiàng)負(fù)責(zé)。在內(nèi)核函數(shù)中循環(huán)完成矩陣B第i行元素與矩陣B第j列元素的乘-加運(yùn)算，并將乘-加的結(jié)果賦給Pvalue。在該kernel 函數(shù)中，矩陣B中的每一個(gè)元素從全局存儲(chǔ)器中讀取了m次，造成了時(shí)間上的大量延遲。

3.4 優(yōu)化設(shè)計(jì)

GPU 全局存儲(chǔ)器屬于片下存儲(chǔ)器，存儲(chǔ)空間較大，但具有較高的訪存延遲。而本地存儲(chǔ)器是GPU片上的高速存儲(chǔ)器，它的緩沖區(qū)駐留在物理GPU上。因此，本地存儲(chǔ)器的訪存延遲要遠(yuǎn)遠(yuǎn)低于全局存儲(chǔ)器，大量工作項(xiàng)的并行執(zhí)行能夠在一定程度上掩蓋全局存儲(chǔ)器操作的延遲。

將矩陣相乘后得到的新矩陣B分解成小矩陣塊，每一個(gè)工作組負(fù)責(zé)計(jì)算一個(gè)小矩陣塊。若矩陣B的大小是m×m，則新矩陣B=B×B。假設(shè)m=b×b，將新矩陣B分為b×b個(gè)小的子矩陣bij，則每一個(gè)子矩陣bij的大小為b×b。2 個(gè)相乘的矩陣B同新矩陣B一樣，劃分為b×b個(gè)小的子矩陣bij，且每一個(gè)子矩陣bij的大小同為b×b，則傳遞閉包并行算法中采用分塊矩陣乘法的定義為計(jì)算原理如圖4 所示。

圖4 傳遞閉包算法中的分塊矩陣相乘Fig.4 Multiplication of block matrix in transitive closure algorithm

在傳遞閉包并行算法的分塊矩陣乘法中，采用靜態(tài)方式定義大小為BLOCK_SIZE×BLOCK_SIZE的本地存儲(chǔ)器數(shù)組，用于存儲(chǔ)矩陣B子塊數(shù)據(jù)。

__local float as[BLOCK_SIZE][BLOCK_SIZE]

__local float bs[BLOCK_SIZE][BLOCK_SIZE]

為從全局存儲(chǔ)器預(yù)取計(jì)算子矩陣到本地存儲(chǔ)器，根據(jù)工作組的ID 和工作項(xiàng)的ID 確定B的計(jì)算子矩陣的位置，并將B中用于計(jì)算的2 個(gè)計(jì)算子矩陣分別預(yù)取至本地?cái)?shù)組as和bs中。每個(gè)工作項(xiàng)負(fù)責(zé)計(jì)算一對(duì)元素的乘積和PPvalue+=as[ty][k]×bs[k][tx]。原來(lái)矩陣的一行或一列數(shù)據(jù)需要從全局存儲(chǔ)器讀取m次，現(xiàn)在只需要讀取m/BBLOCK_SIZE次，這樣在新矩陣B的計(jì)算過(guò)程中矩陣數(shù)據(jù)需要從全局存儲(chǔ)器讀取m×m次，優(yōu)化后只需要讀取m2/BBLOCK_SIZE次。因此，通過(guò)對(duì)GPU的存儲(chǔ)帶寬進(jìn)行充分的利用，減少?gòu)娜执鎯?chǔ)器中重復(fù)讀取數(shù)據(jù)。使用本地存儲(chǔ)器不僅可以降低訪問(wèn)延遲以此提高訪問(wèn)速率，同時(shí)節(jié)約了對(duì)全局存儲(chǔ)器的訪問(wèn)帶寬。

4 實(shí)驗(yàn)測(cè)試與結(jié)果分析

本節(jié)將給出所描述的傳遞閉包方法的測(cè)試結(jié)果。由于單精度浮點(diǎn)運(yùn)算針對(duì)現(xiàn)代計(jì)算機(jī)，特別是在GPU 上進(jìn)行了高度優(yōu)化，因此本文選擇單精度數(shù)據(jù)類型實(shí)現(xiàn)算法。

4.1 測(cè)試環(huán)境和實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)軟硬件平臺(tái)如下：

1）硬件平臺(tái)

平臺(tái)1：CPU 為AMD Ryzen5 1600X 3.6 GHz（六核心），24.0 GB 的系統(tǒng)內(nèi)存。GPU 型號(hào)是NVIDIA GeForce GTX 1070，CUDA 核心1 920 顆，1 506 MHz的核心頻率，1 683 MHz 的流處理器頻率，8 GB GDDR5 的顯存，256 bit 的顯存位寬，256 Gb/s 的顯存帶寬，顯存存取速率為8 Gb/s。

平臺(tái)2：CPU 為AMD Ryzen5 1600X 3.6 GHz（六核心），24.0 GB 的系統(tǒng)內(nèi)存。GPU 型號(hào)是AMD Radeon RX 570，其中，計(jì)算單元32 組，每組計(jì)算單元具有64 個(gè)處理單元，總計(jì)2 048 顆流處理單元，1 168 MHz 的核心頻率，256 bit 的顯存位寬，8 GB GDDR5 顯存。

2）軟件平臺(tái)：操作系統(tǒng)采用微軟Windows 8.1 64位；集成開(kāi)發(fā)環(huán)境為微軟Visual Studio 2017；系統(tǒng)編譯環(huán)境為CUDA Toolkit 8.0，OpenCL 1.2 標(biāo)準(zhǔn)被支持。

有向圖的頂點(diǎn)集合大小n分別取為20、40、50、70、200、300、500、1 024，作為rand()隨機(jī)數(shù)函數(shù)的隨機(jī)數(shù)種子分別生成一組隨機(jī)數(shù)，構(gòu)成布爾矩陣A。根據(jù)本文的傳遞閉包算法的描述，基于OpenMP 平臺(tái)和基于CUDA 平臺(tái)的傳遞閉包并行算法均在文中實(shí)現(xiàn)。

傳遞閉包算法運(yùn)行在基于OpenMP系統(tǒng)、基于CUDA系統(tǒng)、基于AMD GPU 的OpenCL系統(tǒng)和基于NVIDIA GPU 的OpenCL系統(tǒng)的上處理時(shí)間，如表1所示。處理時(shí)間包括傳遞閉包算法的所有處理步驟。在OpenCL 中實(shí)現(xiàn)GPU 并行算法時(shí)，必須執(zhí)行額外的步驟，如內(nèi)核創(chuàng)建（讀取、創(chuàng)建和構(gòu)建最終內(nèi)核對(duì)象）、主機(jī)內(nèi)存和GPU 全局存儲(chǔ)器之間的數(shù)據(jù)傳輸以及數(shù)據(jù)結(jié)構(gòu)初始化。

表1 傳遞閉包算法執(zhí)行時(shí)間Table 1 Execution time of transitive closure algorithm

用加速比作為加速效果的衡量標(biāo)準(zhǔn)，可以直觀地驗(yàn)證各種架構(gòu)下并行算法的效率，其定義如下：

CPU 串行算法執(zhí)行時(shí)間與并行算法執(zhí)行時(shí)間的比值即為加速比：

其中：Tserial是在CPU 上單個(gè)線程的順序運(yùn)算時(shí)間；Tparallel是在多核CPU 或CPU+GPU 上多線程實(shí)現(xiàn)的并行運(yùn)算時(shí)間。

相對(duì)加速比1基于OpenMP 的并行算法運(yùn)算時(shí)間與基于NVIDIA GPU 的OpenCL 并行算法運(yùn)算時(shí)間的比值：

其中：Tparallel-OpenMP是在多核CPU 上多線程的并行運(yùn)算時(shí)間；Tparallel-NOpenCL是在NVIDIA GPU 上OpenCL 的并行運(yùn)算時(shí)間。

相對(duì)加速比2基于NVIDIA GPU 平臺(tái)的CUDA 并行算法運(yùn)算時(shí)間與基于NVIDIA GPU 平臺(tái)的OpenCL 并行算法運(yùn)算時(shí)間的比值：

其中：Tparallel-CUDA是在CUDA 上的并行執(zhí)行時(shí)間；Tparallel-NOpenCL是在NVIDIA GPU 上OpenCL 并行實(shí)現(xiàn)的并行執(zhí)行時(shí)間。Tparallel-CUDA和Tparallel-NOpenCL定義如下：

其中：Tkernel為OpenCL 內(nèi)核在CPU 和GPU 上總的執(zhí)行時(shí)間；Tovehead為在CPU 和GPU 上數(shù)據(jù)傳輸時(shí)間開(kāi)銷的總和；Tother為數(shù)據(jù)結(jié)構(gòu)初始化等操作總的運(yùn)行時(shí)間。

為了更好地對(duì)應(yīng)用系統(tǒng)速度進(jìn)行客觀評(píng)價(jià)，采用加速比指標(biāo)來(lái)反映在一定的計(jì)算架構(gòu)下的并行算法相較串行算法的效率提升幅度。使用相對(duì)加速比1 指標(biāo)來(lái)反映基于NVIDIA GPU 的OpenCL 并行算法相比基于多核CPU 的OpenMP 并行算法的效率提升情況，相對(duì)加速比2 指標(biāo)則反映出基于NVIDIA GPU 的OpenCL 并行算法相比基于GPU 的CUDA 并行算法的效率提升情況，如表2 所示。

表2 傳遞閉包并行算法性能對(duì)比Table 2 Performance comparison of transitive closure parallel algorithm

4.2 實(shí)驗(yàn)數(shù)據(jù)分析

4.2.1 系統(tǒng)性能瓶頸分析

在存儲(chǔ)器讀寫(xiě)操作時(shí)，需要鄰接矩陣數(shù)據(jù)的m×m×m次存儲(chǔ)器讀取，有向圖的傳遞閉包矩陣數(shù)據(jù)的m×m次存儲(chǔ)器寫(xiě)入操作。設(shè)一個(gè)m=200 點(diǎn)的有向圖，每個(gè)像素值分配存儲(chǔ)空間大小是4 Byte，所以，存儲(chǔ)器存取數(shù)據(jù)總量約為0.032 GB，除以kernel 實(shí)際執(zhí)行的時(shí)間0.000 257 s，得到的帶寬數(shù)值是約124.51 GB/s，這已經(jīng)接近GeForce Tesla C2075 顯示存儲(chǔ)器的150.34 GB/s 帶寬。因此，可以很明顯地看出，基于OpenCL 架構(gòu)的傳遞閉包并行算法的效率受限于全局存儲(chǔ)器帶寬。

從表2 可以看出，基于CPU+GPU 的算法加速效果明顯，但GPU 并行算法的加速比隨著有向圖頂點(diǎn)數(shù)的增加呈現(xiàn)緩慢下降的趨勢(shì)。主要原因是在OpenCL 并行算法操作中，CPU 負(fù)責(zé)讀取和輸出圖的鄰接矩陣數(shù)據(jù)，而這一過(guò)程并沒(méi)有加速。隨著被處理鄰接矩陣規(guī)模的增加，讀取和輸出鄰接矩陣數(shù)據(jù)所花費(fèi)的時(shí)間也在增加。因此，OpenCL 架構(gòu)下的傳遞閉包并行算法的性能瓶頸是顯存帶寬和主存與顯存之間數(shù)據(jù)傳輸?shù)膸挕?/p>

4.2.2 傳遞閉包并行算法性能分析

不同并行計(jì)算平臺(tái)下的傳遞閉包并行算法加速比對(duì)比曲線如圖5 所示。在多核CPU 平臺(tái)上，傳遞閉包算法的運(yùn)算速度得到加速。然而，限于核心數(shù)，系統(tǒng)的加速比相對(duì)較小且變化不大，但由于GPU 具有較豐富的計(jì)算資源，在CUDA 架構(gòu)和OpenCL 架構(gòu)下的傳遞閉包算法就可以擁有足夠的工作項(xiàng)來(lái)進(jìn)行大量數(shù)據(jù)的并行處理。1 920 個(gè)處理單元通過(guò)時(shí)間分割機(jī)制分配到一定數(shù)量的工作項(xiàng)，加速比得到較大提高且增幅明顯。通過(guò)表2 分析，在對(duì)計(jì)算密集型特征明顯的大規(guī)模數(shù)據(jù)集計(jì)算時(shí)，GPU系統(tǒng)運(yùn)算時(shí)間有小量增幅，體現(xiàn)了GPU 用于計(jì)算密集型的任務(wù)運(yùn)算不如CPU 敏感，顯現(xiàn)出GPU 強(qiáng)大的運(yùn)算能力。

圖5 傳遞閉包并行算法的加速比對(duì)比Fig.5 Comparison of acceleration ratios of transitive closure parallel algorithm

由圖5 可知，隨著布爾矩陣規(guī)模的增加，GPU 加速下的加速比曲線斜率急劇變大，曲線變得十分陡峭。加速比呈現(xiàn)出快速增加的趨勢(shì)，比較明顯地體現(xiàn)出并行處理的性能提升效果。然而當(dāng)布爾矩陣大小超過(guò)70×70 繼續(xù)增大時(shí)，曲線呈現(xiàn)出一種下降趨勢(shì)。雖然隨著布爾矩陣規(guī)模的增大，工作空間中包含的工作組數(shù)也隨之增多，系統(tǒng)中可同時(shí)執(zhí)行更多的子矩陣，對(duì)于提高訪問(wèn)全局存儲(chǔ)器和本地存儲(chǔ)器的效率有益，也越容易隱藏存儲(chǔ)器延時(shí)，但是布爾矩陣規(guī)模的增大，主機(jī)端和設(shè)備端存儲(chǔ)器之間交互數(shù)據(jù)的時(shí)間成本變大，較大程度地抵消了GPU 并行計(jì)算的優(yōu)勢(shì)，導(dǎo)致GPU系統(tǒng)加速性能下降，整體系統(tǒng)性能受到制約。

4.2.3 傳遞閉包并行算法跨平臺(tái)性分析

可移植性不但要求源碼能夠在不同的平臺(tái)上成功地編譯、運(yùn)行，而且還需要算法應(yīng)當(dāng)有相當(dāng)?shù)男阅?。運(yùn)算結(jié)果表明，在CUDA 架構(gòu)下的傳遞閉包并行算法受到單一硬件平臺(tái)的限制，而基于OpenCL 的傳遞閉包并行算法則在多種硬件平臺(tái)上獲得了較好的可移植性和兼容性，其最大加速比為593.14 倍，如圖6 所示。

圖6 OpenCL 加速比趨勢(shì)Fig.6 OpenCL acceleration ratio trend

由于采用離線編譯內(nèi)核讀寫(xiě)數(shù)據(jù)文件的OpenCL加速的傳遞閉包并行算法，相比在線編譯內(nèi)核讀寫(xiě)數(shù)據(jù)文件的CUDA 加速的傳遞閉包并行算法減少了應(yīng)用初始化時(shí)間。在同等數(shù)據(jù)集規(guī)模下，基于OpenCL 的傳遞閉包并行算法的運(yùn)算耗時(shí)更少，與CUDA 計(jì)算平臺(tái)上的算法性能相比略有提升，最大獲得了1.05 倍加速比。而OpenCL 加速的傳遞閉包并行算法性能較之OpenMP 計(jì)算平臺(tái)下的算法性能則有很大的提高，加速比最大獲得了208.62 倍，如圖7 所示。

圖7 相對(duì)加速比趨勢(shì)Fig.7 Relative acceleration ratio trend

5 結(jié)束語(yǔ)

在許多應(yīng)用系統(tǒng)中傳遞閉包是必要的基本部件，且為系統(tǒng)中較為耗時(shí)的部分，而矩陣乘對(duì)整個(gè)系統(tǒng)實(shí)時(shí)性能則有較大影響。本文針對(duì)傳遞閉包算法串行性能低下的不足，提出適合于OpenCL 架構(gòu)的計(jì)算模式，并設(shè)計(jì)實(shí)現(xiàn)了傳遞閉包GPU 并行算法。實(shí)驗(yàn)結(jié)果表明，基于OpenCL 架構(gòu)的傳遞閉包并行算法的性能相比CPU 串行算法、基于CPU 的OpenMP 并行算法和基于GPU 的CUDA 并行算法，分別取得了593.14 倍、208.62 倍和1.05 倍的加速比。在算法的GPU 實(shí)現(xiàn)過(guò)程中配置適當(dāng)?shù)膬?nèi)核參數(shù)和合理的分塊參數(shù)，能有效提高處理效率，且實(shí)現(xiàn)同等計(jì)算量的GPU 相比CPU，性價(jià)比更高。因此，采用本文GPU異構(gòu)計(jì)算模式對(duì)大規(guī)模數(shù)據(jù)運(yùn)算且系統(tǒng)實(shí)時(shí)性要求較高的應(yīng)用，將是一條新的思路。