На этом шаге мы рассмотрим особенности организации параллельных вычислений.

    Первый вариант параллельного алгоритма для метода сеток может быть получен, если разрешить произвольный порядок пересчета значений u_ij. Программа для данного способа вычислений может быть представлена в следующем виде:

omp_lock_t dmax_lock; 
omp_init_lock (dmax_lock); 
do { 
dmax = 0; // максимальное изменение значений u 
#pragma omp parallel for shared(u,n,dmax) \ 
private(i,temp,d) 
for ( i=1; i<N+1; i++ ) { 
  #pragma omp parallel for shared(u,n,dmax) \ 
  private(j,temp,d) 
  for ( j=1; j<N+1; j++ ) { 
    temp = u[i][j]; 
    u[i][j] = 0.25*(u[i-1][j]+u[i+1][j]+ 
      u[i][j-1]+u[i][j+1]-h*h*f[i][j]);
    d = fabs(temp-u[i][j]) 
    omp_set_lock(dmax_lock); 
    if ( dmax < d ) dmax = d; omp_unset_lock(dmax_lock); 
  } // конец вложенной параллельной области 
} // конец внешней параллельной области 
} while ( dmax > eps ); 

    Следует отметить, что программа получена из исходного последовательного кода путем добавления директив и операторов обращения к функциям библиотеки OpenMP.

    Параллельные области в данном примере задаются директивой parallel for, являются вложенными и включают в свой состав операторы цикла for. Компилятор, поддерживающий технологию OpenMP, разделяет выполнение итераций цикла между несколькими потоками программы, количество которых обычно совпадает с числом процессоров в вычислительной системе. Параметры директивы shared и private определяют доступность данных в потоках программы.

    Наличие общих данных обеспечивает возможность взаимодействия потоков. В этом плане разделяемые переменные могут рассматриваться как общие ресурсы потоков и, как результат, их использование должно выполняться с соблюдением правил взаимоисключения. В данном примере таким разделяемым ресурсом является величина dmax, доступ потоков к которой регулируется специальной служебной переменной (семафором) dmax_lock и функциями omp_set_lock (блокировка доступа) и omp_unset_lock (снятие запрета на доступ). Подобная организация программы гарантирует единственность доступа потоков для изменения разделяемых данных. Участки программного кода (блоки между обращениями к функциям omp_set_lock и omp_unset_lock), для которых обеспечивается взаимоисключение, обычно именуются критическими секциями.

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

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

    Новый вариант программы решения задачи Дирихле имеет вид:

omp_lock_t dmax_lock; 
omp_init_lock(dmax_lock); 
do { 
  dmax = 0; // максимальное изменение значений u 
  #pragma omp parallel for shared(u,n,dmax)\ 
  private(i,temp,d,dm) 
  for ( i=1; i<N+1; i++ ) { 
    dm = 0; 
    for ( j=1; j<N+1; j++ ) { 
      temp = u[i][j]; 
      u[i][j] = 0.25*(u[i-1][j]+u[i+1][j]+ 
        u[i][j-1]+u[i][j+1]-h*h*f[i][j]); 
      d = fabs(temp-u[i][j]) 
      if ( dm < d ) dm = d; 
    } 
    omp_set_lock(dmax_lock); 
    if ( dmax < dm ) dmax = dm; 
    omp_unset_lock(dmax_lock); 
  } 
} // конец параллельной области 
} while ( dmax > eps ); 

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

    На следующем шаге мы рассмотрим возможность неоднозначности вычислений в параллельных программах.

Предыдущий шаг Содержание Следующий шаг