使用 pthreads 在 C 中将顺序循环转换为并行循环

Question

我想对 n×d 维数组应用一个非常简单直接的计算。目标是使用 pthreads 将顺序计算转换为并行计算。我的问题是：拆分问题的最佳方法是什么？ 如何显着减少脚本的执行时间？我提供了 C 中的示例顺序代码和我已经尝试过的关于并行实现的一些想法。

double * calcDistance(double * X ,int n, int d)
{
    //calculate and return an array[n-1] of all the distances
    //from the last point
    double *distances = calloc(n,sizeof(double));
    for(int i=0 ; i<n-1; i++)
    {
        //distances[i]=0;
        for (int j=0; j< d; j++)
        {

            distances[i] += pow(X[(j+1)*n-1]-X[j*n+i], 2);

        }
        distances[i] = sqrt(distances[i]);


    }
    return distances;
}

我提供了一个 main()-caller 函数以使示例完整且可测试：

#include <stdio.h>
#include <stdlib.h>

#define N 10 //00000
#define D 2        

int main()
{

    srand(time(NULL));

    //allocate the proper space for X
    double *X = malloc(D*N*(sizeof(double)));

    //fill X with numbers in space (0,1)
    for(int i = 0 ; i<N ; i++)
    {
        for(int j=0; j<D; j++)
        {
            X[i+j*N] = (double) (rand()  / (RAND_MAX + 2.0));
        }

    }
    X = calcDistances(X, N, D);

    return 0;
}

我已经尝试通过使用强加于 mutex 的 global_index 和 local_index 异步利用 pthreads。通过使用 while() 循环，在每次迭代中将 local_index 分配给每个线程。 local_index 分配取决于当时的 global_index 值（两者都发生在 mutual exclusion 块中）。线程在 distances[local_index] 元素上执行计算。不幸的是，与上面引用的顺序执行相比，此实现导致程序运行速度慢得多，执行时间多了 10 倍或 20 倍。
另一个想法是预先确定和拆分数组（比如分成四个相等的部分）并将每个段的计算分配给给定的 pthread。不过，我不知道这是否是一个普遍有效的程序。

Answer 1

你的内部循环在整个数组 X 中跳跃，混合步幅随着外循环迭代。除非 n 和 d 非常小，否则 ^* 这可能会产生不良的缓存使用率——在串行代码中也是如此，但并行化会放大这种影响.至少X不是函数写的，提高了观感。此外，外循环迭代之间似乎没有任何数据依赖性，这很好。

what is the optimal way to split the problem?

可能最好的方法是在线程之间拆分外循环迭代。对于 T 个线程，让一个执行迭代 0 ... (N / T) - 1，让第二个执行 (N / T) ... (2 * N / T) - 1、etc..

我怎样才能显着减少脚本的执行时间？

I 要做的第一件事是使用简单的乘法而不是 pow 来计算平方。目前还不清楚您是否能从并行性中获益。

I have already tried utilizing pthreads asynchronously through the use of a global_index that is imposed to mutex and a local_index. [...]

如果您必须涉及互斥量、信号量或类似的同步对象，那么该任务可能是无望的。令人高兴的是（也许）似乎没有任何必要。对于这个问题，动态地将外循环迭代分配给线程是过度设计的。正如我已经描述的那样，将迭代静态分配给线程将消除对这种同步的需要，并且由于内部循环的成本看起来不会因不同的外部循环迭代而有很大差异，因此可能不会引入太多低效率方式。

Another idea is to predetermine and split the array (say to four equal parts) and assign the computation of each segment to a given pthread. I don't know if that's a common-efficient procedure though.

这听起来像我描述的那样。它是 OMP 提供的标准调度模型之一，也是解决许多问题最有效的模型之一，因为它本身不需要互斥体。然而，它对线程数和可用执行单元数之间的关系有些敏感。例如，如果您在一台四核机器上并行处理五个内核，那么一个内核将不得不等待运行，直到其他一个内核完成——最佳理论加速 60%。仅跨四个内核并行执行相同的计算可以更有效地利用计算资源，理论上的最佳加速比约为 75%。

^* 如果 n 和 d 非常小，请说任何与示例驱动程序，那么并行化产生的开销很有可能会克服并行执行带来的任何收益。

使用 pthreads 在 C 中将顺序循环转换为并行循环

Convert sequential loop into parallel in C using pthreads

c

parallel-processing

loops

pthreads