矩陣向量相乘的并行算法分析

雷耀明

【摘 要】 大規(guī)模矩陣向量相乘是數(shù)值代數(shù)中常用的科學(xué)計(jì)算方式。其維數(shù)增大而造成的計(jì)算量增大是計(jì)算科學(xué)中需要進(jìn)一步解決的問題。本文基于矩陣向量不同模式下的計(jì)算，給出算法的分析與實(shí)現(xiàn)。

【關(guān)鍵詞】 并行計(jì)算 矩陣相乘 MPI

一、問題背景

矩陣是數(shù)學(xué)以及工程中的一個(gè)基本概念，許多科學(xué)計(jì)算問題往往歸結(jié)為對(duì)矩陣的操作，如三維圖像處理、神經(jīng)網(wǎng)絡(luò)等。由于矩陣的運(yùn)算，特別是大規(guī)模矩陣相乘，矩陣的特征值求解等需要大量?jī)?nèi)存并且耗時(shí)的處理過程，單處理機(jī)已經(jīng)無法承受，因此有效地實(shí)現(xiàn)大型的矩陣并行算法在實(shí)際應(yīng)用中是非常重要的。

二、大規(guī)模矩陣向量相乘的串行算法描述

設(shè)A和B是兩個(gè)n×n矩陣，將矩陣A和B的乘積記為C=B×A，那么C也是一個(gè) n×n矩陣，乘積C的第i行第j列的元素等于A的第i行和B的第j列對(duì)應(yīng)的元素乘積的和，可表示為C（i，j）=，特殊地，當(dāng)考慮矩陣B為矩陣向量。采用串行算法在傳統(tǒng)計(jì)算機(jī)上計(jì)算矩陣乘法時(shí)，需要使用比較多的工作單源和存儲(chǔ)單元，計(jì)算A和B的乘積的結(jié)果矩陣C時(shí)，每計(jì)算出C的一個(gè)元素，需要做n 次乘法和n-1次加法， 逐項(xiàng)計(jì)算個(gè)共需執(zhí)行（n-1）次加法和次乘法，計(jì)算效率將受到很大的影響。

串行算法：

三、 模型建立

3.1矩陣相乘按行計(jì)算

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

3.2 矩陣相乘按列計(jì)算

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

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

MPI是一種基于信息傳遞的并行編程技術(shù)。主進(jìn)程按行劃分矩陣及向量，記錄自身計(jì)算所需矩陣分量并調(diào)MPI_Send將向量發(fā)給各個(gè)進(jìn)程；其余進(jìn)程調(diào)用 MPI_Recv接收主進(jìn)程發(fā)送的矩陣分量及向量分量； 各個(gè)進(jìn)程調(diào)用MPI_Scatter按行共享主進(jìn)程中的矩陣；各個(gè)進(jìn)程進(jìn)行矩陣向量相乘；各進(jìn)程調(diào)用MPI_Gather將所有向量各個(gè)分量聚集到主進(jìn)程上得到最終結(jié)果。

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

MPI結(jié)果圖表分析：

（1）隨著矩陣規(guī)模的不斷增大，程序的執(zhí)行時(shí)間中，計(jì)算時(shí)間占主導(dǎo)因素，并行計(jì)算的優(yōu)勢(shì)得到了體現(xiàn)，運(yùn)行時(shí)間隨著進(jìn)程數(shù)的增加而逐漸減少。

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

（3）隨著矩陣規(guī)模的不斷增大，使用并行計(jì)算的運(yùn)算時(shí)間遠(yuǎn)小于串行算法的運(yùn)算時(shí)間，在大規(guī)模矩陣的運(yùn)算過程中，并行計(jì)算有很大的優(yōu)勢(shì).

【參考文獻(xiàn)】

[1] 多線程并行快速求解e 值的六種方法，朱建偉，劉榮.研究與開發(fā).

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

[3] 周燦，楊小帆.矩陣乘法的并行算法研究分析.計(jì)算機(jī)應(yīng)用研究.