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比单线程慢

回答

相关问题