0

ここで heather.cs.ucdavis.edu/~matloff/OpenMP/Dijkstra.c からダウンロードした Dijkstra のアルゴリズムの openmp 実現を実行しようとしています。

たとえば、5 から 6 までの頂点をもう 1 つ追加して、0 番目からのパスが 2 つの頂点を通過するようにすると、0 番目と 6 番目の間の距離が無限であると言って、プログラムは正しい結果を返すことができません :^(理由？

#define LARGEINT 2<<30-1  // "infinity"
#define NV 6

// global variables, all shared by all threads by default

int ohd[NV][NV],  // 1-hop distances between vertices
mind[NV],  // min distances found so far
notdone[NV], // vertices not checked yet
nth,  // number of threads
chunk,  // number of vertices handled by each thread
md,  // current min over all threads
mv;  // vertex which achieves that min

void init(int ac, char **av)
{  int i,j;
for (i = 0; i < NV; i++)  
  for (j = 0; j < NV; j++)  {
     if (j == i) ohd[i][i] = 0;
     else ohd[i][j] = LARGEINT;
  }
ohd[0][1] = ohd[1][0] = 40;
ohd[0][2] = ohd[2][0] = 15;
ohd[1][2] = ohd[2][1] = 20;
ohd[1][3] = ohd[3][1] = 10;
ohd[1][4] = ohd[4][1] = 25;
ohd[2][3] = ohd[3][2] = 100;
ohd[1][5] = ohd[5][1] = 6;
ohd[4][5] = ohd[5][4] = 8;
for (i = 1; i < NV; i++)  {
  notdone[i] = 1;
  mind[i] = ohd[0][i];
}
}

// finds closest to 0 among notdone, among s through e
void findmymin(int s, int e, int *d, int *v)
{  int i;
  *d = LARGEINT; 
  for (i = s; i <= e; i++)
     if (notdone[i] && mind[i] < *d)  {
        *d = ohd[0][i];
        *v = i;
     }
}

// for each i in [s,e], ask whether a shorter path to i exists, through
// mv
void updateohd(int s, int e)
{  int i;
   for (i = s; i <= e; i++)
      if (mind[mv] + ohd[mv][i] < mind[i])  
     mind[i] = mind[mv] + ohd[mv][i];
}

void dowork()
{  
   #pragma omp parallel  // Note 1  
   {  int startv,endv,  // start, end vertices for this thread
      step,  // whole procedure goes NV steps
      mymd,  // min value found by this thread
      mymv,  // vertex which attains that value
      me = omp_get_thread_num();  // my thread number
      #pragma omp single   // Note 2
      {  nth = omp_get_num_threads();  chunk = NV/nth;  
     printf("there are %d threads\n",nth);  }
      // Note 3
      startv = me * chunk; 
      endv = startv + chunk - 1;
      for (step = 0; step < NV; step++)  {
     // find closest vertex to 0 among notdone; each thread finds
     // closest in its group, then we find overall closest
     #pragma omp single 
     {  md = LARGEINT; mv = 0;  }
     findmymin(startv,endv,&mymd,&mymv);
     // update overall min if mine is smaller
     #pragma omp critical  // Note 4
     {  if (mymd < md)  
          {  md = mymd; mv = mymv;  }
     }
     // mark new vertex as done 
     #pragma omp single 
     {  notdone[mv] = 0;  }
     // now update my section of ohd
     updateohd(startv,endv);
     #pragma omp barrier 
      }
   }
}

int main(int argc, char **argv)
{  int i;
   init(argc,argv);
   dowork();  
   // back to single thread now
   printf("minimum distances:\n");
   for (i = 1; i < NV; i++)
      printf("%d\n",mind[i]);
}
4

1 に答える 1

3

ここには 2 つの問題があります。

スレッドの数が値の数を均等に分割しない場合、この作業の分割は

  startv = me * chunk;
  endv = startv + chunk - 1;

は、最後の(NV - nth*(NV/nth))要素を元に戻します。これは、距離が のままであることを意味しLARGEINTます。これは、さまざまな方法で修正できます。今のところ最も簡単なのは、残りの作業をすべて最後のスレッドに渡すことです

  if (me == (nth-1)) endv = NV-1;

(これは必要以上の負荷の不均衡につながりますが、コードを機能させるための妥当な開始点です。)

もう1つの問題は、設定する前にバリアが除外されていることですnotdone[]

 #pragma omp barrier
 #pragma omp single 
 {  notdone[mv] = 0;  }

これにより、 が確実notdoneに更新され、全員が更新をupdateohd()完了した後にのみ開始されます。findmymin()mdmv

開始した元のコードにエラーを導入するのは非常に簡単であることに注意してください。使用されるグローバル変数により、推論が非常に困難になります。John Burkardt は、彼の Web サイト (こちら) で、これと同じアルゴリズムの改良版を公開しています。

于 2012-11-18T16:01:25.413 に答える