OMP и параллельные операции над std :: set & lt; … & gt; :: iterator

Учитывая структуру данных на основе карта показано ниже:

std::map<int, std::set<std::vector<int>>> cliques;

Где ключ указывает на размер из векторов, содержащихся на нем.

В начале карта имеет только один ключ (например. [3]) который содержит входные векторы (например. {1, 3, 5} а также {2, 4, 6}).

Моя функция принимает векторы хранится в самый большой ключ из карта а также разлагаться их во все возможное комбинации показывая меньше элементов и хранить их в ключ в соответствии с размером новых векторов (например, [2] = {1,3} {1,5} {3,5} {2,4} {2,6} {4,6} and [1] = {1} {3} {5} {2} {4} {6})

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

/// Declare data structure
std::map<int, std::set<std::vector<int>>> cliques;

/// insert "input" vectors
cliques[5] = {{1, 3, 5, 7, 9}};
cliques[4] = {{1, 2, 3, 4}};

/// set boundaries
int kMax = 5;
int kMin = 1;

/// enable/disable parallel execution
bool parallelExec = true;

/// "decompose" source vectors:
for (int k = kMax; k > kMin; k--)
{
std::set<std::vector<int>>::iterator it = cliques[k].begin();
#pragma omp parallel num_threads(max_threads) if(parallelExec)
{
for(int s = 0; s < cliques[k].size(); ++s)
{
std::vector<int> clique;
/// maybe should be "omp critical"?
/// maybe "clique" should be private? (or is it already??)
#pragma omp single
{
clique = *it;
}
for (int v = 0; v < clique.size(); ++v)
{
int& vertex = clique[v];
std::vector<int> new_clique;
std::copy_if(clique.begin(), clique.end(), std::back_inserter(new_clique), [vertex](const int& elem) { return elem != vertex; });
int kNew = k - 1;
#pragma omp critical
{
cliques[kNew].insert(new_clique);
}
}
#pragma omp single
{
it++;
}
}
}
}

/// Display results
for(int i = cliques.size(); i > 0 ; i--)
{
auto kSet = cliques[i];
std::cout << "[" << i << "]: ";
for(auto& vec : kSet)
{
std::cout << "{";
for(auto& elem : vec)
{
std::cout << elem << " ";
}
std::cout << "} ";
}
std::cout << std::endl;
}

Использование «omp параллель» а также «omp single» (вместо «omp for») позволяет безопасно получить доступ к структуре данных, в то же время позволяя всем другим операциям выполняться параллельно. Код работает почти отлично, почти … так как он пропускает некоторые (очень немного) субвекторы в конечных результатах (которые успешно генерируются, если omp отключен).

Есть ли «OMP expert» в состоянии помочь мне с этой проблемой? Заранее спасибо.

—————

ОБНОВИТЬ

Минимальный завершенный проверяемый пример

1

Решение

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

  1. Вы не распараллеливаете обработку: вы не распределяете работу между потоками, вы только реплицируете одну и ту же работу на все потоки, которые наступают друг другу на ноги, чтобы записать результат обратно в то же место.
  2. Даже это не сделано должным образом с момента приращения итератора, что делается с помощью omp single nowait позволяет потокам работать на предыдущей итерации, так как нет синхронизации по значению it выполняется на этом этапе. (Примечание: omp single без nowait который защищает приращение итератора при выходе имеет неявный barrier что обеспечивает потоку согласованное представление этого значения, поэтому расхождение может быть только между текущей итерацией и предыдущей)
  3. это cliques[kNew].insert(new_clique); это действительно место, где все могут взорваться, поскольку доступ к одному и тому же местоположению осуществляется одновременно, что не поддерживается стандартным контейнером. (и что в любом случае неправильно, до предела моего понимания)

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

Наконец, я собирался предложить вам мой алгоритм, но так как в вашем фрагменте кода так много не хватает, я просто не могу.
Если вы разместите правильный mcve, тогда, возможно, я буду.

Обновить
Исходя из вашего кода, здесь возможна параллельная версия:

for (int k = kMax; k > kMin; k--)
{
std::set<std::vector<int>>::iterator it = cliques[k].begin();
for(int s = 0; s < cliques[k].size(); ++s)
{
std::vector<int> clique = *it;
#pragma omp parallel for num_threads(max_threads)
for (int v = 0; v < clique.size(); ++v)
{
int& vertex = clique[v];
std::vector<int> new_clique;
std::copy_if(clique.begin(), clique.end(), std::back_inserter(new_clique), [vertex](const int& elem) { return elem != vertex; });
int kNew = k - 1;
#pragma omp critical
cliques[kNew].insert(new_clique);
}
it++;
}
}
2

Другие решения

Других решений пока нет …