Директивы C ++ OpenMP

Question

У меня есть цикл, который я пытаюсь распараллелить, и в нем я заполняю контейнер, скажем, карту STL.Затем рассмотрим простой псевдокод ниже, где T1 и T2 - некоторые произвольные типы, тогда как f и g - некоторые функции целочисленного аргумента, возвращающие типы T1, T2 соответственно:

#pragma omp parallel for schedule(static) private(i) shared(c)
for(i = 0; i < N; ++i) {
   c.insert(std::make_pair<T1,T2>(f(i),g(i))
}

Это выглядит довольно просто и выглядит какон должен быть тривиально распараллелен, но он не ускоряется, как я ожидал.Напротив, это приводит к ошибкам во время выполнения в моем коде из-за непредвиденных значений, заполняемых в контейнере, вероятно из-за условий гонки.Я даже пытался поставить барьеры и что-нет, но все безрезультатно.Единственное, что позволяет ему работать, это использовать директиву критической , как показано ниже:

#pragma omp parallel for schedule(static) private(i) shared(c)
for(i = 0; i < N; ++i) {
#pragma omp critical
   {
      c.insert(std::make_pair<T1,T2>(f(i),g(i))
   }
}

Но этот вид делает бесполезным весь смысл использования omp в приведенном выше примере, так кактолько один поток одновременно выполняет большую часть цикла (оператор вставки контейнера).Что мне здесь не хватает?Если не считать изменения в написании кода, может кто-нибудь объяснить?

Answer 1

Этот конкретный пример не подходит для параллелизма, если только f() и g() не являются чрезвычайно дорогими вызовами функций.

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

2. Как уже упоминалось в другом ответе, для параллелизма очень много накладных расходов.Так что, если f() и g() не слишком дорогие, ваш цикл не выполняет достаточно работы, чтобы компенсировать издержки параллелизма.

Теперь предположим, что f() и g() чрезвычайнодорогие вызовы, тогда ваш цикл может быть распараллелен так:

#pragma omp parallel for schedule(static) private(i) shared(c)
    for(i = 0; i < N; ++i) {
        std::pair<T1,T2> p = std::make_pair<T1,T2>(f(i),g(i));

#pragma omp critical
       {
          c.insert(p);
       }
    }

Answer 2

1. c будет, очевидно, иметь гонок данных , как вы уже догадались. Карта STL не является поточно-ориентированной. Вызов метода insert одновременно в нескольких потоках будет иметь очень непредсказуемое поведение, в основном это просто сбой.

2. Да, чтобы избежать гонок данных, у вас должен быть (1) мьютекс, такой как #pragma omp critical, или (2) параллельная структура данных (она же структура данных без просмотра). Однако не все структуры данных могут быть свободны от блокировки в текущем оборудовании. Например, TBB предоставляет tbb::concurrent_hash_map. Если вам не нужно упорядочивать ключи, вы можете использовать его и получить некоторое ускорение, поскольку у него нет обычного мьютекса.

3. В случае, если вы можете использовать только хеш-таблицу и таблица очень велика, вы можете использовать подход, подобный сокращению (см. эту ссылку для концепции сокращения). Хеш-таблицы не заботятся о порядке вставки. В этом случае вы выделяете несколько хеш-таблиц для каждого потока и позволяете каждому потоку параллельно вставлять N / # элементы потока, что даст ускорение. Поиск также может быть легко осуществлен путем параллельного доступа к этим таблицам.

Answer 3

Запуск многопоточного кода заставит вас задуматься о безопасности потоков и совместном доступе к вашим переменным.Пока вы начинаете вставлять в c из нескольких потоков, коллекция должна быть готова к таким «одновременным» вызовам и поддерживать согласованность данных. Вы уверены, что это сделано таким образом?

Другое делоу этого распараллеливания есть свои издержки, и вы не получите ничего, когда попытаетесь запустить очень маленькую задачу в нескольких потоках - со стоимостью разделения и синхронизации вы можете получить еще большее общее время выполнения задачи.