C++ OpenMP Parallel For Loop - Альтернативы std :: vector

Question

На основе этой темы OpenMP and STL vector, какие структуры данных являются хорошими альтернативами для shared std :: vector в параллельном для цикла? Основной аспект - скорость, и вектор может потребовать изменения размера во время цикла.

Answer 1

Вопрос, на который вы ссылаетесь, говорит о том, что «этот векторный контейнер STL не является потокобезопасным в ситуации, когда несколько потоков записываются в один контейнер». Это верно, как указано здесь правильно, если вы вызываете методы, которые могут привести к перераспределению базового массива, который имеет std::vector. push_back(), pop_back() и insert() являются примерами этих опасных методов.

Если вам требуется безопасное перераспределение потоков, тогда библиотека intel thread building block предлагает вам concurrent vector containers. Вы не должны использовать tbb :: concurrent_vector в программах с одним потоком, потому что время, необходимое для доступа к случайным элементам, выше, чем время std :: vector, чтобы сделать то же самое (это O (1)). Однако одновременные векторные вызовы push_back(), pop_back(), insert() в потоковом безопасном режиме, даже если происходит перераспределение.

EDIT 1: Слайды 46 и 47 из the following Intel presentation дать иллюстративный пример параллельного перераспределению с использованием TBB :: concurrent_vector

EDIT 2: Кстати, если вы начнете использовать Intel Протектор Building Block (это с открытым исходным кодом , он работает с большинством компиляторов, и он намного лучше интегрирован с функциями C++/C++ 11, чем openmp), тогда вам не нужно использовать openmp для создания parallel_for, Here - хороший пример parallel_for использования tbb.

Answer 2

Я думаю, вы можете использовать std::vector с OpenMP большую часть времени и по-прежнему иметь хорошую производительность. Следующий код, например, заполняет std::vectors параллельно, а затем объединяет их в конце. Пока ваша основная функция цикла/заполнения является узким местом, это должно хорошо работать и быть потокобезопасным.

std::vector<int> vec; 
#pragma omp parallel 
{ 
    std::vector<int> vec_private; 
    #pragma omp for nowait //fill vec_private in parallel 
    for(int i=0; i<100; i++) { 
     vec_private.push_back(i); 
    } 
    #pragma omp critical 
    vec.insert(vec.end(), vec_private.begin(), vec_private.end()); 
} 

Edit:

OpenMP 4.0 позволяет определяемых пользователем сокращений с помощью #pragma omp declare reduction. Код выше может быть упрощена до

#pragma omp declare reduction (merge : std::vector<int> : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end())) 

std::vector<int> vec; 
#pragma omp parallel for reduction(merge: vec) 
for(int i=0; i<100; i++) vec.push_back(i); 

Edit: Что я показал до сих пор не заполняет вектор в порядке. Если порядок имеет значение, то это можно сделать, как этот

std::vector<int> vec; 
#pragma omp parallel 
{ 
    std::vector<int> vec_private; 
    #pragma omp for nowait schedule(static) 
    for(int i=0; i<N; i++) { 
     vec_private.push_back(i); 
    } 
    #pragma omp for schedule(static) ordered 
    for(int i=0; i<omp_get_num_threads(); i++) { 
     #pragma omp ordered 
     vec.insert(vec.end(), vec_private.begin(), vec_private.end()); 
    } 
} 

Это позволяет избежать сохранений зОго :: вектора для каждого потока, а затем объединять их в последовательных за пределы параллельной области. Я узнал об этом «трюке» here. Я не уверен, как это сделать (или даже если это возможно) для пользовательских сокращений.. Это невозможно сделать с пользовательскими сокращениями.

Я только понял, что критический раздел не нужен, что я выяснил из этого вопроса parallel-cumulative-prefix-sums-in-openmp-communicating-values-between-thread. Этот метод также правильно набирает порядок.

std::vector<int> vec; 
size_t *prefix; 
#pragma omp parallel 
{ 
    int ithread = omp_get_thread_num(); 
    int nthreads = omp_get_num_threads(); 
    #pragma omp single 
    { 
     prefix = new size_t[nthreads+1]; 
     prefix[0] = 0; 
    } 
    std::vector<int> vec_private; 
    #pragma omp for schedule(static) nowait 
    for(int i=0; i<100; i++) { 
     vec_private.push_back(i); 
    } 
    prefix[ithread+1] = vec_private.size(); 
    #pragma omp barrier 
    #pragma omp single 
    { 
     for(int i=1; i<(nthreads+1); i++) prefix[i] += prefix[i-1]; 
     vec.resize(vec.size() + prefix[nthreads]); 
    } 
    std::copy(vec_private.begin(), vec_private.end(), vec.begin() + prefix[ithread]); 
} 
delete[] prefix;