CPU—OpenMP和GPU—CUDA并行計(jì)算技術(shù)對矩陣乘法運(yùn)算的加速效果分析

張巖

【摘 要】本文對比了CPU-OpenMP和GPU-CUDA并行計(jì)算技術(shù)對不同階矩陣乘法運(yùn)算相對于CPU單線程計(jì)算的加速效果。結(jié)果表明，CPU-OpenMP并行的計(jì)算加速比與矩陣階數(shù)無關(guān)，且低于所采用的線程數(shù)目。GPU-CUDA并行的計(jì)算加速比隨矩陣階數(shù)的增加顯著增加，最大計(jì)算加速比可達(dá)570倍以上。相對于CPU單線程計(jì)算結(jié)果，CPU-OpenMP并行計(jì)算未產(chǎn)生誤差，而GPU-CUDA并行計(jì)算會產(chǎn)生誤差。結(jié)果表明，GPU-CUDA并行適合高階數(shù)矩陣乘法的加速計(jì)算，而CPU-OpenMP并行適合低階數(shù)矩陣乘法的加速計(jì)算。

【關(guān)鍵詞】矩陣乘法；并行計(jì)算；CPU-OpenMP；GPU-CUDA

中圖分類號： TP391 文獻(xiàn)標(biāo)識碼： A 文章編號： 2095-2457（2017）26-0045-003

Accelerating Effect Analysis of Matrix Multiplication with CPU-OpenMP and GPU-CUDA Parallel Computing

ZHANG Yan

（Beijing Normal University Affiliated High School West High School Class 1， Beijing 100042，China）

【Abstract】This paper compares the accelerating effects of CPU-OpenMP and GPU-CUDA parallel computing on the computation of different-order matrix multiplication over CPU single-thread. The results show that the computational speedup of CPU-OpenMP parallelism is independent of matrix order and lower than the number of threads used. GPU-CUDA parallel computing speedup ratio increases significantly with the increase of the matrix order， the maximum computational speedup up to 570 times. Relative to the CPU single-thread calculations， CPU-OpenMP parallel computing did not produce errors， and GPU-CUDA parallel computing will produce errors. The results show that GPU-CUDA parallel is suitable for accelerated computing of high-order matrix multiplication， while CPU-OpenMP parallel is suitable for accelerated computing of low-order matrix multiplication.

【Key words】Matrix multiplication； Parallel computing； CPU-OpenMP； GPU-CUDA

0 前言

在信息化技術(shù)不斷發(fā)展的今天，人們處在“大數(shù)據(jù)”時代。由于數(shù)據(jù)量巨大，普通的串行計(jì)算方式計(jì)算效率低下，無法滿足人們對數(shù)據(jù)進(jìn)行快速處理的需求。因此，如何能夠提高計(jì)算機(jī)處理“大數(shù)據(jù)”的計(jì)算效率已成為人們?nèi)找骊P(guān)注的話題。為了減少計(jì)算時間、提升計(jì)算效率，并行計(jì)算的出現(xiàn)成為解決上述問題的有效方法。與普通的串行計(jì)算相比，并行計(jì)算將計(jì)算任務(wù)分配到計(jì)算機(jī)的多個處理器協(xié)同處理，從而提高計(jì)算效率。

隨著并行計(jì)算結(jié)果的發(fā)展，并行算法也逐漸成熟。目前，人們采用的并行計(jì)算技術(shù)大致可能分為兩種：一是基于CPU（Central Processing Unit）多核多線程的并行計(jì)算；二是基于GPU（Graphics Processing Unit）的通用并行計(jì)算。對于CPU并行計(jì)算，根據(jù)并行粒度的不同可分為“共享式內(nèi)存結(jié)構(gòu)”和 “分布式內(nèi)存結(jié)構(gòu)”[1]。對于“共享式內(nèi)存結(jié)構(gòu)”的并行計(jì)算，OpenMP（Open Multi-Processing）作為該類型計(jì)算技術(shù)的代表，已被廣泛應(yīng)用于數(shù)據(jù)處理及科學(xué)計(jì)算中。采用OpenMP做并行計(jì)算具有編程簡單、源程序改變小等優(yōu)點(diǎn)[2]。基于GPU的并行計(jì)算技術(shù)是近年來發(fā)展起來的新技術(shù)。與基于CPU的并行計(jì)算相比，GPU并行計(jì)算具有硬件成本低、加速效果顯著的優(yōu)點(diǎn)。隨著NVIDIA通用計(jì)算架構(gòu)CUDA（Compute Unified Device Architecture）的提出，人們用GPU做并行計(jì)算的編程難度大為降低[3]。

