Блог

У меня есть параллельный алгоритм C , который выглядит примерно так:

 void recursiveFunction(int p, std::unordered_set<int> localSet) {
    vector<someStruct> toCall;
    if (p > SOMEINT) {
        return;
    }
    #pragma omp parallel for schedule(dynamic, 1) shared(localSet, someGlobalVector, someOtherGlobalVector)
    for (int i = 0; i < someGlobalVector[p].size();   i) {
        auto someLocalValue = someGlobalVector[p][i];
        auto someOtherLocal = someOtherGlobalVector[p][i];
        std::unordered_set<int> filtered;
        for (auto elem : localSet) {
            if (someLocalValue.count(elem) == 0) {
                filtered.insert(elem);
            }
        }
        if (checkSomeCondition(p 1, filtered)) {
            #pragma omp critical
            {
                tocall.push_back({someOtherLocal, filtered});
            }
        }
    }
    for (auto [elem1, elem2] : toCall) {
        recursiveFunction(p 1, filtered);
    }
}
 

Безопасна ли итерация через общий unordered_set поток?

Безопасна ли итерация через общий поток unordered_set?

Нет, an unordered_set не является потокобезопасным по определению. Однако это не обязательно означает, что при использовании таких структур в коде возникает условие гонки; Например, если кто-то только читает структуру данных, даже одновременно, тогда он находится в безопасности. Это причина, по которой действительно неизменяемые структуры данных потокобезопасны по определению, потому что нельзя изменять эти структуры, отсюда и название.

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

Не Потокобезопасные структуры данных, такие как unordered_set , полагаются на код, обращающийся к ним, для обеспечения взаимного исключения при текущем изменении этих структур несколькими потоками.

Чтобы избежать условий гонки, можно использовать конструктор OpenMP critical для синхронизации обращений к общей структуре во время insert операции:

 #pragma omp critical
{
  // the code to insure mutual exclusion.
}
 

Однако это замедлило бы распараллеливание из-за накладных расходов на такой механизм синхронизации. В качестве альтернативы можно создать структуры данных, к которым каждый поток будет обращаться только по отдельности, вставить в эти структуры и заставить основной поток объединить эти структуры в одну (вне параллельной области).

Давайте немного разберем ваш код:

 void recursiveFunction(int p, std::unordered_set<int> localSet) {
    #pragma omp parallel for schedule(dynamic, 1) shared(localSet, someGlobalVector, someOtherGlobalVector)
    for (int i = 0; i < someGlobalVector[p].size();   i) {
        auto someLocalValue = someGlobalVector[p][i];
        auto someOtherLocal = someOtherGlobalVector[p][i];
        std::unordered_set<int> filtered
        for (auto elem : localSet) {
            if (someLocalValue.count(elem) == 0) {
                filtered.insert(elem)
            }
        }
    }
}
 

localSet , someGlobalVector , someOtherGlobalVector являются общими, но они доступны только для чтения. Следовательно, пока нет другого потока вне этого метода (работающего одновременно), изменяющего эти структуры, все в порядке. vector<someStruct> toCall Разделяется и изменяется, но модификация происходит внутри критического конструктора, поэтому там нет условия гонки.

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

 void recursiveFunction(int p, std::unordered_set<int> localSet, int total_threads) {
    vector<someStruct> thread_tocall[total_threads];
    vector<someStruct> toCall;
    if (p > SOMEINT) {
        return;
    }
    #pragma omp parallel shared(localSet, someGlobalVector, someOtherGlobalVector)
    {
        int thread_id = omp_get_thread_num();
        for (int i = 0; i < someGlobalVector[p].size();   i) {
             auto someLocalValue = someGlobalVector[p][i];
             auto someOtherLocal = someOtherGlobalVector[p][i];
             std::unordered_set<int> filtered;
             for (auto elem : localSet) {
                 if (someLocalValue.count(elem) == 0) {
                    filtered.insert(elem);
                 }
             }
           if (checkSomeCondition(p 1, filtered)) {
                thread_tocall[thread_id].push_back({someOtherLocal, filtered});
            }
         }
    }
    for(int i = 0; i < total_threads; i  )
       for (auto [elem1, elem2] : thread_tocall[i]) {
          recursiveFunction(p 1, filtered);
       }
}
 

Если глобальный объект предварительно заполнен и читается только тогда — тогда да, он обычно потокобезопасен. Но если общий объект может быть изменен, пока кто-то его читает, тогда чтение также становится небезопасным для потоков.