openmp增加线程数会增加执行时间

Question

我正在实现稀疏矩阵乘法(元素类型std::complex)转换为CSR(压缩稀疏行)格式后，我使用openmp，但我注意到，增加线程数量并不一定会提高性能，有时是完全相反的!为什么会这样呢?我能做些什么来解决这个问题?

typedef std::vector < std::vector < std::complex < int >>> matrix;
struct CSR {
std::vector<std::complex<int>> values; //non-zero values
std::vector<int> row_ptr; //pointers of rows
std::vector<int> cols_index; //indices of columns
int rows; //number of rows
int cols; //number of columns
int NNZ; //number of non_zero elements
};
const matrix multiply_omp (const CSR& A,
const CSR& B,const unsigned int num_threds=4) {
if (A.cols != B.rows)
throw "Error";
CSR B_t = sparse_transpose(B);
omp_set_num_threads(num_threds);
matrix result(A.rows, std::vector < std::complex < int >>(B.cols, 0));
#pragma omp parallel
{
int i, j, k, l;
#pragma omp for
for (i = 0; i < A.rows; i++) {
for (j = 0; j < B_t.rows; j++) {
std::complex < int > sum(0, 0);
for (k = A.row_ptr[i]; k < A.row_ptr[i + 1]; k++)
for (l = B_t.row_ptr[j]; l < B_t.row_ptr[j + 1]; l++)
if (A.cols_index[k] == B_t.cols_index[l]) {
sum += A.values[k] * B_t.values[l];
break;
}
if (sum != std::complex < int >(0, 0)) {
result[i][j] += sum;
}
}
}
}
return result;
}

Answer 1

您可以尝试改进此算法的缩放，但我会使用更好的算法。您正在为两个稀疏矩阵的乘积分配一个密集矩阵(错误的，但这不是重点)。这是一种浪费，因为两个稀疏矩阵的项目通常不会很密集。

你的算法也有错误的时间复杂度。你在B中搜索行的方式意味着你的复杂度有一个额外的因子比如每行非零的平均数目。一个更好的算法是假设每一行的下标都是排序的，然后保留一个指针，告诉你在这一行中走了多远。

阅读有关"Graph Blas"关于高效算法的参考。