本文旨在采用CPU-OpenMP和GPU-CUDA并行計(jì)算技術(shù)進(jìn)行不同階矩陣的乘法運(yùn)算，并對比這兩種并行計(jì)算技術(shù)相對于串行計(jì)算（CPU單線程）的加速效果。此外，我們也對GPU-CUDA計(jì)算所產(chǎn)生的計(jì)算誤差進(jìn)行了簡要分析。

1 CPU-OpenMP和GPU-CUDA并行計(jì)算技術(shù)

CPU-OpenMP是一種API（Application Program Interface），用于編寫可移植的多線程應(yīng)用程序，并且無需進(jìn)行復(fù)雜的線程創(chuàng)建、同步、負(fù)載平衡和銷毀工作。CPU-OpenMP能廣泛應(yīng)用在Windows和Linux等多種平臺上，具有可移植性好的優(yōu)點(diǎn)。在Visual Studio 2010 編程環(huán)境下是用OpenMP API時，需打開項(xiàng)目屬性里的OpenMP支持選項(xiàng)。CPU-OpenMP的編程實(shí)現(xiàn)十分簡單，只需在原來串行計(jì)算程序里的for循環(huán)語句里加入#pragma omp parallel for語句即可實(shí)現(xiàn)并行計(jì)算[2]。如圖1所示，CPU-OpenMP并行計(jì)算的思路是主線程將共享內(nèi)存里的數(shù)據(jù)分配到不同的分線程里進(jìn)行計(jì)算，各個分線程完成計(jì)算任務(wù)后將結(jié)果返回到主線程，主線程再負(fù)責(zé)分配各個分線程下一步的計(jì)算任務(wù)。在CPU-OpenMP代碼編寫過程中，需對不同線程內(nèi)的變量屬性進(jìn)行區(qū)分，避免不同線程里的私有變量被其他線程的計(jì)算修改。endprint

圖2是GPU-CUDA的計(jì)算架構(gòu)示意圖。GPU-CUDA采用CPU-GPU異構(gòu)模式協(xié)同工作，將CPU稱為Host，GPU作為Host的協(xié)處理器，即Device。CPU負(fù)責(zé)串行代碼的執(zhí)行，由GPU負(fù)責(zé)執(zhí)行高度并行化的浮點(diǎn)數(shù)計(jì)算任務(wù)。GPU的運(yùn)算任務(wù)被編寫在Kernel函數(shù)里。如圖2所示，每個線程網(wǎng)格（Grid）由多個相同大小和維度的線程塊（Block）組成，若干個線程（Thread）又組成了線程塊，所以一個Grid就對應(yīng)了一個Kernel函數(shù)。

本研究中CPU單線程和CPU-OpenMP多線程運(yùn)算的程序代碼是用C語言編寫的，GPU-CUDA運(yùn)算的程序代碼是用CUDA C編寫的。所采用的硬件型號為CPU（Intel Xeon E5-1680 v4， 3.4GHz）和GPU（NVIDIA GeForce GTX1080Ti），操作系統(tǒng)和運(yùn)行環(huán)境為Windows7和Visual Studio 2010，CUDA版本為CUDA 7.0。

2 CPU-OpenMP和GPU-CUDA計(jì)算效率對比

首先，隨機(jī)產(chǎn)生兩個n階方陣An×n和Bn×n，本文中n的取值分別為n=500，1000，2000，4000，8000，矩陣元素類型為float。隨后，根據(jù)矩陣相乘運(yùn)算規(guī)則計(jì)算An×n·Bn×n，即矩陣元素（AB）ij= A B =A B +A B +…+A B ，分別采用CPU單線程、CPU-OpenMP多線程和GPU-CUDA并行技術(shù)計(jì)算不同階數(shù)矩陣的乘法，統(tǒng)計(jì)相應(yīng)的計(jì)算時間，并獲得CPU-OpenMP和GPU-CUDA的計(jì)算效率加速比。對于GPU-CUDA的計(jì)算結(jié)果，計(jì)算其相對于CPU運(yùn)算的最大相對誤差。本文中，CPU-OpenMP計(jì)算線程數(shù)和GPU-CUDA計(jì)算線程塊內(nèi)的線程數(shù)都設(shè)置為8。

