Зависимость в анализе OMP - PullRequest
Новая
       10

Зависимость в анализе OMP

0 голосов
/ 18 октября 2018

Привет, я новичок в параллельном программировании, и я борюсь с проблемой зависимости.У меня есть следующая функция, которую я хотел бы сделать параллельной, цель кода - вернуть следующий узел в графе, который затем будет использоваться для алгоритма Дейкстры в моей программе.

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;

Я изо всех сил пытаюсь понять, где находится зависимость?Мои результаты последовательного запуска отличаются от моих попыток параллельной версии выше.Может ли кто-нибудь показать мне, если это возможно, способ исправить это?

1 Ответ

0 голосов
/ 18 октября 2018

У вас есть состояние гонки.То есть два потока могут столкнуться и выполнить некорректное обновление.

Предположим, у нас было два потока (например, A и B), и они проверяют G->[iA] (со значением 10) и G->[iB] (со значением20) соответственно.Предположим, что эти значения оба меньше значения minD, которое имеет значение 30.

Итак, они оба хотят обновить minD и nextIndex одновременно.Очевидно, что поток A имеет [в конечном итоге] лучшее значение, но ничто не мешает A установить minD/nextIndex и , а затем B уничтожить это значение.

Это потому, что iftest и набор новых значений не atomic .В противном случае, если бы они были атомарными, 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, поэтому приведенный выше псевдокод, но есть примерыкак это сделать в Интернете.

Но, мне кажется, что это работает во время 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 или нет.

Если вы способны сделать это, возможно, стоит запустить однопоточный.

...