如何在两个子矩阵相乘的同时获得性能增强?

Question

我有一个程序乘驻留在同一个容器矩阵的两个子矩阵。我试图通过使用OpenMP API进行并行化来获得一些性能增益。下面是我使用的乘法算法。

#pragma omp parallel for
for(size_t i = 0; i < matrixA.m_edgeSize; i++) {
for(size_t k = 0; k < matrixA.m_edgeSize; k++) {
for(size_t j = 0; j < matrixA.m_edgeSize; j++) {
resultMatrix(i, j) += matrixA(i, k) * matrixB(k, j);
}
}
}

该算法逐行访问两个输入子矩阵的元素，以提高空间局部性的缓存使用率。

还有什么其他的OpenMP指令可以用来从这个简单的算法中获得更好的性能?对于两个子矩阵重叠区域上的操作是否有其他的优化指令?

你可以假设所有的子矩阵都有相同的大小并且它们是方形的。生成的子矩阵驻留在另一个容器矩阵中。

Answer 1

对于矩阵-矩阵乘积，i,j,k索引的任何排列顺序计算正确的结果。平行的，不是这样的。在您的原始代码中，k迭代不会写入唯一的位置，因此您不能只是折叠外部两个循环。做一个k,j交换，然后是允许的。

当然，OpenMP可以让你从一个核心的5%效率提高到所有核心的5%效率。你真的想要阻断循环。但这要难得多。参见Goto和van de Geijn的论文。

Answer 2

我正在添加一些与主矩阵相关的东西。你会用这个代码来乘两个更大的矩阵吗?然后在不同迭代之间重用其中一个子矩阵，并可能从CPU缓存中获益。例如，如果一个矩阵有4个子矩阵，则每个子矩阵使用两次，以在结果矩阵上获得一个值。

为了最大限度地利用缓存，重用的数据应该保存在同一个线程(核心)的缓存中。要做到这一点，也许最好将工作分配级别移动到选择两个子矩阵的位置。

就像这样:

select sub-matrix A
#pragma omp parallel for
select sub-matrix B
for(size_t i = 0; i < matrixA.m_edgeSize; i++) {
for(size_t k = 0; k < matrixA.m_edgeSize; k++) {
for(size_t j = 0; j < matrixA.m_edgeSize; j++) {
resultMatrix(i, j) += matrixA(i, k) * matrixB(k, j);
}
}
}  

可以更快地工作，因为所有的数据总是保持在同一个线程(核心)。