并行矩阵乘法
Comment实验1 矩阵乘法
191240046 孙博文
实验原理
设 A 和 B 是两个 $n\times n$ 矩阵，它们的乘积也是 $2\times 2$ 矩阵。根据乘积关系，我们有
$$
C[i, j] = \Sigma^{n}_{i = 1}A[i, k]\times B[k, j]
$$
串行程序中，C 的每个元素需要 n 次乘法和 n - 1 次加法。因此，C 的计算复杂度为 $O(n^3)$。
实际上，C 中个元素的计算在本质上是独立的，可以将矩阵划分成多个块，这样串行矩阵乘法中矩阵元素的乘-加运算代换为子矩阵的乘-加运算，然后指派给不同的处理器，实现并行运算。
实现思路
在运算的最外层循环前加上：
1 |
|
让 omp 自动对计算过程进行划分。
实验结果
在矩阵乘法运算开始之前用 omp_get_wtime() 记录下开始的时间，在运算完成后再用当前时间减去开始时间得到运算过程持续的时间。
输入的矩阵阶数 $n = 1000$，
$$
\begin{aligned}
A = \begin{bmatrix}
1 & 2 & 3 & ... & n\\
2 & 3 & 4 & ... & n + 1\\
... & ... & ... & ... & ...\\
n + 1 & n + 2 & n + 3 & ... & 2n - 1\\
\end{bmatrix}\ \ \ \
B = \begin{bmatrix}
1 & ... & 1\\
... & ... & ...\\
1 & ... & 1\\
\end{bmatrix}
\end{aligned}
$$
编译时开启优化选项 -O2，得到的可执行程序在 6 核心 12 线程，3.4GHz 的平台上，得到计算过程的运行时间结果如下：
| 线程数 | 1 | 2 | 4 | 8 | 16 |
|---|---|---|---|---|---|
| 1 | 0.981532 | 0.521334 | 0.265093 | 0.294094 | 0.338403 |
| 2 | 0.914313 | 0.487340 | 0.262216 | 0.462756 | 0.356789 |
| 3 | 0.937469 | 0.493963 | 0.262745 | 0.273746 | 0.352335 |
| 4 | 0.863467 | 0.519115 | 0.270767 | 0.273420 | 0.347093 |
| 5 | 0.981426 | 0.510974 | 0.263687 | 0.412166 | 0.320763 |
| AVG | 0.935641 | 0.506545 | 0.264902 | 0.343236 | 0.343077 |
| 加速比 | 1.00 | 1.85 | 3.53 | 2.73 | 2.73 |
| 效率 | 1 | 0.92 | 0.88 | 0.34 | 0.17 |
