Làm thế nào để tôi song song vòng lặp for thông qua danh sách C++ std :: using OpenMP?

Question

Tôi muốn lặp qua tất cả các phần tử trong danh sách std :: theo cách song song bằng cách sử dụng OpenMP. Vòng lặp sẽ có thể thay đổi các phần tử của danh sách. Có một giải pháp đơn giản cho điều này? Dường như OpenMP 3.0 hỗ trợ song song cho các vòng lặp khi trình lặp là một Bộ lặp truy cập ngẫu nhiên, nhưng không khác. Trong mọi trường hợp, tôi muốn sử dụng OpenMP 2.0 vì tôi không có toàn quyền kiểm soát những trình biên dịch nào có sẵn cho tôi.

Nếu container của tôi là một vector, tôi có thể sử dụng:

#pragma omp parallel for 
for (auto it = v.begin(); it != v.end(); ++it) { 
    it->process(); 
} 

Tôi hiểu rằng tôi có thể sao chép danh sách vào một vector, thực hiện vòng lặp, sau đó sao chép tất cả mọi thứ trở lại. Tuy nhiên, tôi muốn tránh sự phức tạp và chi phí này nếu có thể.

Answer 1

Nếu bạn quyết định sử dụng Openmp 3.0, bạn có thể sử dụng tính năng task:

#pragma omp parallel 
#pragma omp single 
{ 
    for(auto it = l.begin(); it != l.end(); ++it) 
    #pragma omp task firstprivate(it) 
     it->process(); 
    #pragma omp taskwait 
} 

này sẽ thực hiện vòng lặp trong một thread, nhưng ủy nhiệm việc xử lý các yếu tố cho người khác.

