如何并行化这个递归算法

Question

给定一个浮点矩阵 A[N,M] 和一个浮点数组 T[M]，我想使用 OpenMP 并行化以下代码：

for ( int i = 0; i < N; i++ )
{
    T[0] = A[i][0];
    for ( int j = 1; j < M; j++ )
        T[j] = f(A[i][j]-T[j-1]) + A[i][j];

    float v = T[M-1];
    for ( int j = M-2; j >=0; j-- )
    {
        v = g(A[i][j]-v);
        A[i][j] = T[j] + v;
    }

}

其中 f 和 g 是非线性函数。这是一个递归过滤器。我的第一次尝试（我是 OpenMP 的新手）是并行化外部循环并将 T 分配为维度#threads X M 的矩阵，其中#threads=omp_get_max_threads():

#pragma omp parallel for
for ( int i = 0; i < N; i++ )
{
    Let T1 point to the row of T indexed by the current thread (given by omp_get_thread_num())

    T1[0] = A[i][0];
    for ( int j = 1; j < M; j++ )
        T1[j] = f(A[i][j]-T1[j-1]) + A[i][j];

    float v = T1[M-1];
    for ( int j = M-2; j >=0; j-- )
    {
        v = g(A[i][j]-v);
        A[i][j] = T1[j] + v;
    }

}

这样每个线程都使用自己的T内存。我在我的 8 核 i7 CPU 上测试了它，加速大约是 5 倍，但在我的 4 核智能手机 CPU 上我得到了非常小的加速（比如 1.3 倍 - 1.5 倍）。我的问题是：

我预计 Android 上的加速约为 2 倍，但范围是 1.3-1.5 倍。这是一个合理的加速还是应该更多？
是否有更好的方法来并行化这种递归矩阵滤波器？

更新 1.

为了测试它，我使用了 MS Visual Studio，在 8 核 i7 机器上启用了 OpenMP，而在我的智能手机上，我使用 Android NDK 提供的工具链，使用 -fopen -O3 -funroll-loops 标志。我在 Win 上使用 QueryPerformanceCounter，在 Android 上使用以下代码：

///
double  CUtil::GetTimeMs()
{
    struct timespec res;
    clock_gettime(CLOCK_REALTIME, &res);
    return 1000.0 * res.tv_sec + (double) res.tv_nsec / 1e6;
}

更新 2. 我更新了 Android.

上的加速数字

Answer 1

我的感觉是您采用了正确的并行化方法。

但是，由于您的 T 数组似乎仅用作临时存储，因此我不会将其分配为二维数组，第一维是要使用的线程数，我只是将其分配在parallel 区域为私有。这应该不会有太大区别，但可能会简化在 NUMA 环境中确保数据局部性的工作，并避免任何潜在的错误共享。

代码如下所示：

#pragma omp parallel
{
    float *T = new float[M];
    #pragma omp for schedule( static )
    for ( int i = 0; i < N; i++ ) {
        float *AA = A[i]; // this "optimisation" is arguable and can be ignored
        T[0] = AA[0];
        for ( int j = 1; j < M; j++ ) {
            T[j] = f( AA[j] - T[j-1] ) + AA[j];
        }
        float v = T1[M-1];
        for ( int j = M-2; j >= 0; j-- ) {
            v = g( AA[j] - v );
            AA[j] = T[j] + v;
        }
    }
    delete[] T;
}

现在，它是否会对您的代码产生任何影响 performance-wise，我很怀疑。但是，我提请您注意使用 clock() 作为 OpenMP 代码的计时器（在全球范围内使用 multi-threaded）。关键是（在 POSIX 系统上至少 IINM）clock() return 当前线程的 CPU 时间 及其children。同样，IINM，在 Windows 上，相同的函数 return 仅调用线程的 CPU 时间。
因此，如果有任何机会，您的 PC 在 Windows 而您的手机 phone 在 Android，在前一个平台上，您只为一个线程打印 CPU，而后者打印所有线程的累计 CPU 时间...

这是一个非常具有推测性的想法，但无论如何我都不能鼓励你放弃 clock() 并使用 omp_get_wtime()，这 return 是经过的挂钟时间，这才是你真正想要得到的。

编辑:

阅读您的更新（出现在我开始撰写此答案和发布之间），看起来我是对的（对于 Windows 和 Android）。然而，我只是错了 clock()。，但是，在两个平台上使用像 omp_get_wtime() 这样的通用计时器仍然是个好主意。

尽管如此，我认为到目前为止我提出的任何建议都不能解释两台机器上看到的 speed-ups 之间的差异。我怀疑底线可能只是硬件特性。同样，这是非常推测性的（特别是考虑到我从未尝试运行智能 phone 上的任何东西），但这可能只是内存带宽、缓存大小和 CPU 在两台机器上的表现：

您在 PC 上获得的 speed-up（8 核约 5 倍）不错但并不完美。这意味着您已经在那里遇到了瓶颈，这可能是内存带宽或缓存大小。这意味着您的代码很可能对这些硬件参数敏感。
在 smartphone 上测得的 speed-up 与顺序代码相比几乎没有改进。好吧，我（也许天真地）期望 phone 的 CPU 上的缓存大小和内存带宽远小于 PC。即使只看 CPU 峰值性能和缓存大小 and/or 内存带宽之间的比率，我也希望 high-end PC CPU 比智能 phone CPU。如果是这种情况，考虑到 high-end PC CPU 已经被您的代码推到其可扩展性限制，phone 的 CPU 达到其可扩展性限制是很正常的限制甚至更早。

评估是否确实如此的一个好方法是使用两个平台的 roofline model 并计算算法的算术强度以将其绘制在图表上。这将使您对自己的表现有一个清晰的认识，以及您是否还有进一步改进的余地。

如何并行化这个递归算法

How to parallelize this recursive algorithm

parallel-processing

recursion

openmp