郝 靜 劉雅坤

中國石油大學(xué)（華東）理學(xué)院

矩陣向量相乘并行算法分析與實(shí)現(xiàn)

郝 靜 劉雅坤

中國石油大學(xué)（華東）理學(xué)院

矩陣運(yùn)算是工程數(shù)值計(jì)算中一種常見的運(yùn)算方式。大量的高維矩陣運(yùn)算對數(shù)學(xué)計(jì)算提出了新的要求。本文針對行劃分，列劃分不同模式，給出OpenMPI算法的分析與實(shí)現(xiàn)，并得到按行劃分的優(yōu)勢。

矩陣向量，并行，OpenMP；

一、問題背景與提出

矩陣向量相乘是數(shù)學(xué)以及工程中經(jīng)常遇到的一種計(jì)算方式，矩陣向量乘法在許多解決實(shí)際問題中都有應(yīng)用，但矩陣計(jì)算因其維數(shù)增大而造成的計(jì)算量增大是計(jì)算科學(xué)中需要進(jìn)一步解決的問題。利用并行計(jì)算方法，將矩陣向量進(jìn)行分發(fā)，使每個進(jìn)程同時(shí)進(jìn)行計(jì)算，將會大大減少計(jì)算的時(shí)間，提高計(jì)算效率。

并行計(jì)算（Parallel Computing）是指同時(shí)使用多種計(jì)算資源解決計(jì)算問題的過程，是提高計(jì)算機(jī)系統(tǒng)計(jì)算速度和處理能力的一種有效手段。它的基本思想是用多個處理器來協(xié)同求解同一問題，即將被求解的問題分解成若干個部分，各部分均由一個獨(dú)立的處理機(jī)來并行計(jì)算?，F(xiàn)實(shí)社會中，越來越多的數(shù)據(jù)信息需要計(jì)算機(jī)處理，串行計(jì)算機(jī)程序技術(shù)已經(jīng)不能滿足人們的需求，并行計(jì)算會越來越受到人們的青睞。

從一個串行程序得到一個并行程序的工作一般由四個步驟構(gòu)成：1）將計(jì)算分解成任務(wù)：分解的主要目標(biāo)就是要揭示足夠的并行性，從而盡量保持所有的進(jìn)程在所有時(shí)間都忙，同時(shí)要注意由此引起的任務(wù)管理開銷不能太大。2）將任務(wù)分配給進(jìn)程：分配的基本性能目標(biāo)是在進(jìn)程之間做負(fù)載平衡，要減少進(jìn)程之間的通信量，還要減少運(yùn)行時(shí)管理這種分配的開銷。3）在進(jìn)程之間協(xié)調(diào)必要地?cái)?shù)據(jù)訪問、通信和同步。4）將進(jìn)程映射或綁定到處理器。本文就是將矩陣與向量相乘分解成向量與向量相乘，分發(fā)給幾個進(jìn)程分別計(jì)算，將其并行化。

二、矩陣向量的串行算法描述

矩陣向量乘法是將一個mxn的矩陣A= （0≤i≤m-1，0≤j≤n-1）乘以nx1的向量B=得到一個具有m個元素的列向量C=。矩陣向量串行算法假設(shè)一次乘法和加法運(yùn)算時(shí)時(shí)間為一個單位時(shí)間，則矩陣向量乘法算法的時(shí)間復(fù)雜度為O（mn），如果矩陣是方陣，那么復(fù)雜度就變?yōu)镺（）。

矩陣向量串行算法：

三、模型建立

矩陣并行計(jì)算時(shí)，將矩陣進(jìn)行按行、列、塊三種方式進(jìn)行劃分，矩陣和向量按進(jìn)程個數(shù)進(jìn)行分發(fā)，接收矩陣和向量的進(jìn)程做相應(yīng)的運(yùn)算，最后將結(jié)果進(jìn)行規(guī)約綜合。本文只討論進(jìn)程個數(shù)恰能完全將矩陣向量平均分配的情況。

