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

雷耀明

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

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

一、問題背景

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

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

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

串行算法：

三、 模型建立

3.1矩陣相乘按行計算

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

3.2 矩陣相乘按列計算

按列進行劃分是對每一行進行劃分然后發送到每個進程上。我們考慮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是一種基于信息傳遞的并行編程技術。主進程按行劃分矩陣及向量，記錄自身計算所需矩陣分量并調MPI_Send將向量發給各個進程；其余進程調用 MPI_Recv接收主進程發送的矩陣分量及向量分量； 各個進程調用MPI_Scatter按行共享主進程中的矩陣；各個進程進行矩陣向量相乘；各進程調用MPI_Gather將所有向量各個分量聚集到主進程上得到最終結果。

四、數值實驗和結論

MPI結果圖表分析：

（1）隨著矩陣規模的不斷增大，程序的執行時間中，計算時間占主導因素，并行計算的優勢得到了體現，運行時間隨著進程數的增加而逐漸減少。

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

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

【參考文獻】

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

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

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