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並行性能

回答

相關問題