通過已有相關(guān)文獻(xiàn)的查閱，我們得知三種分法方式中，隨著維數(shù)的增高，按行劃分是最有效的方法；按列劃分在分發(fā)時(shí)需要分發(fā)的次數(shù)為維數(shù)的倍數(shù)，分發(fā)的時(shí)間將大大增加。按塊劃分需要將矩陣進(jìn)行塊劃分，按塊劃分的優(yōu)勢在矩陣與矩陣相乘的算法設(shè)計(jì)中優(yōu)勢比較明顯。

在本文中，作者通過設(shè)計(jì)按塊劃分矩陣與向量相乘算法中發(fā)現(xiàn)，算法與按行、按列算法設(shè)計(jì)有很大的相似之處，所以，本文將著重考慮矩陣與向量相乘的按行與按列兩種算法并行的情況。

3.1按行劃分矩陣

矩陣向量相乘時(shí)，我們考慮nxn維矩陣A在n個進(jìn)程間劃分的情況。將計(jì)算機(jī)進(jìn)程編號為0，1，2…n-1。則每一個進(jìn)程都會存儲1xn維矩陣。進(jìn)程會存儲ai1，ai2，ai3…ain。并且負(fù)責(zé)計(jì)算。向量C的存儲方法與B相同。

考慮P（p＜n）個進(jìn)程的情況，每個進(jìn)程存儲1×n/p維矩陣，每個進(jìn)程的矩陣要與向量B相乘，所得的向量C與向量B的乘法類似。所得到的向量即為所求。通信時(shí)間為O（n/p），計(jì)算時(shí)間為O（n2/p）。

3.2按列劃分矩陣

按列進(jìn)行劃分是對每一行進(jìn)行劃分然后發(fā)送到每個進(jìn)程上。我們考慮n×n維矩陣A在n個進(jìn)程間劃分的情況。將計(jì)算機(jī)進(jìn)程編號為0，1，2…n-1。對于矩陣的第一行，a11…a1n進(jìn)行劃分，進(jìn)程pi接收到元素的為a1i，每一行劃分后，進(jìn)程pi接收到的元素為a1i…ani。進(jìn)程pi做的計(jì)算為cj=aji×bj，j=1…n每一個進(jìn)程都會得到一個向量，將每一個向量所對應(yīng)的元素相加，即得到最終的向量c。

3.3按塊劃分矩陣

假設(shè)p2等于n，將矩陣劃分成不同的矩陣塊，每一個矩陣塊上的矩陣為p×p維。將劃分的矩陣塊發(fā)送到每一個進(jìn)程，進(jìn)程上進(jìn)行p×p維矩陣與的乘法運(yùn)算。然后將計(jì)算同一行的矩陣塊的進(jìn)程結(jié)果相加，于同一列矩陣塊相組合，得到最終的結(jié)果。

四、矩陣向量的并行算法描述

4.1基于OpenMP的多核并行算法的設(shè)計(jì)

OpenMP是一種面向共享內(nèi)存以及分布式共享內(nèi)容的多處理器多線程進(jìn)行編程語言，是一種能夠被應(yīng)用于顯式指導(dǎo)多線程、共享內(nèi)存并行的應(yīng)用程序編程接口。OpenMP具有良好可移植性，支持多種編程語言。OpenMP的編程模型以線程為基礎(chǔ)，通過編譯指導(dǎo)語句來顯式地指導(dǎo)并行化，常用編譯指導(dǎo)語句有parallel、parallel for、parallel sections，通過特定的#pragma omp進(jìn)行標(biāo)示。

利用parallel進(jìn)行并行的原理是編譯時(shí)將同一段代碼復(fù)制到每一個線程上編譯，然后在本線程上執(zhí)行編譯好的程序。所有線程程序相同，但是執(zhí)行效果不同，比如利用OpenMP封裝的內(nèi)置函數(shù)omp_ get_thread_num（）來獲得線程號，然后根據(jù)線程號完成不同任務(wù)。執(zhí)行原理和WinAPI利用線程號相同，都是獲取線程號來分不同任務(wù)，只不過線程號獲取方式不同。利用編譯指導(dǎo)語句parallel執(zhí)行并行計(jì)算是粗粒度的并行，并且在parallel的末尾有一個隱含的同步屏障，所有線程完成所需的重復(fù)任務(wù)后，將各個同步屏障匯合，然后可以從各個線程收集所需要的數(shù)據(jù)合成所需要結(jié)果。

