OpenMP Shared Array в C: проблема сокращения по сравнению с атомарным обновлением - PullRequest
Новая
       54

OpenMP Shared Array в C: проблема сокращения по сравнению с атомарным обновлением

0 голосов
/ 04 ноября 2019

У меня проблемы с определением, что происходит с этим примером задачи OpenMP. Для контекста y - это большой общий массив, а rowIndex не уникален для каждой задачи. Может быть несколько задач, пытающихся увеличить значение y [rowIndex].

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

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

#pragma omp parallel shared(y) // ??? reduction(+:y) ???
#pragma omp single
for(i = 0; i < n; i++)
{  
  sum = DoSmallWork_SingleThread();  
  rowIndex = getRowIndex_SingleThread();

  #pragma omp task firstprivate(sum, rowIndex)  
  {    
    sum += DoLotsOfWork_TaskThread();

    // ??? #pragma omp atomic update ???
    y[ rowIndex ] += sum;  
  }
}

1 Ответ

2 голосов
/ 05 ноября 2019

У вас есть в основном 3 решения, чтобы избежать этих типов гонки, о которых вы все упоминаете. Все они работают по-разному:

  1. атомарный доступ , т. Е. Предоставление потокам / задачам доступа к одному и тому же массиву в одно и то же время, но при этом обеспечивается правильное упорядочение операций. Это сделанос помощью предложения shared для массива с предложением atomic для операции: 

    #pragma omp parallel
#pragma omp single
for(i = 0; i < n; i++)
{
    sum = DoSmallWork_SingleThread();
    rowIndex = getRowIndex_SingleThread();

    #pragma omp task firstprivate(sum, rowIndex) shared(y)
    {
        increment = sum + DoLotsOfWork_TaskThread();

        #pragma omp atomic
        y[rowIndex] += increment;
    }
}

  2. приватизация , т. е. каждая задача / поток имеет свою собственнуюкопия массива, а затем они затем суммируются, что и делает предложение reduction: 

    #pragma omp parallel
#pragma omp single
#pragma omp taskgroup task_reduction (+:y[0:n-1])
for(int i = 0; i < n; i++)
{
    int sum = DoSmallWork_SingleThread();
    int rowIndex = getRowIndex_SingleThread();

    #pragma omp task firstprivate(sum, rowIndex) in_reduction(+:y[0:n-1])
    {
        y[rowIndex] += sum + DoLotsOfWork_TaskThread();
    }
}

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

    #pragma omp parallel
#pragma omp single
for(i = 0; i < n; i++)
{
    sum = DoSmallWork_SingleThread();
    rowIndex = getRowIndex_SingleThread();

    #pragma omp task firstprivate(sum, rowIndex) depend(inout:y[rowIndex])
    {
        y[rowIndex] += sum + DoLotsOfWork_TaskThread();
    }
}

Когда следуетиспользовать каждый из них?

  1. Атомарный доступ - это более медленный тип доступа к памяти, который обеспечивает гарантии согласованности и может быть особенно медленным в случае конфликтов, то есть когда два (или более)Потоки пытаются изменить одно и то же значение одновременно.

    Предпочтительно использовать атомарность только тогда, когда обновления до y немногочисленны, а вероятность возникновения конфликтов мала.

  2. Приватизация позволяет избежать этого конфликтапроблема, создавая копии массивов и соединяя их (в вашем случае, добавляя их) вместе.

    Это приводит к перегрузке памяти и, возможно, влияет на кэш, пропорционально размеру y.

  3. Наконец, предоставление зависимостей задач полностью устраняет проблему, используя планирование , то есть только одновременное выполнение задач, которые изменяют отдельные части массива. В общем, это предпочтительно, когда y велико и операции, модифицирующие y, часто встречаются в задаче.

    Однако ваш параллелизм ограничен числом зависимостей, которые вы определяете, поэтому в приведенном выше примерепо количеству строк в y. Например, если у вас только 8 строк, а 32 ядра, это может быть не лучшим подходом, поскольку вы будете использовать только 25% своей вычислительной мощности.

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

...