OpenMP: для цикла избежать гонки данных без использования критических - PullRequest
Новая
       27

OpenMP: для цикла избежать гонки данных без использования критических

0 голосов
/ 07 октября 2018

Предположим, у меня есть следующий код на C и я хочу распараллелить его, используя OpenMP. 

for (int i = 0; i < n; ++i)
{
    int key = get_key(i);
    toArray[count[key]++] = fromArray[i];
}

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

#pragma omp parallel for schedule(static)
for (int i = 0; i < n; ++i)
{
    int key = get_key(i);
    #pragma omp criical
    toArray[count[key]++] = fromArray[i];
}

Интересно, есть ли способ распараллелить ее с хорошей производительностью?

1 Ответ

0 голосов
/ 07 октября 2018

Боюсь, ваше предположение неверно.Версия с критическим разделом действительно дает правильный ответ - по крайней мере, не детерминированный ответ.

Для простоты возьмем случай, когда get_key всегда возвращает 0.Последовательная версия будет копировать массив, параллельная - произвольную перестановку.Между всеми итерациями существует упорядоченная зависимость, в которой get_key возвращает одно и то же значение.

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

int index;
#pragma omp atomic capture
index = count[key]++;
#pragma omp atomic write
toArray[index] = fromArray[i];

Интересно, есть ли способ распараллелить его с хорошей производительностью?

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

...