利用parallel for 并行原理是采用工作分配的執(zhí)行方式，將循環(huán)所需要工作量按一定方式分配到各個執(zhí)行線程，所有線程執(zhí)行工作總和是原串行完成工作量。此方式對一個確定并且完整的for循環(huán)進(jìn)行分割，分割成多段在不同CPU上運(yùn)行。

4.2按行劃分矩陣向量相乘

程序要點(diǎn)：

利用parallel指令的復(fù)制執(zhí)行的方式，利用各個線程的ID號劃分了工作任務(wù)，將矩陣按行劃分分配給各個線程，通過獲取線程號來分布不同任務(wù)。

實(shí)現(xiàn)按行劃分的矩陣向量乘法的程序關(guān)鍵代碼如下：

4.3按列劃分的算法實(shí)現(xiàn)

程序要點(diǎn)：

利用parallel指令的復(fù)制執(zhí)行的方式，利用各個線程的ID號劃分了工作任務(wù)，將矩陣按列劃分分配給各個線程，通過獲取線程號來分布不同任務(wù)。

實(shí)現(xiàn)按列劃分的矩陣向量乘法的程序關(guān)鍵代碼如下：

五、算法實(shí)現(xiàn)

5.1最終計(jì)算結(jié)果

進(jìn)行上機(jī)實(shí)驗(yàn)，開發(fā)環(huán)境為Microsoft Visual Studio 2010（旗艦版）

表一　4個進(jìn)程計(jì)算結(jié)果（OpenMP）

表二　8個進(jìn)程計(jì)算結(jié)果（OpenMP）

六、數(shù)值實(shí)驗(yàn)和結(jié)論

6.1圖表分析

圖一　4個進(jìn)程計(jì)算結(jié)果加速比增長關(guān)系（openMP）

圖二　8個進(jìn)程計(jì)算結(jié)果加速比增長關(guān)系（openMP）

6.2實(shí)驗(yàn)結(jié)論

通過對上述圖表分析，我們可得到以下結(jié)論：

（1）OpenMP中隨著維數(shù)的增長，行劃分和列劃分方式加速比逐漸增長，但所用的進(jìn)程數(shù)目較大時(shí)，加速比和效率較為明顯，因?yàn)榫€程數(shù)目越大，每個線程分配的任務(wù)量相對越小，運(yùn)行效率越快。

（2）隨著維數(shù)的增高，按行劃分是相對有效的方法。按列劃分在分發(fā)時(shí)需要分發(fā)的次數(shù)為維數(shù)的倍數(shù)，分發(fā)的時(shí)間將大大增加。按列劃分需要將矩陣進(jìn)行塊劃分。然后再進(jìn)行分發(fā)，相對來講，增大了時(shí)間的消耗。

（3）在工程計(jì)算中，當(dāng)矩陣維數(shù)較大時(shí)，可以采取按行劃分的方式大大增加計(jì)算速度，而當(dāng)矩陣維數(shù)較小時(shí)，建議使用串行算法。

［1］ 朱建偉.多線程并行快速求解e值的六種方法［J］.現(xiàn)代計(jì)算機(jī)：普及版.2013（17）.15-20

［2］多核系列教材編寫組.多核程序設(shè)計(jì)［M］.北京.清華大學(xué)出版社，2007

［3］ 鄧倩妮.并行程序設(shè)計(jì)導(dǎo)論［M］.北京.北京機(jī)械工業(yè)出版社.2012.8

［4］尚智，陳碩.大型矩陣相乘并行計(jì)算的特性分析［J］.Software Engineering，2013.02（1）：15-19

郝靜（1994—），女，漢族，山東煙臺人，中國石油大學(xué)（華東）理學(xué)院，2013級本科生，數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)

劉雅坤（1995—），女，漢族，山東青島人，中國石油大學(xué)（華東）理學(xué)院，2013級本科生，數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)