Dijkstra parallèle

Question

J'utilise OpenMP pour réaliser une version parallèle de l'algorithme de Dijkstra. Mon code se compose de deux parties. La première partie est exécutée par un seul thread (master). Ce thread choisit de nouveaux nœuds dans la liste. La deuxième partie est exécutée par d'autres threads. Ces threads modifient les distances entre la source et les autres nœuds. Malheureusement, dans mon code, une erreur se produit car l'un des nombreux threads qui exécutent la deuxième partie "disparaît" soudainement. Il y a probablement un problème de synchronisation des données, mais je ne sais pas où. Je serais reconnaissant si quelqu'un pouvait me dire où est mon erreur. Voici le code :

map<int, int> C;
map<int, int> S;
map<int, int> D;
int init;
int nu;
int u;
int p = 3;//omp_get_num_threads();
int d;
int n = graph->getNodesNum();

#pragma omp parallel shared(n, C, d, S, init, nu, u, D, graph, p) num_threads(p)
{
    int myId = omp_get_thread_num();
    if (myId == 0)
    {
        init = 0;
        nu = 0;

        u = to;
        while (init < p - 1)
        {
        }

        while (u != 0)
        {
            S[u] = 1;
            while (nu < p - 1)
            {
            }
            u = 0;
            d = INFINITY;
            for (int i = 1; i <= p - 1; ++i)
            {
                int j = C[i];
                if ((j != 0) && (D[j] < d))
                {
                    d = D[j];
                    u = j;
                }
            }
            nu = 0; 
        }
    }
    else
    {
        for (int i=myId; i<=n; i += p-1)
        {
            D[i] = INFINITY;
            S[i] = 0;
        }

        D[u] = 0;

        ++init; 
        while (init < p-1)
        {
        }
        while (u != 0)
        {
            C[myId] = 0;
            int d = INFINITY;

            for (int i = myId; i<=n; i+=p-1)
            {
                if (S[i] == 0)
                {
                    if (i != u)
                    {
                        int cost = graph->getCostBetween(u, i);
                        if (cost != INFINITY)
                        {
                            D[i] = min(D[i], D[u] + cost);
                        }
                    }
                    if ((d > D[i])) 
                    {                           
                        d = D[i];
                        C[myId] = i;
                    }
                }
            }
            ++nu;
            while (nu != 0)
            {
            }   
        }
    }       
}

}

Answer 1

Je ne sais pas de quelles informations vous disposez, mais la parallélisation d'un algorithme irrégulier et hautement synchronisé avec de petites tâches est l'un des problèmes parallèles les plus difficiles à résoudre. Les équipes de recherche peuvent se consacrer à ces tâches et obtenir des gains de vitesse limités, voire nuls. Souvent, ces algorithmes ne fonctionnent que sur des architectures spécifiques conçues pour la parallélisation, et les frais généraux bizarres tels que les faux partages ont été éliminés en concevant les structures de données de manière appropriée.

Un tel algorithme nécessite beaucoup de temps et d'efforts pour établir des profils, les mesurer et les prendre en considération. Voir par exemple ce document.

ww2.cs.fsu.edu/~flin/ppq_report.pdf

Maintenant, pour en venir à votre question directe, puisque votre algorithme est hautement synchronisé et que les tâches sont petites, vous subissez l'effet secondaire des courses de données. Les supprimer de votre algorithme parallèle va être très délicat, et personne ici ne peut le faire à votre place.

La première chose à faire est donc d'examiner les outils qui peuvent vous aider à détecter les courses de données, tels que Valgrind et le vérificateur de threads d'Intel.