时间戳

首页 > 解决方案 > 如何解决多线程代码中for循环中的依赖关系？

c++ - 如何解决多线程代码中for循环中的依赖关系？

问题描述

我无法使用 OpenMP 解决 for 循环中的依赖关系，因此程序将执行得更快。我就是这样做的，而且它有效，但我需要一个更快的解决方案。有谁知道这样做，所以它会工作得更快？

        #pragma omp parallel for num_threads(tc) ordered schedule(dynamic, 1) private(i) shared(openSet, maxVal, current, fScores)
        for(i = 0;i < openSet.size();i++){
            if(fScores[openSet[i].x * dim + openSet[i].y] < maxVal){
                #pragma omp ordered
                maxVal = fScores[openSet[i].x * dim + openSet[i].y];
                current = openSet[i];
            }
        }

第二个 for 循环是这个：

    #pragma omp parallel for num_threads(tc) ordered schedule(dynamic, 1) private(i) shared(neighbours, openSet, gScores, fScores, tentative_gScore)
    for(i = 0;i < neighbours.size();i++){
        #pragma omp ordered
        tentative_gScore = gScores[current.x * dim + current.y] + 1;

        if(tentative_gScore < gScores[neighbours[i].x * dim + neighbours[i].y]){
            cameFrom[neighbours[i].x * dim + neighbours[i].y] = current;
            gScores[neighbours[i].x * dim + neighbours[i].y] = tentative_gScore;
            fScores[neighbours[i].x * dim + neighbours[i].y] = tentative_gScore + hScore(); //(p.x, p.y, xEnd, yEnd)
            if(contains(openSet, neighbours[i]) == false){
                openSet.push_back(neighbours[i]);
            }
        }
    }

编辑：我没有提到我什至在这里做什么。我正在实现 A* 算法，这段代码来自维基百科。另外，我想再添加 2 个变量，这样我就不会混淆任何人。

    PAIR current = {};
    int maxVal = INT32_MAX;

标签： c++multithreadingparallel-processingopenmp

解决方案

首先，您需要确保这是您的热点。然后我们使用适当的测试套件，以确保您真正获得性能。使用诸如“google_benchmark”之类的工具。确保您在发布模式下编译，否则您的测量结果将完全被破坏。

这就是说，我认为您正在寻找最大减少

 #pragma omp parallel for reduction(max : maxVal )
    for(i = 0;i < openSet.size();i++){
        if(fScores[openSet[i].x * dim + openSet[i].y] > maxVal){

            maxVal = fScores[openSet[i].x * dim + openSet[i].y];

        }
    }

“当前”接缝是多余的。我认为比较已经混淆了。

你能以线性方式访问“fScores”中的数据吗？使用 'openSet' 的间接寻址会导致很多缓存未命中。如果你能以某种方式摆脱这种间接性，你将在单线程和多线程场景中获得很高的加速。

在第二个循环中，“push_back”会破坏你的表现。我有一个类似的问题。对我来说这是非常有益的

  • 创建一个具有最大可能长度的向量
  • 用空值初始化它
  • 使用满足标准的 openmp 正确设置它。
  • 使用向量时检查空值。

推荐阅读