一、矩陣乘法定義

矩陣 A _{x × y} 和 矩陣 B _{u × v} 相乘的前提條件是 y = = u ，并且相乘后得到的矩陣為 C _{x × v}（即 A 的行和 B 的列構(gòu)成了矩陣 C的行列）；

 二、矩陣類封裝

我們用 C++ 封裝了一個 n × m 的矩陣類，用二維數(shù)組來存儲數(shù)據(jù)，定義如下：

#define MAXN 1000
#define LL __int64

class Matrix {
private:
	int n, m;
	LL** pkData;
public:
	Matrix() : n(0), m(0) {
		pkData = NULL;
	}
	void Alloc() {
		pkData = new LL *[MAXN];            // 1)
		for (int i = 0; i < MAXN; ++i) {
			pkData[i] = new LL[MAXN];
		}
	}
	void Dealloc() {
		if (pkData) {
			for (int i = 0; i < MAXN; ++i) {      // 2)
				delete [] pkData[i];
			}
			delete[] pkData;
			pkData = NULL;
		}
	}
};

1） p k D a t a 可以認(rèn)為是一個二維數(shù)組（ p k D a t a [ i ] [ j ]就是矩陣第 i 行，第 j 列的數(shù)據(jù)），之所以這里用了二維指針，是因為當(dāng) MAXN 很大時，棧上分配不了這么多空間，容易導(dǎo)致棧溢出，所以通過 new 把空間分配在了堆上；2）釋放空間的時候，首先釋放低維空間，再釋放高維空間；

三、矩陣乘法實現(xiàn)

1、ijk式

最簡單的矩陣乘法實現(xiàn)如下：

class Matrix {
	...
public:
	void Multiply_ijk(const Matrix& other, Matrix& ret) {
		// assert(m == other.n);
		ret.Reset(n, other.m);
		int i, j, k;
		for (i = 0; i < n; i++) {
			for (j = 0; j < other.m; j++) {
				for (k = 0; k < m; k++) {
					ret.pkData[i][j] += pkData[i][k] * other.pkData[k][j];
				}
			}
		}
	}
};

這種方法被稱為ijk 式，對矩陣乘法 A × B = C ，枚舉 A 的每一行，再枚舉 B的每一列，分別對應(yīng)相乘后放入矩陣 C的對應(yīng)位置中，如下圖所示；

2、 ikj 式

對上述算法進(jìn)行一些改進(jìn)，交換兩個內(nèi)層循環(huán)的位置，得到如下算法：

class Matrix {
	...
public:
	void Multiply_ikj(const Matrix& other, Matrix& ret) {
		// assert(m == other.n);
		ret.Reset(n, other.m);
		int i, j, k;
		for (i = 0; i < n; i++) {
			for (k = 0; k < m; k++) {
				LL v = pkData[i][k];
				for (j = 0; j < other.m; j++) {
					ret.pkData[i][j] += v * other.pkData[k][j];
				}
			}
		}
	}
};

這種方法被稱為 ikj 式，對矩陣乘法 A × B = C A \times B = C A×B=C，行優(yōu)先枚舉 A A A 的每一個格子，再枚舉 B B B 的每一行，分別對應(yīng)相乘后放入矩陣 C C C 的對應(yīng)位置中，每次相乘得到的 C C C 都是部分積，如下圖所示，用綠色的深淺來表示這個值是否已經(jīng)完整求得；

3、kij 式

對上述算法再進(jìn)行一些改進(jìn)，交換兩個外層循環(huán)的位置，得到如下算法：

class Matrix {
	...
public:
	void Multiply_kij(const Matrix& other, Matrix& ret) {
		// assert(m == other.n);
		ret.Reset(n, other.m);
		int i, j, k;
		for (k = 0; k < m; k++) {
			for (i = 0; i < n; i++) {
				LL v = pkData[i][k];
				for (j = 0; j < other.m; j++) {
					ret.pkData[i][j] += v * other.pkData[k][j];
				}
			}
		}
	}
};

這種方法被稱為 k i j kij kij 式，對矩陣乘法 A × B = C A \times B = C A×B=C，列優(yōu)先枚舉 A A A 的每一個格子，再枚舉 B B B 的每一行，分別對應(yīng)相乘后放入矩陣 C C C 的對應(yīng)位置中，每次相乘得到的 C C C 都是部分積，如下圖所示，用綠色的深淺來表示這個值是否已經(jīng)完整求得；

四、時間測試

由于矩陣乘法本身的時間復(fù)雜度是 O(N3) 的，所以數(shù)據(jù)量越大，越能看出實際效果；

五、原理分析

原因是因為 CPU 訪問內(nèi)存的速度比 CPU 計算速度慢得多，為了解決速度不匹配的問題，在 CPU 與 內(nèi)存 之間加了高速緩存cache。高速緩存 cache 的存在大大提高了 CPU 訪問數(shù)據(jù)的速度。但是當(dāng)內(nèi)存訪問不連續(xù)的時候，就會導(dǎo)致 cache 命中率降低，所以為了加速，就要盡可能使內(nèi)存訪問連續(xù)，即不要跳來跳去。矩陣

六、最后結(jié)論

運行速度： ikj ≈ kij > ijk

模板地址：矩陣乘法模板

到此這篇關(guān)于C++ 利用硬件加速矩陣乘法的實現(xiàn)的文章就介紹到這了,更多相關(guān)C++ 矩陣乘法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論