OMP分析的依赖性

Question

嗨，我是并行编程的新手，我正在努力解决依赖问题。我有以下函数，我希望并行，代码的目的是返回图形中的下一个节点，然后在我的程序中用于Dijkstra的算法。

long getNextNode(graph* G)
{
    long i;
    long minD;
    long nextNode;

    nextNode = -1;
    minD = INF;

    //Find unvisited node with lowest Distance to the intial node
    #pragma omp parallel for schedule(runtime)
    for(i = 0; i<G->N; i++){
        if( (G->visited[i] == NOT_VISITED) && (G->D[i] < minD) ){
                minD = G->D[i];
                nextNode = i;
        }
    }

    return nextNode;
}

变量看起来像这样：

#define INF INT_MAX
typedef struct {
    long N; //Number of nodes
    char** node; //Matrix of Nodes and connections

    int* D; //Result of Dijkstra Algorithm. Shortest path length for each node.
    char* visited; //Used to flag which nodes have been visted yet or not.
} graph;

我很难理解依赖在哪里？我按顺序运行它的结果与上面尝试的并行版本不同。有人可以告诉我是否有可能解决这个问题？

Answer 1

你有竞争条件。也就是说，两个线程可能会发生冲突并进行不正确的更新。

假设我们有两个线程（例如A和B），他们分别检查G->[iA]（值为10）和G->[iB]（值为20）。假设这些值都小于minD的值，其值为30。

所以，他们都希望同时更新minD和nextIndex。显然，线程A具有[最终]更好的值，但是没有什么可以阻止A设置minD/nextIndex然后B摧毁该值。

这是因为if测试和新值的集合不是原子的。否则，如果它们是原子的，A将设置共享值而B不会，因为它的if测试将失败[而不是更新]，因为它将保证看到由A更新的值

---

警告：我不是一个openmp大师，所以采取以下所有盐和一粒盐。

这应该工作，但可能不是非常有效：

long
getNextNode(graph * G)
{
    long i;
    long minD;
    long nextNode;

    nextNode = -1;
    minD = INF;

    // Find unvisited node with lowest Distance to the intial node
#pragma omp parallel for shared(minD,nextNode) schedule(runtime)
    for (i = 0; i < G->N; i++) {
        if (G->visited[i] != NOT_VISITED)
            continue;

#pragma omp atomic
        if (G->D[i] < minD) {
            minD = G->D[i];
            nextNode = i;
        }
    }

    return nextNode;
}

---

另一种方法是添加一个reduction子句，但我不确定是否适用，因为你有两个变量。例如，如果您不需要nextNode，要获得最小值，您可以：

long
getNextNode(graph * G)
{
    long i;
    long minD;

    minD = INF;

    // Find unvisited node with lowest Distance to the intial node
#pragma omp parallel for reduction(min:minD) schedule(runtime)
    for (i = 0; i < G->N; i++) {
        if (G->visited[i] != NOT_VISITED)
            continue;

        if (G->D[i] < minD)
            minD = G->D[i];
    }

    return minD;
}

---

另一种方法是让每个线程的循环自由运行私有变量（例如private(nextNode,minD)），但将最终的nextNode和minD值存储在全局数组中，由线程号索引：

struct res {
    long res_node;
    long res_min;
};

struct res thread_list[NUMTHREADS];

thread_list[my_thread_number].res_node = nextNode;
thread_list[my_thread_number].res_min = minD;

然后，在退出并行部分后，遍历主线程中的列表并选择具有最低res_min值的条目。

我不确定在openmp下执行此操作的确切方法，因此以上是伪代码，但有一些示例说明如何在Web上执行此操作。

---

但是，这让我觉得在O(n^2)时间运行。也就是说，getNextNode需要O(n)时间，但它[推测]被称为n时间（即）O(n*n)或O(n^2)。

假设你有8个核心，这减少到O(n^2)/8，仍然是O(n^2)

如果可能的话，最好在graph中创建一个排序列表（例如，将long *S添加到图形结构中）并根据visited/D对其进行预排序。

排序需要O(n*log2(n))时间。

然后，getNextNode可以按顺序遍历S并获得相同的效果。但是，时间变成O(n*log2(n)) + O(n)，减少到O(n*log2(n))

当然，这取决于您是否在调用getNextNode之间修改图表。

如果能够这样做，那么运行单线程可能就好了。