使用 OpenMP 加速和调度

Question

我正在将 OpenMP 用于 kNN 项目。两个并行化的 for 循环是：

#pragma omp parallel for
 for(int ii=0;ii<sizeTest;ii++){
    for(int t = 0 ; t<sizeTraining ; t++){
        distance[ii][t]=EuclideanDistance(testSet[ii],trainingSet[t]);
    }

和

#pragma omp parallel for
for(int ii=0;ii<sizeTest;ii++){          
   classifyPointFromDistance(trainingSet, &testSet[ii], distance[ii],k,sizeTraining);
}

我尝试了不同的调度组合，结果如下：

连续剧：1020 秒

静态（默认块大小）- 4 个线程 = 256.28 秒

动态（默认块大小 = 1）- 4 个线程 = 256.27 秒

我预计静态会是最好的，因为迭代大约需要相同的时间，而动态会引入太多开销。这似乎没有发生，我不明白为什么。此外，在静态执行中，除了 16 个线程的情况外，加速似乎是线性的：

连续剧：1020 秒

2 个线程：511,35 秒

4 个线程：256.28 秒

8 个线程：128,66 秒

16 个线程：90.98 秒

24 个线程：61.4 秒

为什么 16 线程案例与其他案例有如此大的不同？我是运行具有 24 个线程和 96 GB 内存的 Google VM 机器上的算法。感谢大家。

Answer 1

Why the 16 Threads case differs so much from the others? I'm running the algorithm on a Google VM machine with 24 Threads and 96 GB of ram.

正如您在评论中提到的：

It's a Intel Xeon CPU @2.30 GHz, 12 physical core

这就是当您移动到 16 线程时（几乎）停止线性扩展的原因，因为您不再只使用物理内核，还使用逻辑内核（即超线程）。

I expected that static would be the best since the iterations takes approximately the same time, while the dynamic would introduce too much overhead.

动态分配的大部分开销来自线程为获取要使用的新迭代而执行的锁定步骤。在我看来，没有太多的线程锁定争用，即使有，也可以通过动态调度程序实现的更好的负载平衡来补偿。之前看过这个一模一样的图案，没有错。

另外请注意，您可以将代码转换为：

#pragma omp parallel
{
    #pragma omp for
    for(int ii=0; ii<sizeTest; ii++)
        for(int t = 0 ; t<sizeTraining ; t++)
            distance[ii][t]=EuclideanDistance(testSet[ii],trainingSet[t]);
      

    #pragma omp for nowait
    for(int ii=0; ii<sizeTest; ii++){          
        classifyPointFromDistance(trainingSet, &testSet[ii], distance[ii],k,sizeTraining);
}

避免有两个平行区域。此外，根据您的代码，您可以通过向两个 #pragma omp for 添加一个 nowait 子句来进一步优化它，这将删除一个 implicit 障碍。尽管如此，您需要确保这不会导致竞争条件。

使用 OpenMP 加速和调度

Speed up and scheduling with OpenMP

parallel-processing

performance

multithreading

openmp

knn