Cập nhật giá trị tối đa từ nhiều chủ đề

Question

Có cách nào để cập nhật tối đa từ nhiều luồng bằng cách sử dụng các phép toán nguyên tử không?

minh họa ví dụ:

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

Trong trường hợp trên, phần quan trọng đồng bộ hóa quyền truy cập vào toàn bộ vector, trong khi chúng ta chỉ cần để đồng bộ hóa truy cập vào mỗi trong những giá trị độc lập.

Answer 1

Theo một đề xuất trong nhận xét, tôi đã tìm thấy giải pháp không yêu cầu khóa và thay vào đó sử dụng chức năng so sánh và trao đổi được tìm thấy trong tiêu chuẩn :: atomic/boost :: atomic. Tôi bị giới hạn trong C++ 03 vì vậy tôi sẽ sử dụng boost :: atomic trong trường hợp này.

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

Có một số boilerplate tham gia vào việc đặt các giá trị float trong int, vì có vẻ như phao nguyên tử không khóa. Tôi không sử dụng 100% về thứ tự bộ nhớ, nhưng mức hạn chế ít nhất là 'thoải mái' có vẻ là OK, vì bộ nhớ không nguyên tử không liên quan.

Answer 2

Làm cách nào để khai báo, ví dụ: std::vector<std::mutex> (hoặc boost::mutex) có độ dài 128 và sau đó tạo đối tượng khóa sử dụng yếu tố thứ j?

Ý tôi là, một cái gì đó như:

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

Hoặc, theo 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

Không chắc chắn về cú pháp, nhưng thuật toán, bạn có ba lựa chọn:

1. Khóa toàn bộ vectơ để đảm bảo truy cập nguyên tử (đó là những gì bạn đang làm).

2. Khóa từng phần tử để mọi phần tử có thể được cập nhật độc lập với các phần tử khác. Ưu điểm: tối đa song song; Nhược điểm: rất nhiều ổ khóa cần thiết!

3. Thứ gì đó ở giữa! Suy nghĩ về phân vùng vector của bạn thành 16 (hoặc 32/64/...) "ngân hàng" như sau: bank0 bao gồm các phần tử vectơ 0, 16, 32, 48, 64, ... bank1 bao gồm các phần tử vectơ 1 , 17, 33, 49, 65, ... bank2 bao gồm các phần tử vectơ 2, 18, 34, 50, 66, ... ... Bây giờ, hãy sử dụng 16 khóa rõ ràng trước khi bạn truy cập phần tử và bạn có thể có tối đa 16 chiều song song. Để truy cập phần tử n, lấy khóa (n% 16), kết thúc truy cập, sau đó nhả khóa tương tự.

Answer 4

Chỉ cần thêm hai xu của tôi, trước khi bắt đầu tối ưu hóa hạt mịn hơn tôi sẽ thử các phương pháp sau đây mà loại bỏ sự cần thiết của 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 

    } 
} 

Chú ý rằng tôi đã không biên dịch đoạn mã , vì vậy tôi có thể đã để lại một số lỗi cú pháp bên trong. Dù sao thì tôi hy vọng tôi đã truyền đạt ý tưởng đó.