4
Я использую OpenMP для параллельной версии алгоритма Дейкстры. Мой код состоит из двух частей. Первая часть выполняется только одним потоком (ведущим). Этот поток выбирает новые узлы из списка. Вторая часть выполняется другими потоками. Эти потоки меняют расстояния от источника к другим узлам. К сожалению, в моем коде есть ошибка, потому что один из многих потоков, выполняющих вторую часть, внезапно «исчезает». Вероятно, есть проблема с синхронизацией данных, но я не знаю, где. Буду признателен, если кто-нибудь скажет мне, где моя ошибка. Вот код:Parallel Dijkstra
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)
{
}
}
}
}
}
это звучит как ужасный способ распараллеливать по существу последовательный алгоритм. Зачем ты это делаешь? стоимость передачи вершины в поток должна быть приблизительно равна стоимости обновления затрат. – akappa
Я должен подготовить параллельную версию, чтобы показать, что Dijkstra может быть быстрее, когда мы используем больше ядер. Я знаю, что Dijkstra трудно распараллелить и обычно ускорение ниже 1. Однако я нашел некоторую информацию о том, что существует способ реализовать этот алгоритм с ускорением 1,2-1,4. Мой код представлен таким образом, поэтому в этот момент я хочу обнаружить ошибку. – mchrobok
«Ускорение» реализации зависит от количества используемых параллельных процессоров, поэтому я не понимаю, что означают эти цифры. Вероятно, ускорение зависит от «плотности» вашего графика и от того, сколько времени вы тратите на проходящие вершины. Это очень тонкий подход **, поэтому вам нужна чудесно настроенная реализация для достижения версии, которая значительно быстрее (если быстрее вообще) w.r.t. последовательная реализация. Что касается вашей реализации, я не понимаю, где ваш основной поток отправляет вершины для расслабления в другие потоки. – akappa