使用 OpenMP 以 C 语言并行化旅行商问题代码

Question

我有一个 C 代码，可以使用贪心算法解决旅行商问题。然而，当前的实现是顺序的，我想使用 OpenMP 对其进行并行化以获得更好的性能。

这是现有的代码：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

#define N 5000
#define LARGE (2 * pow(N * 10, 2))

int X[N];
int Y[N];
float distance[N][N + 1];

int main(int na, char * arg[]) {
  assert(na == 2);

  printf("Dimension %s\n", arg[1]);
  int nn = atoi(arg[1]);
  assert(nn <= N);

  for (int i = 0; i < nn; i++)
    X[i] = rand() % (nn * 10);
  for (int i = 0; i < nn; i++)
    Y[i] = rand() % (nn * 10);

  for (int i = 0; i < nn; i++)
    distance[i][i] = 0;

  for (int i = 0; i < nn; i++)
    for (int j = i + 1; j < nn; j++)
      distance[i][j] = distance[j][i] = sqrt(pow(X[i] - X[j], 2) + pow(Y[i] - Y[j], 2));

  float best = LARGE;
  int good[nn];
  for (int first = 0; first < nn; first++) {
    float dist = 0;
    int path[nn];

    for (int i = 0; i < nn; i++)
      path[i] = -1;

    path[first] = 0;
    int current = first;

    for (int i = 1; i < nn; i++) {
      float dmin = LARGE;
      int index = 0;

      for (int j = 0; j < nn; j++) {
        if (path[j] == -1 && current != j && distance[current][j] < dmin) {
          dmin = distance[current][j];
          index = j;
        }
      }

      current = index;
      path[current] = i;
      dist += dmin;

      if (dist >= best) {
        dist = 0;
        break;
      }
    }

    if (dist) {
      float dmin = distance[current][first];
      dist += dmin;

      if (dist < best) {
        for (int i = 0; i < nn; i++)
          good[path[i]] = i;
        best = dist;
      }

      distance[first][nn] = dist;
    }
  }

  printf("Solution :\n");
  for (int i = 0; i < nn; i++)
    printf("%d\n", good[i]);
  printf("Distance %g == %g\n", best, distance[good[0]][nn]);

  exit(0);
}

我正在寻找有关如何使用 OpenMP 有效并行化此代码以实现最佳加速的指导。代码中是否有更适合并行化的特定部分？我应该考虑使用哪些 OpenMP 构造，是否有我应该注意的潜在陷阱？

任何有关如何并行化此代码的见解、代码片段或建议将不胜感激。谢谢！

Answer 1

如果您的目标是使用 OpenMP 并行化代码并且您不想更改算法，那么您必须使用用户定义的缩减或手动缩减。下面，我提供了一个使用手动缩减的示例来响应您在评论中的请求。

 // these are the critical variables you have to take care
 float best = LARGE;
 int good[nn];
  
  #pragma omp parallel
  {  
      // create private variables for each thread
      float private_best = LARGE;
      int private_good[nn];
      
      #pragma omp for
      for (int first = 0; first < nn; first++) {
        // use the above defined private variables inside the for loop
        // best ---> private_best
        // good ---> private_good
         .....
         .....
      }
      // Find the minimum of 'private_best' and copy it to 'best' and 
      // also copy the 'private_good' array back to 'good' array 
      #pragma omp critical    
      if(private_best < best){
          best = private_best;
          for (int i = 0; i < nn; i++)
              good[i] = private_good[i];          
      }
  }