在向量中搜索最大值和索引

Question

我正在尝试并行化这段在列上搜索最大值的代码。问题是并行版本比串行版本运行得慢

可能由于最大值和索引的同步，主元（列上的最大值）的搜索速度较慢，对吗？

int i,j,t,k;
    // Decrease the dimension of a factor 1 and iterate each time
for (i=0, j=0; i < rwA, j < cwA; i++, j++) {
    int i_max = i; // max index set as i
    double matrixA_maxCw_value = fabs(matrixA[i_max][j]);
    #pragma omp parallel for reduction(max:matrixA_maxCw_value,i_max) //OVERHEAD
    for (t = i+1; t < rwA; t++) {
        if (fabs(matrixA[t][j]) > matrixA_maxCw_value) {
            matrixA_maxCw_value = matrixA[t][j];
            i_max = t;
        }
    }
    if (matrixA[i_max][j] == 0) {
        j++; //Check if there is a pivot in the column, if not pass to the next column
    }
    else {
        //Swap the rows, of A, L and P
        #pragma omp parallel for //OVERHEAD
        for (k = 0; k < cwA; k++) {
            swapRows(matrixA, i, k, i_max);
            swapRows(P, i, k, i_max);
            if(k < i) {
                swapRows(L, i, k, i_max);
            }
        }
        lupFactorization(matrixA,L,i,j,rwA);
    }
}

void swapRows(double **matrixA, int i, int j, int i_max) {
    double temp_val = matrixA[i][j];
    matrixA[i][j] = matrixA[i_max][j];
    matrixA[i_max][j] = temp_val;   
}

我不想要不同的代码，但我只想知道为什么会这样，在维度为 1000x1000 的矩阵上，串行版本需要 4.1s，并行版本需要 4.28s

同样的事情（开销很小但确实存在）发生在行的交换上，理论上可以毫无问题地并行完成，为什么会这样？

Answer 1

您的并行化至少有两处错误

#pragma omp parallel for reduction(max:matrixA_maxCw_value,i_max) //OVERHEAD
for (t = i+1; t < rwA; t++) {
    if (fabs(matrixA[t][j]) > matrixA_maxCw_value) {
        matrixA_maxCw_value = matrixA[t][j];
        i_max = t;
    }
}

你得到的是所有索引中最大的，但这并不意味着它属于最大值。例如查看以下数组：

[8, 7, 6, 5, 4 ,3, 2 , 1]

如果您使用两个线程并行化，第一个线程将具有 max=8 和 index=0，第二个线程将具有 max=4 和 index=4。减少完成后，最大值将是 8，但索引将是 4，这显然是错误的。

OpenMP 具有考虑单个目标值的内置缩减函数，但是在您的情况下，您想要减少考虑 2 个值 max 和数组索引。在 OpenMP 4.0 one can create its own reduction functions (i.e., User-Defined Reduction).

之后

您可以查看实现此类逻辑的完整示例here

另一个问题是这部分：

   #pragma omp parallel for //OVERHEAD
    for (k = 0; k < cwA; k++) {
        swapRows(matrixA, i, k, i_max);
        swapRows(P, i, k, i_max);
        if(k < i) {
            swapRows(L, i, k, i_max);
        }
    }

您正在并行交换这些元素，这会导致状态不一致。

首先你需要解决这些问题，然后再分析你的代码为什么没有加速。

先正确后效率。但是除了当前实现的很多加速之外，并行执行的计算量足以证明并行的开销。

在向量中搜索最大值和索引

Search of max value and index in a vector

c

parallel-processing

performance

multithreading

openmp