表1是采用CPU單線程計(jì)算不同階數(shù)矩陣乘法所需的計(jì)算時間。可以看到，隨著矩陣階數(shù)的增加，CPU單線程計(jì)算時間明顯增加。此外，由于矩陣乘法的計(jì)算量是隨著矩陣階數(shù)的增加呈指數(shù)增加的，采用CPU單線程計(jì)算時所需計(jì)算時間也是呈指數(shù)增加。對于8000階矩陣乘法，直接采用CPU單線程計(jì)算的計(jì)算效率已經(jīng)十分低下，無法滿足人們對大通量數(shù)據(jù)快速處理的要求。

表1 CPU單線程計(jì)算不同階矩陣乘法所需時間

采用CPU-OpenMP多線程并行計(jì)算將原來單線程的計(jì)算任務(wù)分配給多個CPU線程分工執(zhí)行，從而提高計(jì)算效率。表2列出了采用CPU-OpenMP八線程并行計(jì)算得到不同階矩陣乘法所需的計(jì)算時間。可以看到，CPU-OpenMP八線程計(jì)算時間隨著矩陣階數(shù)的增加也呈指數(shù)級增加趨勢。然而，相對于CPU單線程計(jì)算，CPU-OpenMP八線程計(jì)算所需的計(jì)算時間明顯降低。由此可見，采用CPU-OpenMP多線程并行計(jì)算可顯著提升計(jì)算效率。

下面我們采用GPU-CUDA并行技術(shù)計(jì)算不同階數(shù)的矩陣乘法。首先，在GPU（Device）的顯存上為計(jì)算矩陣分配內(nèi)存空間；其次，將CPU（Host）上的矩陣數(shù)據(jù)復(fù)制到GPU顯存中，并在GPU上運(yùn)行Kernel函數(shù)進(jìn)行矩陣乘法運(yùn)算。在本文所采用的CUDA C程序中，Kernel函數(shù)里的內(nèi)存類型為Global。矩陣乘法計(jì)算結(jié)束后，把GPU顯存上存儲的計(jì)算結(jié)果復(fù)制到CPU內(nèi)存上，釋放GPU顯存并統(tǒng)計(jì)計(jì)算時間。表3給出了采用GPU-CUDA并行技術(shù)計(jì)算不同階數(shù)矩陣相乘的計(jì)算時間。與表1和表2 對比可以發(fā)現(xiàn)，對于高階數(shù)的矩陣乘法（n >2000），GPU-CUDA所需的計(jì)算時間遠(yuǎn)遠(yuǎn)低于CPU單線程計(jì)算和CPU-OpenMP八線程計(jì)算。對于低階數(shù)的矩陣乘法（n =500），GPU-CUDA的計(jì)算時間與CPU單核計(jì)算時間相差不大，并且慢于CPU-OpenMP八線程計(jì)算時間。由此可見，采用GPU-CUDA并行技術(shù)對于具有較大的運(yùn)算量的計(jì)算任務(wù)具有顯著的加速效果，但對于較小運(yùn)算量的計(jì)算任務(wù)加速效果不明顯。

為了能夠更好的展示和比較并行計(jì)算的加速效果，圖3給出了CPU-OpenMP八線程計(jì)算和GPU-CUDA計(jì)算相對于CPU單線程的計(jì)算加速比。其中，圖3（a）的縱坐標(biāo)用線性表示，圖3（b）的縱坐標(biāo)用指數(shù)表示，并且圖3（b）上標(biāo)出了不同階數(shù)矩陣乘法的計(jì)算加速比。從圖3（a）可以看出，相對于不同階數(shù)的矩陣乘法，CPU-OpenMP八線程計(jì)算的加速比變化不大，基本在6左右，低于所采用的線程數(shù)目。從圖3（b）可以發(fā)現(xiàn)，隨著矩陣階數(shù)的增加，GPU-CUDA獲得的計(jì)算加速比顯著增大。當(dāng)矩陣階數(shù)為n=8000時，GPU-CUDA的計(jì)算加速比達(dá)到了570倍以上，這樣的加速效果是相當(dāng)可觀的。

