尽管存在数据依赖性，仍尝试并行化

Question

我正在尝试并行化矩阵乘法。我遇到了 Fox 算法，它可以将整个过程分为 3 个步骤。你可以查一下算法。我已附上图片。 代码：

void matmul_fox(int *matrixA, int *matrixB, int *zeroMatrix, int n){
    #pragma acc kernels copyin(matrixA[0:n*n], matrixB[0:n*n]) copy(zeroMatrix[0:n*n])
    {
    // Operation 1
    #pragma acc loop independent
    for (int i = 0; i < n; i++){ // Extract the diagonal from arr1
        #pragma acc loop independent
        for (int j = 0; j < n; j++){ // Add arr3 and multiplication of diag(broadcasted)*arr2
            #pragma acc loop independent reduction (+: zeroMatrix[0:n*n])
            for (int k = 0; k < n; k++){
                zeroMatrix[j * n + k] += matrixA[j * n + j] * matrixB[j * n + k]; 
            }
        }

     
    // Operation 2
        // Shift-up on the rows of arr2
        #pragma acc loop independent
        for (int a = 0; a < n; a++) {
            int temp1 = matrixB[0 * n + a];
            #pragma acc loop independent
            for (int j = 0; j < n - 1; j++) {
                matrixB[j * n + a] = matrixB[(j + 1) * n + a];
        }
        matrixB[(n - 1) * n + a] = temp1;
    }
    // Operation 3
        // Shift-left on the rows of arr1
        #pragma acc loop independent
        for (int b = 0; b < n; b++){
            int temp2 = matrixA[b * n + 0]; // Store the first element of the row
            #pragma acc loop independent
            for (int j = 0; j < n - 1; j++){
                matrixA[b * n + j] = matrixA[b * n + (j+1)]; // Shift elements to the left
            }
        matrixA[b * n + (n - 1)] = temp2; // Place the first element at the end
        }
 
    }   }
}

由于操作 2 和操作 3 具有依赖性，因此我无法将这 3 个操作全部并行化。不过我在某处读到，我们可以使用 async、wait 和 update 等子句来解决这个问题。也许操作 2 和操作 3 可以等到操作 1 完成，一旦完成，操作 2 和操作 3 就可以并行完成，因为它们之间没有依赖关系。

我尝试不使用等待子句，但由于存在可见的依赖关系，因此给出了错误的结果。在不使用OpenACC的情况下，代码可以正常运行，但执行时间比传统的顺序算法要长。如果 Fox 算法可以并行工作，我可以期待更好的性能。

Answer 1

操作 2 和 3 中的外部“i”循环不可并行化，内部“j”循环也不可并行化。您只需要使用三个卸载区域来并行化中间循环。鉴于操作 2 和 3 相当小，我还将通过 OpenACC 异步子句同时启动这两个卸载区域。额外的等待子句确保操作 1 在启动 2 和 3 之前完成。

例如：

// Parallel implementation using Fox algorithm
void matmul_fox(int *matrixA, int *matrixB, int *zeroMatrix, int n){
#pragma acc data copyin(matrixA[0:n*n], matrixB[0:n*n]) copy(zeroMatrix[0:n*n])
        {
                for (int i = 0; i < n; i++){ // Extract the diagonal from matrixA
#pragma acc parallel loop collapse(2) async(1) wait(2,3)
                        for (int j = 0; j < n; j++){ // Add zeroMatrix and multiplication of diag(matrixA)*matrixB
                                for (int k = 0; k < n; k++){
                                        zeroMatrix[j * n + k] += matrixA[j * n + j] * matrixB[j * n + k];
                                }
                        }

                        // Cyclic Shift-up on the rows of matrixB
#pragma acc parallel loop async(2) wait(1)
                        for (int a = 0; a < n; a++) {
                                int temp1 = matrixB[0 * n + a];
                                for (int j = 0; j < n - 1; j++) {
                                        matrixB[j * n + a] = matrixB[(j + 1) * n + a];
                                }
                                matrixB[(n - 1) * n + a] = temp1;
                        }

                        // Cyclic Shift-left on the rows of matrixA
#pragma acc parallel loop async(3) wait(1)
                        for (int b = 0; b < n; b++){
                                int temp2 = matrixA[b * n + 0]; // Store the first element of the row
                                for (int j = 0; j < n - 1; j++){
                                        matrixA[b * n + j] = matrixA[b * n + (j+1)]; // Shift elements to the left
                                }
                                matrixA[b * n + (n - 1)] = temp2; // Place the first element at the end
                        }
                }
#pragma acc wait
        }
}