Как я могу распараллелить цикл for через C ++ std :: list с помощью OpenMP?

Я хотел бы повторить все элементы в std :: list параллельно, используя OpenMP. Цикл должен иметь возможность изменять элементы списка. Есть ли простое решение для этого? Похоже, что OpenMP 3.0 поддерживает параллель для циклов, когда iterator является Итератором произвольного доступа, но не иначе. В любом случае, я бы предпочел использовать OpenMP 2.0, поскольку у меня нет полного контроля над тем, какие компиляторы доступны мне.

Если мой контейнер был вектором, я мог бы использовать:

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

Я понимаю, что я мог бы скопировать список в вектор, сделать цикл, а затем скопировать все обратно. Однако я хотел бы избежать этой сложности и накладных расходов, если это возможно.

Если вы решите использовать Openmp 3.0 , вы можете использовать функцию 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 } 

Это выполнит цикл в одном streamе, но делегирует обработку элементов другим.

Без OpenMP 3.0 самым простым способом было бы писать все указатели на элементы в списке (или iteratorы в векторе и итерации по этому. Таким образом, вам не нужно было ничего копировать и избегать накладных расходов на копирование самих элементов, поэтому ему не нужно много накладных расходов:

 std::vector 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(); } 

Если вы хотите избежать копирования даже указателей, вы всегда можете создать распараллеливание для цикла вручную. Вы можете либо получить доступ к элементам чередования элементов в списке (как это было предложено KennyTM), либо расколоть диапазон в примерно равных сторожевых частях перед повторением и повторением этих элементов. Позднее кажется предпочтительным, поскольку streamи не позволяют получить доступ к спискам, которые в настоящее время обрабатываются другими streamами (даже если это только следующий указатель), что может привести к ложному совместному использованию. Это выглядит примерно так:

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

Барьер не является строго необходимым, однако, если process мутирует обработанный элемент (что означает, что он не является методом const), может быть какой-то фальшивый обмен без него, если streamи будут итерации по последовательности, которая уже мутируется. Этот способ будет перебирать 3 * n раз по последовательности (где n – количество streamов), поэтому масштабирование может быть менее оптимальным для большого количества streamов.

Чтобы уменьшить накладные расходы, вы можете поставить генерацию диапазонов вне #pragma omp parallel , однако вам нужно будет знать, сколько streamов будет составлять параллельный раздел. Поэтому вам, вероятно, придется вручную установить num_threads или использовать omp_get_max_threads() и обработать случай, когда количество созданных streamов меньше omp_get_max_threads() (что является только верхней границей). Последний способ можно было бы обработать, возможно, назначив каждый stream severa chunks в этом случае ( #pragma omp for нужно использовать #pragma omp for ):

 int max_threads = omp_get_max_threads(); std::vector::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(); } 

Это займет всего три итерации по list (два, если вы можете получить размер списка без итерации). Я думаю, что это самое лучшее, что вы можете сделать для iteratorов без случайного доступа без использования tasks или итерации по некоторой неуместной структуре данных (например, вектор указателя).

Я сомневаюсь, что это возможно, так как вы не можете просто прыгнуть в середину списка, не пройдя по списку. Списки не сохраняются в непрерывной памяти, а iteratorы std :: list не являются случайным доступом. Они только двунаправленные.

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 

Это можно понимать как развернутое как:

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

Учитывая такой код:

 int main() { std::vector l(4,0); #pragma omp parallel for for(int i=0; i 

экспортируйте OMP_NUM_THREADS = 4, выведите следующим образом (обратите внимание на второй раздел, номер рабочего streamа может повторяться):

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

Без использования OpenMP 3.0 у вас есть возможность перебора всех streamов по списку:

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

В этом случае каждый stream имеет свою собственную копию iteratorа ( private ), но только один stream будет обращаться к определенному элементу ( одиночному ), тогда как другие streamи будут перемещаться вперед к следующим элементам ( nowait )

Или вы можете зацикливать один раз, чтобы создать вектор указателей, который затем будет распределен между streamами:

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

В зависимости от вашего конкретного случая один или другой может быть быстрее. Тестирование, которое вам подходит, легко.

Вот решение, которое позволяет вставлять / удалять новые элементы списка параллельно.

Для списка с N элементами мы сначала вырезаем список в списки nthreads с приблизительно элементами N/nthreads . В параллельной области это можно сделать так

 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 l2; #pragma omp for ordered schedule(static) for(int i=0; i 

Где l2 - список разрезов для каждого streamа.

Затем мы можем действовать по каждому списку параллельно. Например, мы можем вставить -1 каждую первую позицию в списке, подобную этой

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

Наконец, после того, как мы параллельно работаем над списками, мы объединяем списки для каждого streamа обратно в один список в следующем порядке:

 #pragma omp for ordered schedule(static) for(int i=0; i 

Алгоритм по существу.

  1. Быстрая перемотка вперед по последовательному списку, составляющая списки разрезов.
  2. Действуйте над списками разрезов параллельно, добавляя, изменяя или удаляя элементы.
  3. Соедините измененные списки списков снова последовательно.

Вот рабочий пример

 #include  #include  #include  #include  int main(void) { std::list 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 l2; #pragma omp for ordered schedule(static) for(int i=0; i 

результат

 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 
  • Поведение Stream.skip с неупорядоченной работой терминала
  • Потоки Java 8: почему параллельный stream медленнее?
  • Запуск ограниченного числа дочерних процессов параллельно в bash?
  • Ядро возврата Cuda
  • Как Java использует несколько ядер?
  • Используют ли новые ключевые слова C # 5.0 «asynchronous» и «ожидающий» несколько ядер?
  • Как настроить тонкую пул streamов для фьючерсов?
  • Параллельный wget в Bash
  • Уменьшение массива в OpenMP
  • Как параллельно выполнять единичные тесты (MSTest)?
  • Как вы запускаете несколько программ параллельно из сценария bash?
  • Давайте будем гением компьютера.