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”的文献以获取高效算法的参考。

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

openmp increasing number of threads increases the execution time

c

c++

openmp