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

雷耀明

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

【關鍵詞】 并行計算 矩陣相乘 MPI

一、問題背景

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

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

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

串行算法：

三、 模型建立

3.1矩陣相乘按行計算

特殊地，考慮B矩陣為，矩陣向量相乘時，我們考慮nxn維矩陣A在n個進程間劃分的情況。將計算機進程編號為，0，1，2…n-1 。則每一個進程都會存儲1xn維矩陣。進程會存ai1，ai2，ai3…ain。并且負責計算。向量C的存儲方法與B相同。考慮P（p

3.2 矩陣相乘按列計算

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

3.3 基于MPI的多核并行算法的設計

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

四、數(shù)值實驗和結論

MPI結果圖表分析：

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

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

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

【參考文獻】

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

[2] 多核系列教材編寫組.多核程序設計[M].北京.清華大學出版社，2007.

[3] 周燦，楊小帆.矩陣乘法的并行算法研究分析.計算機應用研究.