平行與OMP stucks

我有下面的代碼的問題：平行與OMP stucks

int *chosen_pts = new int[k]; 
std::pair<float, int> *dist2 = new std::pair<float, int>[x.n]; 
// initialize dist2 
for (int i = 0; i < x.n; ++i) { 
    dist2[i].first = std::numeric_limits<float>::max(); 
    dist2[i].second = i; 
} 

// choose the first point randomly 
int ndx = 1; 
chosen_pts[ndx - 1] = rand() % x.n; 
double begin, end; 
double elapsed_secs; 
while (ndx < k) { 
    float sum_distribution = 0.0; 
    // look for the point that is furthest from any center 
    begin = omp_get_wtime(); 
    #pragma omp parallel for reduction(+:sum_distribution) 
    for (int i = 0; i < x.n; ++i) { 

     int example = dist2[i].second; 
     float d2 = 0.0, diff; 
     for (int j = 0; j < x.d; ++j) { 
      diff = x(example,j) - x(chosen_pts[ndx - 1],j); 
      d2 += diff * diff; 
     } 
     if (d2 < dist2[i].first) { 
      dist2[i].first = d2; 
     } 

     sum_distribution += dist2[i].first; 

    } 

    end = omp_get_wtime() - begin; 

    std::cout << "center assigning -- " 
      << ndx << " of " << k << " = " 
      << (float)ndx/k * 100 
      << "% is done. Elasped time: "<< (float)end <<"\n";   

    /**/ 
    bool unique = true; 

    do { 
     // choose a random interval according to the new distribution 
     float r = sum_distribution * (float)rand()/(float)RAND_MAX; 
     float sum_cdf = dist2[0].first; 
     int cdf_ndx = 0; 
     while (sum_cdf < r) { 
      sum_cdf += dist2[++cdf_ndx].first; 
     } 
     chosen_pts[ndx] = cdf_ndx; 

     for (int i = 0; i < ndx; ++i) { 
      unique = unique && (chosen_pts[ndx] != chosen_pts[i]); 
     } 
    } while (! unique); 


    ++ndx; 
}

正如你可以看到我使用OMP for循環使並行。它工作正常，我可以實現顯着的加速。但是，如果我增加x.n價值超過2000萬的功能停止工作8-10循環後：

它doestn產生任何輸出（STD ::法院）
只有一個核心工作
沒有錯誤，無論如何

如果我註釋掉而循環，它再次按預期工作。所有內核都很忙，每次迭代後都會有輸出，我可以根據需要增加超過1億的k.n。

來源

2015-01-05 user1930254

這不是OpenMP並行卡，它顯然是在您的串行do-while循環中。

我看到的一個特殊問題是在訪問dist2的內部while循環中沒有陣列邊界檢查。理論上說，不應該出現邊界外訪問;但實際上它可能 - 看下面的原因。所以首先我會改寫cdf_ndx計算，以保證循環結束時，所有的元素都檢查：

float sum_cdf = 0; 
    int cdf_ndx = 0; 
    while (sum_cdf < r && cdf_ndx < x.n) { 
     sum_cdf += dist2[cdf_ndx].first; 
     ++cdf_ndx; 
    }

現在，怎麼可能會發生sum_cdf沒有達到r？這是由於浮點運算的細節和sum_distribution並行計算的事實，而sum_cdf是連續計算的。問題是一個元素對總和的貢獻可能低於浮點數的精度;換句話說，當你將兩個相差大於8個數量級的浮動值相加時，較小的值不會影響總和。

因此，在某點之後有20M浮點數可能會發生下一個要添加的值，與累積的sum_cdf相比非常小，因此添加此值不會改變它！另一方面，sum_distribution基本上被計算爲幾個獨立的部分和（每個線程一個），然後組合在一起。因此它更準確，並且可能比sum_cdf所能達到的要大。

一個解決方案可以計算sum_cdf的部分，有兩個嵌套循環。例如：

float sum_cdf = 0; 
    int cdf_ndx = 0; 
    while (sum_cdf < r && cdf_ndx < x.n) { 
     float block_sum = 0; 
     int block_end = min(cdf_ndx+10000, x.n); // 10000 is arbitrary selected block size 
     for (int i=cdf_ndx; i<block_end; ++i) { 
      block_sum += dist2[i].first; 
      if(sum_cdf+block_sum >=r) { 
       block_end = i; // adjust to correctly compute cdf_ndx 
       break; 
      } 
     } 
     sum_cdf += block_sum; 
     cdf_ndx = block_end; 
    }

而且你需要檢查cdf_ndx < x.n環後，以其他方式與新的隨機時間間隔重複。

來源

2015-01-06 05:36:51

謝謝！我本人從未想過自己。浮點運算的問題是未來需要注意的問題。 – user1930254

平行與OMP stucks

回答

相關問題