openmp并行性能

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

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; 
     } 
    } 
}

来源

2012-01-27 DOSMarter

你可以发表更多的行，使其成为一个运行的例子吗？ – 2012-01-27 20:46:15

你在双重嵌套循环中有一个'#pragma omp critical'，你想知道瓶颈在哪里？ o.O – ildjarn 2012-01-27 20:59:54

#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; 
    } 
}

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

来源

2012-01-27 21:16:04 ildjarn

我确实修复了关键部分。但是，当我在8核心机器上运行时，串行代码的性能仍然非常类似于并行代码。该代码与他在答案中建议的ildjarn相同。谢谢ildjarn :) – DOSMarter 2012-01-30 14:17:46

正如已经指出的那样，使用关键部分会减慢速度，因为一次只允许该部分中有一个线程。绝对不需要使用关键部分，因为每个线程都会将写入数据的互斥部分，读取未修改的数据显然不需要保护。

我对代码变慢的怀疑归咎于线程中不均匀的工作分配。默认情况下，我认为openmp在线程间平分迭代。作为一个例子，考虑当你有8个线程，8分：

-thread 0将获得7个距离计算

-thread 1将获得6个距离计算

...

- 线程7将得到0距离计算

即使有更多的迭代，类似的不平等仍然存在。如果您需要说服自己，请使用线程专用计数器来跟踪每个线程实际完成多少距离计算。

对于像parallel for这样的工作共享结构，您可以指定各种工作分配策略。在你的情况，可能是最好的与

#pragma omp for schedule(guided)

去当每个线程请求的一些迭代循环，它会得到剩余的循环数（不是已经给一个线程）的线程数划分。所以最初你会得到大块，以后你会得到更小的块。这是一种自动负载平衡的形式，请注意，在向线程动态分配迭代时会有一些（可能很小的）开销。

为了避免第一个线程获得大量不公平的工作，应该更改循环结构，以便较低的迭代计算较少，例如，改变内循环为

for (j=0; j<p-1; j++)

另一件要考虑的事情是，当处理大量内核时，内存可能成为瓶颈。你有8个处理器争夺大概2个或3个通道的DRAM（单个记忆棒在同一个通道上仍然在争夺带宽）。片上CPU缓存最好在所有处理器之间共享，因此您的缓存不会超过此程序的串行版本。

来源

2012-02-08 04:48:19 Jason

openmp并行性能

回答

相关问题