c - 性能:在列 [OpenMP，C] 上高效减少二维数组

Question

我想实现非常有效的并行缩减操作(即求和):二维数组(行长内存布局中的内存缓冲区)的每一列都应求和到一维数组的条目。

为了更清楚预期的输入和输出

double* array = malloc(sizeof(double) * shape0 * shape1) /* (shape0*shape1) 2-d array */
double* out = malloc(sizeof(double) * shape1) /* where out[j] = sum_j(array_ij) */

并行化行的总和非常简单且高效，因为这些值在内存中是连续的，并且不存在竞争条件的风险。我发现这很好用

void sum_rows(double* array, int shape0, int shape1, double* out) {
    int i, j;
    #pragma omp parallel for private(j) schedule(guided) 
    for (i=0; i < shape0; i++){
        for (j=0; j < shape1; j++){
            out[i] += array[shape1 * i + j];
        }
    }
}

我发现更难平行于另一个轴。这应该是一个简单的并行方法，但我无法找到明确的答案，即最有效的编程方法是什么。

这是天真的串行代码，我想编写一个高效的并行版本:

void sum_columns(double* array, int shape0, int shape1, double* out) {
    int i, j;
    for (i=0; i < shape0; i++){
        for (j=0; j < shape1; j++){
            out[j] += array[shape1 * i + j];
        }
    }
}

注意:我已经阅读了以下 q/a，但它们并没有让我对天真的顺序代码有任何加速:

Parallelizing matrix times a vector by columns and by rows with OpenMP

OpenMP average of an array

Reduction with OpenMP

Answer 1

只是报告我经过一些尝试后能够实现的更快的实现。在这里，我将列分配给不同的线程，以尽可能在本地工作并避免错误共享的方式。

void sum_columns(double* array, int N_rows, int N_cols, double* out, int n_threads) {
    omp_set_dynamic(0);
    omp_set_num_threads(n_threads);
    #pragma omp parallel
    {
        /* private vars */
        int i, j, id, N_threads, col_chunk_size, start_col, end_col;
        /* ICVs */
        id = omp_get_thread_num();
        N_threads = omp_get_num_threads();
        /* distribute cols to different threads */
        col_chunk_size = N_cols / N_threads;
        start_col = id * col_chunk_size;
        end_col = (id+1) * col_chunk_size;
        if (id == N_threads - 1) end_col = N_cols;

        /* main loop */
        for (i=0; i < N_rows; i++){
            for (j=start_col; j < end_col; j++){
                out[j] += array[N_cols * i + j];
            }
        }
    }
 }