c++ - openmp并行性能

Question

我正在尝试使用 openmp 并行实现距离矩阵，在其中我计算每个点与所有其他点之间的距离，所以到目前为止我想到的最佳算法成本为 O(n^2) 和性能我的算法在 8 处理器机器上使用 10 个线程的 openmp 在运行时间方面并不比串行方法好，所以我想知道我在 openmp 方法上的实现是否有任何错误，因为这是我第一次使用 openmp，因此，如果我的方法有任何错误或任何更好的“更快”方法，请告诉我。以下是我的代码，其中“dat”是一个包含数据点的 vector 。

map <int, map< int, double> > dist;   //construct the distance matrix 

int c=count(dat.at(0).begin(),dat.at(0).end(),delm)+1;

#pragma omp parallel for shared (c,dist)

for(int p=0;p<dat.size();p++)
{

    for(int j=p+1;j<dat.size();j++)
    {
        double ecl=0;

        string line1=dat.at(p);
        string line2=dat.at(j);

        for (int i=0;i<c;i++)
        {

            double num1=atof(line1.substr(0,line1.find_first_of(delm)).c_str());

            line1=line1.substr(line1.find_first_of(delm)+1).c_str();

            double num2=atof(line2.substr(0,line2.find_first_of(delm)).c_str());

            line2=line2.substr(line2.find_first_of(delm)+1).c_str();

            ecl += (num1-num2)*(num1-num2);
        }

        ecl=sqrt(ecl);

#pragma omp critical
        {
            dist[p][j]=ecl;
            dist[j][p]=ecl;
        }
    }
}

Answer 1

#pragma omp critical 具有序列化循环的效果，因此摆脱它应该是您的首要目标。这应该是朝着正确方向迈出的一步:

ptrdiff_t const c = count(dat[0].begin(), dat[0].end(), delm) + 1;
vector<vector<double> > dist(dat.size(), vector<double>(dat.size()));

#pragma omp parallel for
for (size_t p = 0; p != dat.size(); ++p)
{
  for (size_t j = p + 1; j != dat.size(); ++j)
  {
    double ecl = 0.0;
    string line1 = dat[p];
    string line2 = dat[j];
    for (ptrdiff_t i = 0; i != c; ++i)
    {
      double const num1 = atof(line1.substr(0, line1.find_first_of(delm)).c_str());
      double const num2 = atof(line2.substr(0, line2.find_first_of(delm)).c_str());

      line1 = line1.substr(line1.find_first_of(delm) + 1);
      line2 = line2.substr(line2.find_first_of(delm) + 1);
      ecl += (num1 - num2) * (num1 - num2);
    }

    ecl = sqrt(ecl);
    dist[p][j] = ecl;
    dist[j][p] = ecl;
  }
}

还有一些其他明显的事情可以使整体速度更快，但修复并行化是最重要的事情。