基于并行存儲優化的矩陣乘法運算

摘要:該文就數值運算中常見的矩陣乘法運算的實現算法展開討論，從時間和空間不同角度分析矩陣乘法運算中影響性能的主要因素，改良了原有算法，提出了基于存儲優先的數據訪問方式，并結合當今比較熱門的并行運算機制，提高了矩陣乘積運算的速度。

關鍵詞:矩陣;復雜度;Cache miss;并行運算;存儲;shared memory

中圖分類號:TP312文獻標識碼:A文章編號:1009-3044(2010)03-693-03

An Improved Parallel Matrix Multiplication Algorithm Based on Memory

WU Meng， LIU Zhen

(College of Computer Science and Technology， China University of Mining and Technology， Xuzhou 221008， China)

Abstract: In this paper， we talk about the realization of the matrix multiplication algorithm， which is common in numerical calculation， from a different perspective of time and space matrix， and discuss its main factors affecting the performance， Improved the original algorithm， based on the priority of the data storage access methods， and compared with today's popular parallel computing mechanism， enhances the speed of the matrix multiplication operation.

Key words: Matrix; complexity; Cache miss; parallel computing; storage; shared memory

1 概述

在數值計算中，矩陣乘法是最基本和經常使用的運算之一，它的性能對數值計算的操作性能產生直接的影響。我們知道，典型n×n稠密矩陣乘法運算的時間復雜度為O(n3)，它的平凡下界是O(n2)。可以用O(nw+e)來表示標準矩陣的乘積運算復雜度，w表示n*n矩陣必須的復雜度2(e>0)[1]。后來Strassen引入分治思想將w+e從3將為2.81(lg7)，目前已知的最好計算時間上界是Coppersmith 和Shmuel Winograd 提出的O(n2.376)。

目前，對于大型矩陣乘積運算的處理普遍采用分治思想，將運算分布在多個結點上。每個結點單獨完成部分運算，然后將結果匯總。基于Coppersmith和Shmuel Winograd的算法(甚至是Strassen的算法)實現復雜，在結點運算中，如果采用，不僅在算法實現難以實現，而且會導致大量的冗雜數據，CPU運算次數少了，但是大量數據的頻繁交換還是會使存儲體的讀取速度遠不及CPU的速度，這樣的交換在追求效益的社會上是不劃算的，因而實際運算中采用的還是經過優化了的普通矩陣乘法。

本文從影響運算性能的實際因素中找到關鍵點，并由此提出優化算法，改善運行環境，從而解決矩陣乘法運算的效率問題。

2 基本思想

2.1 Cache miss以及分塊思想

矩陣乘法在算法上很容易實現，即三重循環 :

matrix multiplication (a， b: matrices)

for i:=0 to n-1

for j:=0 to n-1

begin

cij :=0

for q:=1 to n-1

cij := cij+aiq ×bqj

end

而由于計算機存取數據的時間已經對運算時間產生了影響，Cache的存在一定程度上解決了存儲器傳輸速度和CPU處理速度的瓶頸。但對于大型的數據處理時，數據的讀寫仍制約著運算的效率。在實際運算中，數據讀寫所花的時間已經遠超過CPU有效處理時間。比如，上式中n很大，嵌套循環中的數據頻繁訪問便導致cache hit次數的急劇下降，嵌套循環中的數據訪問順序也同樣導致較多的Cache miss，如此繁瑣無序的Cache讀取使得CPU不得不從內存中單獨讀取所需的數據，而CPU對主存的訪問時間是對Cache訪問時間的10倍左右，使得實際運算效率遠遠低于理論效率。如圖1，當矩陣規模增加時，實際運算時間幾乎成指數方式增長。

由此可見，Cache的有效載入對運算性能的提升起到了舉足輕重的作用?？紤]到影響Cache hit次數的影響因素:1)空間局部性;2)時間局部性，我們從這兩方面入手。

2.1.1 空間局部性

由于Cache讀取數據是以塊(block)為單位的，每操作一次內存，便讀取相鄰的一塊數據。就數組形式存儲的矩陣來說，一般情況下，其在內存中的存儲方式是按行存儲的。[2]即:

Ad.a[s1，s2] = Ad.a[1，1] + {(s1-1)*n + (s2-1)}*k (k為元素大小)

因而，在數據操作時盡可能的對連續數據進行集中處理。我們進行了如下處理:先將matrix b轉置，得到bT，再與a相乘，于是在內層循環中可以對讀取的連續數據塊進行集中處理，而不是標準算法中對matrix b的跨空間讀取，因而在數據較大時(Cache讀取的一塊存不了一次操作所需的所有數據)，有效地降低了Cache miss次數。由圖1可見，當N>500時，改良后的算法比普通算法有近一倍的性能提升。這里，我們姑且將此改良算法稱為T-Matrix，即基于存儲訪問方式優化的算法。

