Блог

Всем доброго времени суток! Не так давно мне удалось распараллелить рекурсивный алгоритм поиска возможных вариантов объединения некоторых событий. На данный момент код выглядит следующим образом:

 //#include's
// function announcements
// declaring a global variable:
QVector<QVector<QVector<float>>> variant; (or "std::vector")
 
int main() {
 
    // reads data from file
    // data are converted and analyzed
 
    // the variant variable containing the current best result is filled in (here - by pre-analysis)
 
    #pragma omp parallel shared(variant)
    #pragma omp master
    // occurs call a recursive algorithm of search all variants:
    PEREBOR(Tabl_1, a, i_a, ..., reс_depth);
 
    return 0;
}
 
void PEREBOR(QVector<QVector<uint8_t>> Tabl_1, QVector<A_struct> a, uint8_t i_a, ..., uint8_t reс_depth)
{
    // looking for the boundaries of the first cycle for some reasons
    for (int i = quantity; i < another_quantity; i  ) {
        // the Tabl_1 is processed and modified to determine the number of steps in the subsequent for cycle
        for (int k = 0; k < the_quantity_just_found; k  ) {
            if the recursion depth is not 1, we go down further: {
                // add descent to the next recursion level to the call stack:
                #pragma omp task
                PEREBOR(Tabl_1_COPY, a, i_a, ..., reс_depth-1);
            }
            else (if we went down to the lowest level): {
                if (condition fulfilled) // condition check - READ variant variable
                    variant = it_is_equal_to_that_,_to_that...;
                else
                    continue;
            }
        }
    }
}
 

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

 omp_lock_t lock;

int main() {
...
omp_init_lock(amp;lock);
#pragma omp parallel shared(variant, lock)
...
}

...
else (if we went down to the lowest level): {
    if (condition fulfilled) { // condition check - READ variant variable
        omp_set_lock(amp;lock);
        variant = it_is_equal_to_that_,_to_that...;
        omp_unset_lock(amp;lock);
        }
    else
        continue;
...
 

будет ли эта блокировка защищать чтение переменной во всех других местах? Или мне нужно будет вручную проверить статус блокировки и приостановить поток, прежде чем читать в другом месте?
Я буду невероятно благодарен уважаемому сообществу за помощь!

В спецификации OpenMP (1.4.1 Структура модели памяти OpenMP) вы можете прочитать

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

Это практически означает, что (как и в любой модели с ослабленной памятью), только в четко определенных точках потоки гарантированно имеют одинаковое, согласованное представление о значении общих переменных. Между такими точками временное представление может отличаться в потоках.

В своем коде вы справились с проблемой одновременной записи одной и той же переменной, но нет никакой гарантии, что другой поток прочитает правильное значение переменной без дополнительных мер.

У вас есть 3 варианта действий (обратите внимание, что каждое из этих решений не только обрабатывает одновременное чтение/запись, но и обеспечивает согласованное представление значений общих переменных).:

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

 #pragma omp parallel
{
    ...
    #pragma omp atomic read 
    tmp=variant;
    ....
    #pragma omp atomic write
    variant=new_value;
}
 

2. Используйте критическую конструкцию. Это решение можно использовать, если ваша переменная имеет сложный тип (например, класс) и ее чтение/запись не может быть выполнена атомарно. Обратите внимание, что это гораздо менее эффективно (медленнее), чем атомарная операция.

 #pragma omp parallel
{
    ...
    #pragma omp critical 
    tmp=variant;
    ....
    #pragma omp critical
    variant=new_value;
}
 

3. Используйте блокировки для каждого чтения/записи вашей переменной. Ваш код подходит для записи, но его также нужно использовать для чтения. Это требует наибольшего кодирования, но практически результат такой же, как при использовании критической конструкции. Обратите внимание, что реализации OpenMP обычно используют блокировки для реализации критических конструкций.