Преобразование для цикла в OpenMP

Question

Итак, у меня есть цикл, в котором я повторяю элементы вектора, вызываю функцию для каждого элемента, и если она соответствует определенным критериям, я нажимаю ее на список.

my_list li; 

for (auto itr = Obj.begin(); itr != Obj.end(); ++itr) { 
    if ((*itr).function_call()) 
     li.push_back((*itr); 
} 

Я думал о том, чтобы оптимизировать свою программу, и я наткнулся на OpenMP, но много образец кода трудно следовать.

Может ли кто-нибудь пройти меня, как преобразовать вышеуказанный цикл, чтобы использовать несколько ядер параллельно?

Спасибо.

Answer 1

Есть несколько моментов, которые вы должны позаботиться, чтобы распараллелить, что фрагмент кода

1. Если вы используете OpenMP 3.0 (или выше), вы можете распараллеливания для цикла #pragma omp for, если вы используете более старую версию OpenMP, вам нужно использовать вектор доступа, ориентированный на цикл, с индексами.
2. Вы должны защитить li.push_back((*itr); заявление с замком или установить его в качестве критической секции
3. Если function_call не очень медленно функции или ваш вектор не содержит так много деталей, то оно не может быть необходимо распараллелить как создание потоков будет ввести накладные расходы.

Так реализация псевдо-код будет

my_list li; 
#pragma omp for 
for (auto itr = Obj.begin(); itr != Obj.end(); ++itr) { 
    if ((*itr).function_call()) 
    { 
     #pragma omp critical CRIT_1 
     { 
      li.push_back((*itr); 
     } 
    } 
}

Answer 2

Пришло время, чтобы обсудить эффективные способы использования классов контейнеров, таких как станд :: список или станд :: вектор с OpenMP (с OP хочет оптимизировать свой код, используя списки с OpenMP). Позвольте мне перечислить четыре способа повышения эффективности.

1. Заполните контейнер в параллельной секции в критическом блоке
2. Сделать частные версии контейнера для каждого потока, заполнить их параллельно, а затем объединить их в критической секции
3. Не используйте STL. STL не был разработан с учетом эффективности. Вместо этого напишите свой собственный или используйте что-то вроде Agner Fog's containters, которые предназначены для повышения эффективности. Например, вместо использования кучи для распределения памяти они используют пул памяти.
4. В некоторых особых случаях можно также объединить частные версии контейнеров параллельно.

Пример кода для первого случая приведен в принятом ответе. Это приводит к большей части использования сквозного кода, поскольку каждая итерация заполняет контейнер в критическом разделе.

Пример кода для второго случая можно найти по адресу: C++ OpenMP Parallel For Loop - Alternatives to std::vector. Вместо того, чтобы повторно опубликовать код здесь позвольте мне привести пример для третьего случая с использованием контейнерами классов Agner противотуманными в

DynamicArray<int> vec; 
#pragma omp parallel 
{ 
    DynamicArray<int> vec_private; 
    #pragma omp for nowait //fill vec_private in parallel 
    for(int i=0; i<100; i++) { 
     vec_private.Push(i); 
    } 
    //merging here is probably not optimal 
    //Dynamic array needs an append function 
    //vec should reserve a size equal to the sum of size each vec_private 
    //then use memcpy to append vec_private into vec in a critcal section 
    #pragma omp critical 
    { 
     for(int i=0; i<vec_private.GetNum(); i++) { 
      vec.Push(vec_private[i]); 
     } 
    }   
} 

Наконец, в особых случаях, например, с гистограммами (вероятно, наиболее распространенной структурой данных в экспериментальной физике элементарных частиц) , можно параллельно объединить частные массивы. Для гистограмм это эквивалентно уменьшению массива. Это немного сложно.Пример, показывающий, как это сделать, можно найти на странице Fill histograms (array reduction) in parallel with OpenMP without using a critical section