Эффективное параллельное объединение множеств с OpenMP

Question

Мне нужно вычислить глобальный std::set (или эквивалентный глобальный std::unordered_set) в распараллеленной программе OpenMP. На данный момент каждый поток имеет локальный std::set, который затем вычисляется объединение с использованием

#pragma omp critical //critical as std container inserting is not thread safe 
global_set.insert(local_set.begin(), local_set.end());

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

Как я могу улучшить это, распараллеливая объединение наборов? Объединению предшествует большой блок работы, есть ли удобный способ дать все потоки разного объема работы, чтобы позволить другим работать, пока один вставляет элементы в набор? Или можно эффективно распараллелить само объединение (например, объединяя наборы в виде «двоичного дерева»)?

Answer 1

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

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