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

Ответ 1

Если вы решите использовать 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
}

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

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

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

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

#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), может быть какой-то фальшивый обмен без него, если потоки будут итерации по последовательности, которая уже мутировали. Этот путь будет итерировать 3 * n раз по последовательности (где n - количество потоков), поэтому масштабирование может быть менее оптимальным для большого количества потоков.

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

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

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

Ответ 2

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

Ответ 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

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

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

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

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 = 4, выводить следующим образом (обратите внимание на второй раздел, номер рабочего потока может повторяться):

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

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

Ответ 4

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

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

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

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

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

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

Ответ 5

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

Для списка с элементами 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<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);
    }
}

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

Тогда мы можем действовать по каждому списку параллельно. Например, мы можем вставить -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);
}

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

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

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

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

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

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

Результат

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