通过 openmp parallel 进行矩阵向量乘法和加法任务

Question

我想计算以下矩阵向量乘法和加法运算

y = (A + C + C^T + R + R^T + D1 + D1^T + D2 + D2^T)x

我可以使用openmp中的并行任务来加速这个操作吗？代码如下

    y.setZero();
    int ny = y.size();
#pragma omp parallel shared(x)
{
#pragma omp single
    {
        VectorXd yA(ny),yC(ny), yCt(ny), yR(ny), yRt(ny), yD1(ny), yD1t(ny), yD2(ny), yD2t(ny);
        yA.setZero();
        yC.setZero();
        yCt.setZero();
        yR.setZero();
        yRt.setZero();
        yD1.setZero();
        yD1t.setZero();
        yD2.setZero();
        yD2t.setZero();

    #pragma omp task
        yA = A * x;
    #pragma omp task
        yC = C * x;
    #pragma omp task
        yCt = C.transpose() * x;
    #pragma omp task
        yR = R * x;
    #pragma omp task
        yRt = R.transpose() * x;
    #pragma omp task
        yD1 = D1 * x;
    #pragma omp task
        yD1t = D1.transpose() * x;
    #pragma omp task
        yD2 = D2 * x;
    #pragma omp task
        yD2t = D2.transpose() * x;

    #pragma omp taskwait
        y = yA + yC + yCt + yR + yRt + yD1 + yD1t + yD2 + yD2t;
    }
};

此代码基于 Eigen 库。与不使用 openmp 相比，我无法在计算机中观察到明显的加速。但我认为它可以与openmp并行。所以我问这个问题。如果有人能回答我的问题，我将不胜感激。

Answer 1

Can I use the tasking parallel in openmp to accelerate this operation? The code is as follow Blockquote

是的。虽然在您的代码中，我可以看到 3 处需要改进的地方。

1) 数据共享 - 当开始使用 OpenMP 时，我建议在您的任务中明确使用 default(none), shared(...) or firstprivate(...) - 这样您就可以了解变量的实际复制方式。

2) 缩放 - 在性能方面，您的代码不会超过 9 个内核，因为您只表达 9 个任务。
做代数的时候，你可以通过块操作来任务化应用程序。
例如，您可以将 A = B + C 拆分为 4 个独立的块操作 （使用 Eigen 接口...）

A(0, 0, n/2, n/2) = B(0, 0, n/2, n/2) + C(0, 0, n/2, n/2)
A(0, n/2, n/2, n/2) = B(0, n/2, n/2, n/2) + C(0, n/2, n/2, n/2)
A(n/2, 0, n/2, n/2) = B(n/2, 0, n/2, n/2) + C(n/2, 0, n/2, n/2)
A(n/2, n/2, n/2, n/2) = B(n/2, n/2, n/2, n/2) + C(n/2, n/2, n/2, n/2)

此处的块大小为 n/2 并定义了您的 tasks granularity

3) 同步 - 为了确保正确的执行顺序，您使用了 # pragma omp taskwait - 这是一个等待先前生成的任务完成的显式屏障。
从 OpenMP 4.0 开始，任务可以 dependences 来保证更精细级别的执行顺序。

混淆 - 我用你的问题的 3 个版本做了一个 micro-benchmark - source

顺序 - 计算在 1 个核心上完成
taskwait - 你的版本
block - 使用 Eigen 块操作和 OpenMP 依赖项。
我将计算分成 2 个操作，并使用 m 块对每个操作进行任务化。
- add - M := A + C + C^T + R + R^T + D1 + D1^T + D2 + D2^T
- mult - y := M.x
  在这个图中，是 m=2 的依赖任务图 - add(0, 0) 任务在 top-left 块上工作，add(1, 0) 任务在 top-right 块上工作，等等... - mult 任务取决于在同一行块上工作的 add 任务 - norm 任务是正确性检查。

我运行它在 16 个核心上，具有 n=4,096 和 m=16（每个 line-wise 操作的块数）。这是我的结果

sequential version took 1.28707 s.
taskwait version took 0.177616 s.(SUCCESS)
task version took 0.128707 s.(SUCCESS)

我又运行了，不过这次是64核，m=64

sequential version took 1.31316 s.
taskwait version took 0.170817 s.(SUCCESS)
task version took 0.0785489 s.(SUCCESS)

“块版本”随内核扩展，但“taskwait”版本不扩展。

这是第一次执行的甘特图(m=16)。蓝色大任务对应 sequential-version 执行，红色任务对应 taskwait-version 执行。紫色和粉红色的任务分别对应block-version.

的add和mult任务

如您所见，taskwait-version 仅使用 16 个内核中的 9 个，而 block-version 可以使用所有内核。

放大 block-version，并使用箭头启用依赖渲染

这些数字是使用 Multi-Processor-Computing (MPC) 生成的 - 它实现了 OpenMP 运行时间和跟踪工具。

通过 openmp parallel 进行矩阵向量乘法和加法任务

Task for matrix-vector multiplication and adding by openmp parallel

openmp

matrix-multiplication