張巖

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

【關(guān)鍵詞】矩陣乘法；并行計算；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ù)量巨大，普通的串行計算方式計算效率低下，無法滿足人們對數(shù)據(jù)進(jìn)行快速處理的需求。因此，如何能夠提高計算機(jī)處理“大數(shù)據(jù)”的計算效率已成為人們?nèi)找骊P(guān)注的話題。為了減少計算時間、提升計算效率，并行計算的出現(xiàn)成為解決上述問題的有效方法。與普通的串行計算相比，并行計算將計算任務(wù)分配到計算機(jī)的多個處理器協(xié)同處理，從而提高計算效率。

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

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

1 CPU-OpenMP和GPU-CUDA并行計算技術(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)十分簡單，只需在原來串行計算程序里的for循環(huán)語句里加入#pragma omp parallel for語句即可實(shí)現(xiàn)并行計算[2]。如圖1所示，CPU-OpenMP并行計算的思路是主線程將共享內(nèi)存里的數(shù)據(jù)分配到不同的分線程里進(jìn)行計算，各個分線程完成計算任務(wù)后將結(jié)果返回到主線程，主線程再負(fù)責(zé)分配各個分線程下一步的計算任務(wù)。在CPU-OpenMP代碼編寫過程中，需對不同線程內(nèi)的變量屬性進(jìn)行區(qū)分，避免不同線程里的私有變量被其他線程的計算修改。endprint

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

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

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

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

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

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

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

3 結(jié)論

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

【參考文獻(xiàn)】

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

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

[3]周海芳，高暢，方民權(quán).基于CUBLAS和CUDA的MNF并行算法設(shè)計與優(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é)斌，王彥棢，王玨，劉芳.并行計算與實(shí)現(xiàn)技術(shù)[M]. 北京：科學(xué)出版社，2015.endprint