Parallel Dijkstra

Question

I'm using OpenMP to make parallel version of Dijkstra algorithm. My code consists of two parts. First part is execute only by one thread (master). This thread chooses new nodes from list. Second part is execute by other threads. These threads change distances from source to other nodes. Unfortunatelly in my code is error because one of many threads which execute second part suddenly "disappear". Probably there is problem with data synchronization, but I don't know where. I would be grateful if someone could tell me where is my mistake. Here is the 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

I don't know what information you have, but parallelising an irregular, highly synchronized algorithm with small tasks is amongst the toughest parallel problems one can have. Research teams can dedicate themselves to such tasks and get limited speedups, or nowhere with it. Often such algorithms only work on specific architectures that are tailored for the parallelisation, and quirky overheads such as false sharing have been eliminated by designing the data structures appropriately.

An algorithm such as this needs a lot of time and effort to profile, measure, and consideration. See for example this paper.

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

Now, onto your direct question, since your algorithm is highly synchronized and tasks are small you are experiencing the side effect of data races. To remove these from your parallel algorithm is going to be very tricky, and no-one here can do it for you.

So your first point of call is to look at tools which can help you detect data races such as Valgrind and the Intel thread checker.