Dijkstra算法OpenMP比單線程慢

我想使用OpenMP並行Dijkstra的算法，但串行版運行速度快40倍。我可能會錯過一個概念或做錯事。我是新來的並行和OpenMP。你能幫忙嗎？謝謝。Dijkstra算法OpenMP比單線程慢

long* prev; // array of pointers to preceding vertices 
long* dist; // array of distances from the source to each vertex 
long* visited; // visited vertices, 0 if not visited, 1 otherwise 
long** vSetDistance; // distance between i and j 

void dijkstraAlgorithm(
     long * prev, 
     long * dist, 
     long * visited, 
     long ** vSetDistance) 
    { 
    int i, j, min; 

    // Initialization: set every distance to INFINITY until we discover a path 
    for (i = 1; i <= numVertices; i++) 
     { 
     prev[i] = -1; 
     visited[i] = 0; 
     dist[i] = INFINITY; 
     } 

    // The distance from the source to the source is defined to be zero 
    dist[sourceVertex] = 0; 

     { 
     for (j = 1; j <= numVertices; j++) 
     { 
     min = -1; 

#pragma omp parallel default(none) private(i, j) \ 
    shared(min, visited, dist, prev, vSetDistance, numVertices) 

      { 
      /* This loop corresponds to sending out the explorers walking the paths, 
      * where the step of picking "the vertex, v, with the shortest path to s" 
      * corresponds to an explorer arriving at an unexplored vertex */ 

#pragma omp for 

      for (i = 1; i <= numVertices; i++) 
#pragma omp critical 
       { 
       if (!visited[i] && ((min == -1) || (dist[i] <= dist[min]))) 
        min = i; 
       } 

      visited[min] = 1; // visited = true 

      // relaxation 
#pragma omp for 
      for (i = 1; i <= numVertices; i++) 
       { 
       if (vSetDistance[min][i]) 
        { 
        if ((dist[min] + vSetDistance[min][i]) < dist[i]) 
        { 
        dist[i] = dist[min] + vSetDistance[min][i]; 
        prev[i] = min; 
        } 
        } 
       } 
      } 
     } 
     } 
    }

來源

2014-05-04 link_boy

請在詢問之前搜索網站。正如你所說你是新手，所以請事先通知你自己。一般來說，OpenMP和並行化有很多資源。可能的[OpenMP緩慢代碼如何可以並行化？]可能的重複（http://stackoverflow.com/questions/15318331/slower-code-with-openmp-how-it-can-be-parallelized） –

並行並不總是獲得更高性能的免費票據。我看到兩件事情可能導致經濟放緩。

臨界區可能花費大量時間處理同步。我不完全熟悉OpenMP如何實現這些部分，但我的第一個猜測是他們使用互斥鎖來鎖定對該部分的訪問。互斥鎖對於鎖定/解鎖並不是很便宜，而且該操作比您要執行的操作貴得多。另外，由於循環完全處於關鍵部分，除了其中一個線程外，其他所有線程都將等待臨界區中的線程完成。實質上，該循環仍將以串行方式完成，同時增加額外的開銷。
可能沒有足夠的頂點從並行化中受益。同樣，啓動線程不是免費的，開銷可能比獲得的時間要大得多。隨着頂點數量變小，這變得越來越明顯。

我的猜測是，第一個問題是大多數減速發生的地方。減輕這個問題的最簡單方法是簡單地以串行方式進行。其次，您可以嘗試讓每個線程僅在其自己的部分中找到最小值，然後在並行部分之後對它們進行串行比較。

來源

2014-05-05 06:53:58

偉大的建議。我跑在99.999999的頂點上。刪除關鍵字並使用「讓每個線程找到最小值」的建議後，我在大型數據上獲得了巨大的性能提升。謝謝！ –

Dijkstra算法OpenMP比單線程慢

回答

相關問題