multithreading - 使用 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 Threads 案例与其他案例有如此大的不同？
我在具有 24 个线程和 96 GB 内存的 Google VM 机器上运行该算法。
谢谢大家。

Answer 1

Why the 16 Threads case differs so much from the others? I'm runningthe 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 takesapproximately the same time, while the dynamic would introduce toomuch 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 子句来进一步优化它。 ，这将消除一个隐式障碍。尽管如此，您需要确保这不会导致竞争条件。