對比CPU單線程計(jì)算和CPU-OpenMP多線程并行計(jì)算的結(jié)果，發(fā)現(xiàn)兩種計(jì)算手段得到的矩陣數(shù)據(jù)是完全相同的，即CPU-OpenMP多線程并行計(jì)算不會產(chǎn)生計(jì)算誤差。然而，對比發(fā)現(xiàn)，采用GPU-CUDA得到的矩陣數(shù)據(jù)與CPU計(jì)算得到的結(jié)果有所差異，這可能是由于GPU與CPU 對于float浮點(diǎn)數(shù)協(xié)議的差異[6]。為了體現(xiàn)GPU-CUDA并行計(jì)算所帶來的誤差，我們對比了GPU-CUDA與CPU對不同階矩陣乘法的計(jì)算結(jié)果，并統(tǒng)計(jì)了最大相對誤差，其計(jì)算方式為RE=MAX{[（AB） -（AB） ]/（AB） }，計(jì)算結(jié)果見表4。可以看出，對于低階數(shù)的矩陣乘法（n=500），GPU-CUDA計(jì)算得到的矩陣數(shù)據(jù)誤差較大；對于其他階數(shù)的矩陣，GPU-CUDA計(jì)算得到的矩陣數(shù)據(jù)誤差較小，甚至為0（n=1000）.結(jié)合圖3（b）給出的計(jì)算加速比對比圖，可以發(fā)現(xiàn)高階數(shù)矩陣乘法的計(jì)算更加適合用GPU-CUDA進(jìn)行加速，此時加速比大且誤差較小；低階數(shù)矩陣乘法的計(jì)算選用GPU-CUDA加速時需慎重，因?yàn)镚PU-CUDA可能會給出較大的計(jì)算誤差。因此，對于低階數(shù)矩陣乘法，宜選用CPU-OpenMP方法進(jìn)行加速。

3 結(jié)論

本文分別采用CPU單線程、CPU-OpenMP多線程和GPU-CUDA并行計(jì)算技術(shù)，對不同階數(shù)的矩陣乘法進(jìn)行計(jì)算并比較了計(jì)算時間。隨著矩陣階數(shù)的增加，CPU單線程所需的計(jì)算時間成線性增加。對于不同階數(shù)的矩陣乘法，CPU-OpenMP多線程計(jì)算都可以加快計(jì)算效率，計(jì)算加速比低于所采用的線程數(shù)目。GPU-CUDA的計(jì)算加速比隨矩陣階數(shù)的增加顯著增加。當(dāng)矩陣階數(shù)為n=8000時，GPU-CUDA的計(jì)算加速比達(dá)到了570倍以上。相對于CPU單線程計(jì)算結(jié)果，CPU-OpenMP的計(jì)算結(jié)果沒有產(chǎn)生誤差，而GPU-CUDA計(jì)算結(jié)果會產(chǎn)生誤差。GPU-CUDA的最大相對誤差分析表明GPU-CUDA并行計(jì)算技術(shù)更加適合高階數(shù)的矩陣乘法的加速計(jì)算，而CPU-OpenMP更加適合低階數(shù)的矩陣乘法的加速計(jì)算。

【參考文獻(xiàn)】

[1]唐兵，Laurent BOBELIN，賀海武.基于MPI和OpenMP混合編程的非負(fù)矩陣分解并行算法[J].計(jì)算機(jī)科學(xué)，2017，44（03）：51-54.

[2]周漫，車欣.大規(guī)模稠密線性方程組求解的并行計(jì)算方法[J].信息與電腦（理論版），2016（11）：88-89.

[3]周海芳，高暢，方民權(quán).基于CUBLAS和CUDA的MNF并行算法設(shè)計(jì)與優(yōu)化[J].湖南大學(xué)學(xué)報（自然科學(xué)版），2017，44（04）：147-156.

[4]Blaise Barney，OpenMP tutorials [M]：https：//computing.llnl.gov/tutorials/openMP/.

[5]NVIDIA，CUDA C programming guide[M].NVIDIA Corporation，2015：11.

[6]遲學(xué)斌，王彥棢，王玨，劉芳.并行計(jì)算與實(shí)現(xiàn)技術(shù)[M]. 北京：科學(xué)出版社，2015.endprint