4
我正在使用OpenMP來製作Dijkstra算法的並行版本。我的代碼由兩部分組成。第一部分僅由一個線程（主）執行。這個線程從列表中選擇新的節點。第二部分由其他線程執行。這些線程改變了從源到其他節點的距離。不幸的是，在我的代碼中是錯誤的，因爲許多執行第二部分的線程中的一個突然「消失」了。數據同步可能存在問題，但我不知道在哪裏。如果有人能告訴我我的錯誤在哪裏，我將不勝感激。下面是代碼：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