c - 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 test 和新值集不是原子。否则，如果它们是原子的，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)变量(例如 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最低的entry值(value)。

我不确定在 openmp 下执行此操作的确切方法, 所以上面是伪代码，但是在网络上有如何做到这一点的例子。

---

但是，这让我觉得是在 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 之间修改图表还是不是。

如果您能够做到这一点，运行单线程可能是可行的方法。