從多個線程更新最大值

Question

有沒有辦法使用原子操作更新多個線程的最大值？

說明性實例：

std::vector<float> coord_max(128); 
#pragma omp parallel for 
for (int i = 0; i < limit; ++i) { 
    int j = get_coord(i); // can return any value in range [0,128) 
    float x = compute_value(j, i); 
    #pragma omp critical (coord_max_update) 
    coord_max[j] = std::max(coord_max[j], x); 
} 

在上述情況下，臨界段同步訪問整個矢量，而我們只需要訪問的每個值獨立地進行同步。

Answer 1

根據評論中的建議，我找到了一個不需要鎖定的解決方案，而是使用std :: atomic/boost :: atomic中的比較和交換功能。我僅限於C++ 03，所以我會在這種情況下使用boost :: atomic。

BOOST_STATIC_ASSERT(sizeof(int) == sizeof(float)); 
union FloatPun { float f; int i; }; 

std::vector< boost::atomic<int> > coord_max(128); 
#pragma omp parallel for 
for (int i = 0; i < limit; ++i) { 
    int j = get_coord(i); 
    FloatPun x, maxval; 
    x.f = compute_value(j, i); 

    maxval.i = coord_max[j].load(boost::memory_order_relaxed); 
    do { 
     if (maxval.f >= x.f) break; 
    } while (!coord_max[j].compare_exchange_weak(maxval.i, x.i, 
     boost::memory_order_relaxed)); 
} 

有一些樣板涉及浮點值ints，因爲它似乎原子浮動不鎖定。我並不是100％地使用關於內存的順序，但限制性最低的「寬鬆」級別似乎沒有問題，因爲不涉及非原子內存。

Answer 2

如何聲明長度爲128的std::vector<std::mutex>（或boost::mutex），然後使用j th元素創建鎖定對象？

我的意思是，是這樣的：

std::vector<float> coord_max(128); 
std::vector<std::mutex> coord_mutex(128); 
#pragma omp parallel for 
for (int i = 0; i < limit; ++i) { 
    int j = get_coord(i); // can return any value in range [0,128) 
    float x = compute_value(j, i); 
    std::scoped_lock lock(coord_mutex[j]); 
    coord_max[j] = std::max(coord_max[j], x);  
} 

或者，按Rahul Banerjee's suggestion #3：

std::vector<float> coord_max(128); 
const int parallelism = 16; 
std::vector<std::mutex> coord_mutex(parallelism); 
#pragma omp parallel for 
for (int i = 0; i < limit; ++i) { 
    int j = get_coord(i); // can return any value in range [0,128) 
    float x = compute_value(j, i); 
    std::scoped_lock lock(coord_mutex[j % parallelism]); 
    coord_max[j] = std::max(coord_max[j], x);  
} 

Answer 3

不知道有關語法，但是算法，你有三種選擇：

1. 鎖定整個矢量以保證原子訪問（這是您目前正在做的）。

2. 鎖定單個元素，以便每個元素都可以獨立於其他元素進行更新。優點：最大平行度;缺點：需要大量的鎖！

3. 之間的東西！在概念上，將您的矢量劃分爲16（或32/64/...）個「bank」，如下所示： bank0由矢量元素0,16,32,48,64，...， 組成矢量元素1 ，17，33，49，65，... bank2由矢量元素2，18，34，50，66，...， ... 現在，在訪問元素之前使用16個顯式鎖，具有高達16路並行性。要訪問元素n，獲取鎖定（n％16），完成訪問，然後釋放相同的鎖定。

Answer 4

我想補充我的兩分錢，開始更細粒度的優化，我會試試下面的辦法，消除了omp critical前需要：

std::vector<float> coord_max(128); 
float    fbuffer(0); 
#pragma omp parallel 
{ 
    std::vector<float> thread_local_buffer(128); 

    // Assume limit is a really big number 
    #pragma omp for  
    for (int ii = 0; ii < limit; ++ii) { 
    int jj = get_coord(ii); // can return any value in range [0,128) 
    float x = compute_value(jj,ii); 
    thread_local_buffer[jj] = std::max(thread_local_buffer[jj], x); 
    } 
    // At this point each thread has a partial local vector 
    // containing the maximum of the part of the problem 
    // it has explored 

    // Reduce the results 
    for(int ii = 0; ii < 128; ii++){ 
    // Find the max for position ii 
#pragma omp for schedule(static,1) reduction(max:fbuffer) 
    for(int jj = 0; jj < omp_get_thread_num(); jj++) { 
     fbuffer = thread_local_buffer[ii]; 
    } // Barrier implied here 
    // Write it in the vector at correct position 
#pragma omp single 
    { 
     coord_max[ii] = fbuffer; 
     fbuffer = 0; 
    } // Barrier implied here 

    } 
} 

注意，我沒有編譯代碼段，所以我可能在裏面留下了一些語法錯誤。無論如何，我希望我已經傳達了這個想法。