OpenMP и C: должна ли эта операция быть атомарной? - PullRequest
Новая
       21

OpenMP и C: должна ли эта операция быть атомарной?

3 голосов
/ 10 декабря 2011

Предположим, у нас есть пара массивов в соответствии со следующими объявлениями типов 

bool B[ N ];
Bar Foo[ M ];
int B_of_Foo[ M ]; // 0 <= B_of_Foo[m] < N

B и Foo могут содержать произвольные значения (в зависимости от контекста), в то время как записи B_of_Foo содержатограничено индексами от 0 до N-1.Давайте посмотрим на следующий код: 

bool repeat = true

while( repeat ) {

    repeat = false;

    for( int m = 0; m < M; m++ ) {
      if( complicated_condition( Foo[m] ) {
        B [ B_of_Foo[ m ] ] = true
        repeat |= true;
      }
    }

}

complicated_condition - истина, если некоторые И или ИЛИ в Bs верны, а B[ B_of_Foo[ m ] ] - ложь.Этот код гарантированно завершается при последовательном выполнении.Я хочу распараллелить это с OpenMP.Переменный повтор можно лечить редукцией.Интересно, нужно ли тогда помечать обновление 

B [ B_of_Foo[ m ] ] = true

как атомарную операцию.

Я думаю, что любые одновременные или дублированные обновления приведут к тому же результату.Даже если один поток проверяет сложное_условие с устаревшей версией B[ B_of_Foo[ m ] ], его последующая операция записи не изменит эту запись B, и код будет стабильным, даже если цикл while повторяется без какого-либо обновления B.

1 Ответ

1 голос
/ 11 декабря 2011

Да, обновление B [ B_of_Foo[ m ] ] должно быть атомарным (или иным образом сериализованным), поскольку результат нескольких потоков, записывающих в одну и ту же переменную, не указан, даже , если они пишут одно и то же значение.Из раздела 1.4.1 (Модель памяти) стандарта OpenMP 3:

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

При запуске большинство людей имеют в виду модель памяти, в которой есть некоторая гарантия последовательной согласованности - как в файловой системе POSIX -где, если происходят две одновременные операции записи, они ведут себя так, как если бы они были сериализованы со случайной «победой».Это не помогает, что это тот пример, который чаще всего используют при обучении гонкам данных.Но ничего такого не гарантируется, и в принципе результат может быть полным бредом.(Происходит ли это когда-нибудь в практике на вашей любимой архитектуре - это другой вопрос. Здесь ваши значения являются однобайтовыми, и я должен думать, что вы будете в порядке в большинстве реализаций на x86. Но ничего не гарантировано.)

...