進一步深入Cache的空間因素，當矩陣足夠大時，Cache無法載入一行或一列，或是頻繁的換行換列讀取，直接導致了較多的Cache miss。采用分塊思想可有效解決上述數據過大的問題。通過分塊思想，集中訪問取入Cache的塊狀矩陣，避免了全行全列的讀寫，增強了空間和時間的局部性，分塊的算法如下:

Matrix multiplication (a， b: matricesnb:blockfactor)

for x:=0 to N;y:=0 to N

for i:=0 to N;j:=0 to nb

r = 0;

for k:=0 to nb

r = r + aik*bkj;

cij =cij + r;

分塊思想的難點和重點在于如何定分塊的大小(即nb的大小)，過大過小都可能影響運算性能[3]。根據一般層次，按行或按列分塊的選擇，可以有2*2*2種選擇(考慮到前一個矩陣的列數要和后一個矩陣的行數相同，即aik*bkj)，上述分塊算法在內層循環(也就是上述分塊形式中最小塊)重復使用aik*bkj，而這些數據一直保存在Cache中，提高了Cache hit的效率。

2.1.2 時間局部性

在上例中，將要訪問的一小塊數據在統一的時間內集中處理，避免了不同時間重復讀取相同數據的時間浪費，增強數據的可重復利用性，并將計算所得分批次的順序存儲在matrix c中，這種實現機制從時間利用的角度出發，充分利用數據的重復使用特性，減少了數據讀取的頻繁程度，獲得了較多的Cache hit次數。

…

Begin

for k:=0 to nb

r = r + aik*bkj;

cij =cij + r;

end

2.2 并行機制

討論關于空間時間局部性的算法實現都是基于串行化原理處理的，并未引入并行化或是分布式并行處理的思想。我們下面將從此處著手，提出更加優化的算法。

3 并行處理

并行處理的基本思路就是利用多個部件完成同一個任務。它的好處就在于可以很好的縮小解題規模和縮短解題時間，并且它對硬件的要求不高，因而可以有效地降低成本。

基于分布式存儲，將矩陣乘積運算劃分成相對對立的幾個模塊，每個模塊對應整個數據場的一小部分，而每個CPU則負責這數據處理這一小部分的數據，從而達到分而治之的目的。[4]

基于上述原理，我們提出了并行處理下的優化算法，即PT-M。圖1總體說明了算法的實現機制。Server是分發任務并將結果匯總，是整個系統的控制中心。

一個Process對應著一塊緩存區，將ai對應Process i以及所在的緩沖區。Server將ai復制到相應的緩沖區內，與共享內存中的matrix b完成最終的乘法運算，并將結果同樣保存在shared memory中。圖2顯示了運算過程中數據在不同存儲設備中的流向。

算法實現:

Begin:

將ai按行分組至process i相應的緩沖區內

求的bT;存儲在shared memory中;

for i:= 0 to n

process i: ai*bT;結果存儲在shared memory中;

直接從shared memory讀取最終的結果

end

4 測試結果及分析

圖3為T-M算法與其他算法的比較。

圖4顯示了基于T-M算法優化后的并行運算在n = 4下和普通算法在運算時間上的對比。性能提升上基本在4倍以上，但在規模較小時(N<500)，PT-M算法并沒有多大優勢。另外此種算法在穩定上還有待提高。

5結束語

本文從實際角度出發，就影響矩陣運算性能的因素逐步展開討論，提出了更加優化的算法，并同其它算法進行了比較，驗證了算法的有效性。并行運算在科學運算中經常遇到，單它的實現較為復雜，實現過程中增加了不少外部因素，使得運行效率可能遠不如原有算法?？磥恚P于并行運算的高效實現還有待進一步的研究。

參考文獻:

[1] Cohn H，Kleinberg R，Szegedy B，et al.Group-theoretic Algorithms for Matrix Multiplication[C].Proceedings of the 2006 international symposium on Symbolic and algebraic computation，2006.

[2] Dhamfhere D M.系統編程與操作系統[M].北京:電子工業出版社，2001.

[3] 蔣孟奇，張云泉，宋剛，李玉成.GOTOBLAS一般矩陣乘法高效實現機制的研究[J].計算機工程，2008，34(7):84-86.

[4] 陳國良.并行算法的設計與分析[M].北京:高等教育出版社，2002.

[5] Md Islam N， Md Islam S，Kashem M A，et al.An Empirical Distributed Matrix Multiplication Algorithm to Reduce Time Complexity[C].IMECS 2009，2009.