如何使用Open MP并行化A*算法？

Question

我在并行化A*算法时遇到困难。我已经尝试并行化单个for循环，但这并没有任何改进。事实上，串行实现仍然比这个更快。你能帮我改进一下或者给我一些建议吗？

while(openSet.size() > 0){
    PAIR current = {};
    int maxVal = INT32_MAX;

    int i;
    #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];
        }
    }

    if(current.x == xEnd && current.y == yEnd){
        elapsed = omp_get_wtime() - start;
        //printMat(gScores, dim);
        printPath("res.txt", mat, cameFrom, current, dim, tc);
        break;
    }

    int rm = check_remove(openSet, current, tc);
    openSet.erase(openSet.begin() + rm);

    vector<PAIR> neighbours;

    if(current.x - 1 >= 0 && mat[(current.x - 1) * dim + current.y] != '1'){
        neighbours.push_back(PAIR(current.x - 1, current.y));
    }
    if (current.y - 1 >= 0 && mat[current.x * dim + (current.y - 1)] != '1'){
        neighbours.push_back(PAIR(current.x, current.y - 1));
    }
    if (current.x + 1 < dim && mat[(current.x + 1) * dim + current.y] != '1'){
        neighbours.push_back(PAIR(current.x + 1, current.y));
    }
    if (current.y + 1 < dim && mat[current.x * dim + (current.y + 1)] != '1'){
        neighbours.push_back(PAIR(current.x, current.y + 1));
    }
    
    int tentative_gScore;
    #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++){
        tentative_gScore = gScores[current.x * dim + current.y] + 1;

        if(tentative_gScore < gScores[neighbours[i].x * dim + neighbours[i].y]){
            #pragma omp ordered
            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]);
            }
        }
    }
}

Answer 1

在第一个循环中，ordered子句导致了巨大的时间浪费，如果只需要maxVal，则可以通过使用reduction来避免这种浪费。但是，由于您还需要current，因此您必须手动执行缩减。因此，您应该为这些变量创建中间向量，即maxValVector和currentVector，而不是直接查找maxVal和current。然后，我建议每个线程查找maxValVector[omp_get_thread_num()]和currentVector[omp_get_thread_num()]。因此，您不需要使用ordered子句，并且每个线程都知道最大编号值。然后，通过对所涉及的线程数量进行串行微循环，从maxValVector和currentVector获取maxVal和current。这应该允许您对第一个循环进行更有效的并行化。

在第二个循环中，为了保证线程安全，变量tentative_gScore应该是私有的。此外，我也不认为这里需要ordered子句。不确定openSet.push_back(neighbours[i]);是怎么回事，但如果可能的话，这一行可能应该由atomic或critical子句来保护。