Parallel Dijkstra

Question

I use OpenMP to create a parallel version of Dijkstra's algorithm. My code has two parts. The first part is performed by only one thread (leading). This thread selects new nodes from the list. The second part is performed by other threads. These flows change the distance from the source to other nodes. Unfortunately, there is an error in my code because one of the many threads executing the second part suddenly “disappears”. There is probably a problem with data synchronization, but I do not know where. I would be grateful if someone would tell me where my mistake is. 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 parallelizing an irregular, strictly synchronized algorithm with small tasks is one of the most difficult parallel problems that may arise. Research teams can devote themselves to such tasks and get limited acceleration or nowhere with them. Often, such algorithms only work on certain architectures that are adapted for parallelization, and debilitating overhead, such as spurious exchanges, have been eliminated by properly designing data structures.

Such an algorithm requires a lot of time and effort for profiling, measuring and reviewing. See, for example, this article.

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

Now, to your direct question, since your algorithm is highly synchronized and tasks are small, you experience a side effect of data calculations. To remove them from your parallel algorithm, it will be very difficult, and no one will be able to do this for you.

So, your first point of call is to look at tools to help you detect data races such as Valgrind and Intel thread checking.