Nếu không có OpenMP 3.0 cách dễ nhất là viết tất cả các con trỏ đến các phần tử trong danh sách (hoặc vòng lặp trong vec-tơ và lặp lại trên vectơ đó. Bằng cách này bạn sẽ không phải sao chép bất kỳ thứ gì và tránh chi phí sao chép các phần tử bản thân, vì vậy nó không cần phải nhiều overhead:

std::vector<my_element*> elements; //my_element is whatever is in list 
for(auto it = list.begin(); it != list.end(); ++it) 
    elements.push_back(&(*it)); 

#pragma omp parallel shared(chunks) 
{ 
    #pragma omp for 
    for(size_t i = 0; i < elements.size(); ++i) // or use iterators in newer OpenMP 
     elements[i]->process(); 
} 

Nếu bạn muốn tránh sao chép ngay cả những gợi ý, bạn luôn có thể tạo song song cho vòng lặp bằng tay bạn có thể có đề truy cập vào các yếu tố xen kẽ của. danh sách (như được đề xuất bởi KennyTM) hoặc chia phạm vi trong các bộ phận gần như tương đương nhau trước khi lặp lại và lặp qua những phần đó. stnodes hiện đang được xử lý bởi các luồng khác (ngay cả khi chỉ có con trỏ tiếp theo), điều này có thể dẫn đến chia sẻ sai. Đây sẽ trông gần như thế này:

#pragma omp parallel 
{ 
    int thread_count = omp_get_num_threads(); 
    int thread_num = omp_get_thread_num(); 
    size_t chunk_size= list.size()/thread_count; 
    auto begin = list.begin(); 
    std::advance(begin, thread_num * chunk_size); 
    auto end = begin; 
    if(thread_num = thread_count - 1) // last thread iterates the remaining sequence 
    end = list.end(); 
    else 
    std::advance(end, chunk_size); 
    #pragma omp barrier 
    for(auto it = begin; it != end; ++it) 
    it->process(); 
} 

Rào cản không được nghiêm chỉnh cần thiết, tuy nhiên nếu process đột biến các yếu tố xử lý (có nghĩa là nó không phải là một phương pháp const), có thể có một số loại chia sẻ sai mà không có nó, nếu các luồng lặp qua chuỗi đã bị biến đổi. Bằng cách này sẽ lặp lại 3 * n lần so với chuỗi (trong đó n là số lượng chủ đề), do đó, tỷ lệ có thể ít hơn thì tối ưu cho một số lượng lớn các luồng.

Để giảm chi phí, bạn có thể đặt thế hệ phạm vi bên ngoài #pragma omp parallel, tuy nhiên bạn sẽ cần phải biết có bao nhiêu luồng sẽ tạo thành phần song song. Vì vậy, bạn có thể phải tự thiết lập các num_threads, hoặc sử dụng omp_get_max_threads() và xử lý các trường hợp số lượng các chủ đề tạo ra là ít hơn omp_get_max_threads() (mà chỉ là một ràng buộc trên). Cách cuối cùng có thể được xử lý bởi có thể gán mỗi thread severa khối trong trường hợp đó (sử dụng #pragma omp for nên làm điều đó):

int max_threads = omp_get_max_threads(); 
std::vector<std::pair<std::list<...>::iterator, std::list<...>::iterator> > chunks; 
chunks.reserve(max_threads); 
size_t chunk_size= list.size()/max_threads; 
auto cur_iter = list.begin(); 
for(int i = 0; i < max_threads - 1; ++i) 
{ 
    auto last_iter = cur_iter; 
    std::advance(cur_iter, chunk_size); 
    chunks.push_back(std::make_pair(last_iter, cur_iter); 
} 
chunks.push_back(cur_iter, list.end(); 

#pragma omp parallel shared(chunks) 
{ 
    #pragma omp for 
    for(int i = 0; i < max_threads; ++i) 
    for(auto it = chunks[i].first; it != chunks[i].second; ++it) 
     it->process(); 
} 

này sẽ chỉ mất ba lần lặp trên list (hai, nếu bạn có thể nhận được kích thước của danh sách mà không cần lặp lại).Tôi nghĩ đó là điều tốt nhất bạn có thể làm cho các trình vòng lặp truy cập không ngẫu nhiên mà không cần sử dụng tasks hoặc lặp qua một số cơ sở hạ tầng ngoài (như một vectơ của con trỏ).

Answer 2

Tôi nghi ngờ điều đó là có thể vì bạn không thể chỉ nhảy vào giữa danh sách mà không đi qua danh sách. Danh sách không được lưu trữ trong bộ nhớ tiếp giáp và std :: danh sách vòng lặp không phải là truy cập ngẫu nhiên. Chúng chỉ là hai chiều.

Answer 3

http://openmp.org/forum/viewtopic.php?f=3&t=51

#pragma omp parallel 
{ 
    for(it= list1.begin(); it!= list1.end(); it++) 
    { 
     #pragma omp single nowait 
     { 
     it->compute(); 
     } 
    } // end for 
} // end ompparallel 

này có thể được hiểu như trải ra như:

{ 
    it = listl.begin 
    #pragma omp single nowait 
    { 
    it->compute(); 
    } 
    it++; 
    #pragma omp single nowait 
    { 
    it->compute(); 
    } 
    it++; 
... 
} 

Cho một mã như thế này:

int main()                  
{                    
     std::vector<int> l(4,0);             
     #pragma omp parallel for               
     for(int i=0; i<l.size(); ++i){           
       printf("th %d = %d \n",omp_get_thread_num(),l[i]=i);    
     }                  
     printf("\n");               
     #pragma omp parallel                
     {                  
       for (auto i = l.begin(); i != l.end(); ++i) {     
       #pragma omp single nowait              
       {              
         printf("th %d = %d \n",omp_get_thread_num(),*i); 
       }              
      }                
     }                  
     return 0;                
} 

OMP_NUM_THREADS xuất khẩu = 4, sản lượng như sau (lưu ý phần thứ hai, số luồng công việc có thể lặp lại):

th 2 = 2 
th 1 = 1 
th 0 = 0 
th 3 = 3 

th 2 = 0 
th 1 = 1 
th 2 = 2 
th 3 = 3 

Answer 4

Nếu không sử dụng OpenMP 3,0 bạn có tùy chọn của việc có tất cả các chủ đề iterating trên danh sách:

std::list<T>::iterator it; 
#pragma omp parallel private(it) 
{ 
    for(it = list1.begin(); it!= list1.end(); it++) 
    { 
     #pragma omp single nowait 
     { 
     it->compute(); 
     } 
    } 
} 

Trong trường hợp này mỗi thread có bản sao của nó tự có của iterator (tin) nhưng chỉ một sợi đơn sẽ truy cập vào một phần tử cụ thể (đơn) trong khi các chủ đề khác sẽ chuyển tiếp tới các mục tiếp theo (nowait)

Hoặc bạn có thể lặp một lần để xây dựng một vector của con trỏ được sau đó phân phối giữa các chủ đề:

std::vector< T*> items; 

items.reserve(list.size()); 
//put the pointers in the vector 
std::transform(list.begin(), list.end(), std::back_inserter(items), 
       [](T& n){ return &n; } 
); 

#pragma omp parallel for 
for (int i = 0; i < items.size(); i++) 
{ 
    items[i]->compute(); 
} 

Tùy thuộc vào trường hợp cụ thể của bạn một này hay cách khác có thể nhanh hơn. Thử nghiệm cái nào phù hợp với bạn tốt hơn là dễ dàng.

Answer 5

Đây là giải pháp cho phép chèn/xóa các phần tử mới của danh sách song song.

Để có danh sách với các yếu tố N, trước tiên chúng tôi cắt danh sách thành nthreads liệt kê với các thành phần khoảng N/nthreads. Trong một khu vực song song này có thể được thực hiện như thế này

int ithread = omp_get_thread_num(); 
int nthreads = omp_get_num_threads(); 
int t0 = (ithread+0)*N/nthreads; 
int t1 = (ithread+1)*N/nthreads; 

std::list<int> l2; 
#pragma omp for ordered schedule(static) 
for(int i=0; i<nthreads; i++) { 
    #pragma omp ordered 
    { 
     auto it0 = l.begin(), it1 = it0; 
     std::advance(it1, t1-t0);  
     l2.splice(l2.begin(), l2, it0, it1); 
    } 
} 

đâu l2 là danh sách cắt cho mỗi thread.

Sau đó, chúng tôi có thể hành động trên từng danh sách song song. Ví dụ chúng ta có thể chèn -1 mỗi vị trí đầu tiên trong danh sách như thế này

auto it = l2.begin(); 
for(int i=(t0+4)/5; i<(t1+4)/5; i++) { 
    std::advance(it, 5*i-t0); 
    l2.insert(it, -1); 
} 

Cuối cùng, sau khi chúng tôi đang làm hoạt động trên danh sách song song chúng ta ghép các danh sách cho mỗi thread trở lại một danh sách theo thứ tự như thế này:

#pragma omp for ordered schedule(static) 
for(int i=0; i<nthreads; i++) { 
    #pragma omp ordered 
    l.splice(l.end(), l, l2.begin(), l2.end()); 
} 

Thuật toán cơ bản.

1. Chuyển tiếp nhanh qua danh sách cắt danh sách liên tiếp.
2. Hành động trên danh sách cắt song song thêm, sửa đổi hoặc xóa các phần tử.
3. Ghép các danh sách cắt được sửa đổi lại với nhau theo thứ tự.

---

Dưới đây là một ví dụ làm việc

#include <algorithm> 
#include <iostream> 
#include <list> 
#include <omp.h> 

int main(void) { 
    std::list<int> l; 
    for(int i=0; i<22; i++) { 
    l.push_back(i); 
    } 
    for (auto it = l.begin(); it != l.end(); ++it) { 
    std::cout << *it << " "; 
    } std::cout << std::endl; 

    int N = l.size(); 
    #pragma omp parallel 
    { 
    int ithread = omp_get_thread_num(); 
    int nthreads = omp_get_num_threads(); 
    int t0 = (ithread+0)*N/nthreads; 
    int t1 = (ithread+1)*N/nthreads; 

    //cut list into nthreads lists with size=N/nthreads 
    std::list<int> l2; 
    #pragma omp for ordered schedule(static) 
    for(int i=0; i<nthreads; i++) { 
     #pragma omp ordered 
     { 
    auto it0 = l.begin(), it1 = it0; 
    std::advance(it1, t1-t0);  
    l2.splice(l2.begin(), l2, it0, it1); 
     } 
    } 
    //insert -1 every 5th postion 
    auto it = l2.begin(); 
    for(int i=(t0+4)/5; i<(t1+4)/5; i++) { 
     std::advance(it, 5*i-t0); 
     l2.insert(it, -1); 
    } 

    //splice lists in order back together. 
    #pragma omp for ordered schedule(static) 
    for(int i=0; i<nthreads; i++) { 
     #pragma omp ordered 
     l.splice(l.end(), l, l2.begin(), l2.end()); 
    } 
    } 

    for (auto it = l.begin(); it != l.end(); ++it) { 
    std::cout << *it << " "; 
    } std::cout << std::endl; 
} 

quả

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
-1 0 1 2 3 4 -1 5 6 7 8 9 -1 10 11 12 13 14 -1 15 16 17 18 19 -1 20 21