Распараллеливание OpenMP для цикла с картой

Question

Я пытаюсь распараллелить цикл for, который сканирует std::map. Ниже моя игрушечная программа:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <cassert>
#include <omp.h>

#define NUM 100000

using namespace std;

int main()
{
  omp_set_num_threads(16);
  int realThreads = 0;
  string arr[] = {"0", "1", "2"};
  std::map<int, string> myMap;
  for(int i=0; i<NUM; ++i)
    myMap[i] = arr[i % 3];

  string is[NUM];

  #pragma omp parallel for
  for(map<int, string>::iterator it = myMap.begin(); it != myMap.end(); it++)
  {
    is[it->first] = it->second;
    if(omp_get_thread_num() == 0)
      realThreads = omp_get_num_threads();
  }
  printf("First for-loop with %d threads\n", realThreads);

  realThreads = 0;
  #pragma omp parallel for
  for(int i=0; i<NUM; ++i)
  {
    assert(is[i] == arr[i % 3]);
    if(omp_get_thread_num() == 0)
      realThreads = omp_get_num_threads();
  }
  printf("Second for-loop with %d threads\n", realThreads);
  return 0;
}

Команда компиляции:

icc -fopenmp foo.cpp

Вывод вышеуказанного кодового блока:

First for-loop with 1 threads
Second for-loop with 16 threads

Почему я не могу распараллелить первый цикл for?

Answer 1

std::map не предоставляет итераторы с произвольным доступом, только обычный двунаправленный итератор. OpenMP требует, чтобы итераторы в параллельных циклах имели тип произвольного доступа. С другими видами итераторов вместо этого следует использовать явные задачи:

#pragma omp parallel
{
  #pragma omp master
  realThreads = omp_get_num_threads();

  #pragma omp single
  for(map<int, string>::iterator it = myMap.begin(); it != myMap.end(); it++)
  {
    #pragma omp task
    is[it->first] = it->second;
  }
}

Обратите внимание, что в этом случае для каждого элемента карты создается отдельная задача. Поскольку тело задачи очень простое в вычислительном отношении, издержки OpenMP в этом конкретном случае будут относительно высокими.