Файл: 12. Параллельные методы решения дифференциальных уравнений в частных производных.pdf

7
// Параллельный метод Гаусса-Зейделя (первый вариант) 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 dm = 0;
for ( j=1; j if ( dm < d ) dm = d;
} omp_set_lock(dmax_lock); if ( dmax < dm ) dmax = dm; omp_unset_lock(dmax_lock);
}
} // конец параллельной области
} while ( dmax > eps );
Алгоритм 12.3.
Второй вариант параллельного алгоритма Гаусса-Зейделя
Как результат выполненного изменения схемы вычислений, количество обращений к общей переменной dmax уменьшается с до раз, что должно приводить к существенному снижению затрат на синхронизацию потоков и уменьшению проявления эффекта сериализации вычислений.
Результаты экспериментов с данным вариантом параллельного алгоритма, приведенные в табл. 12.1, показывают существенное изменение ситуации – ускорение в ряде экспериментов оказывается даже большим, чем используемое количество процессоров (такой эффект
сверхлинейного ускорения
достигается за счет наличия у каждого из процессоров вычислительного сервера своей быстрой кэш- памяти). Следует также обратить внимание, что улучшение показателей параллельного алгоритма достигнуто при снижении максимально возможного параллелизма (для выполнения программы может использоваться не более процессоров).
2
N
N
N
12.2.3. Возможность неоднозначности вычислений в параллельных
программах
Последний рассмотренный вариант организации параллельных вычислений для метода сеток обеспечивает практически максимально возможное ускорение выполняемых расчетов – так, в экспериментах данное ускорение достигало величины 5.9 при использовании четырехпроцессорного вычислительного сервера. Вместе с этим необходимо отметить, что разработанная вычислительная схема расчетов имеет важную принципиальную особенность – порождаемая при вычислениях последовательность обработки данных может различаться при разных запусках программы даже при одних и тех же исходных параметрах решаемой задачи. Данный эффект может проявляться в силу изменения каких-либо условий выполнения программы (вычислительной нагрузки, алгоритмов синхронизации потоков и т.п.), что может повлиять на временные соотношения между потоками (см. рис. 12.5). Взаиморасположение потоков по области расчетов может быть различным: одни потоки могут опережать другие и, обратно, часть потоков могут отставать (при этом, характер взаиморасположения может меняться в ходе вычислений). Подобное поведение параллельных участков программы обычно именуется
состязанием потоков (race condition).

Процессоры
(потоки) значения предшествующей итерации
Процессор 2 опережает
(используются "старые" значения) значения текущей итерации
1 2
3 1
2 3
1 2
3
Процессор 2 отстает
(используются "новые" значения)
Процессор 2 средний
(используются "старые" и "новые" значения) узел сетки, для которого выполняется пересчет значения
Рис. 12.5.
Возможные различные варианты взаиморасположения параллельных потоков
(состязание потоков)
В рассматриваемом примере при вычислении нового значения в зависимости от условий выполнения могут использоваться разные (от предыдущей или текущей итераций) оценки соседних значений по вертикали. Тем самым, количество итераций метода до выполнения условия остановки и, самое главное, конечное решение задачи может различаться при повторных запусках программы.
Получаемые оценки величин будут соответствовать точному решению задачи в пределах задаваемой точности, но, тем не менее, могут быть различными. Использование вычислений такого типа для сеточных алгоритмов получило наименование
метода хаотической релаксации (chaotic relaxation).
ij
u
ij
u
Следует отметить, что в общем случае неоднозначность результатов параллельных вычислений является нежелательной, поскольку повторяемость результатов работы программ является основой для возможности проверки правильности программного обеспечения. Стремление к однозначности получаемых результатов расчета приводит к необходимости соблюдения важного принципа параллельного программирования, в соответствии с которым временная динамика выполнения параллельных потоков не должна сказываться на выполнение параллельных программ.
12.2.4. Проблема взаимоблокировки
Возможный подход для получения однозначных результатов (уход от состязания потоков) может состоять в ограничении доступа к узлам сетки, которые обрабатываются в параллельных потоках программы. Для этого можно ввести набор семафоров row_lock[N], который позволит потокам закрывать доступ к "своим" строкам сетки:
// поток обрабатывает i строку сетки
omp_set_lock(row_lock[i]);
omp_set_lock(row_lock[i+1]);
omp_set_lock(row_lock[i-1]);
// обработка i строку сетки
omp_unset_lock(row_lock[i]);
omp_unset_lock(row_lock[i+1]);
omp_unset_lock(row_lock[i-1]);
Закрыв доступ к своим данным, параллельный поток уже не будет зависеть от динамики выполнения других параллельных участков программы. Результат вычислений потока однозначно определяется значениями данных в момент начала расчетов.
8

Данный подход позволяет продемонстрировать еще одну проблему, которая может возникать в ходе параллельных вычислений. Эта проблема состоит в том, что при организации доступа к множественным общим переменным может возникать конфликт между параллельными потоками и этот конфликт не может быть разрешен успешно. Так, в приведенном фрагменте программного кода при обработке потоками двух последовательных строк (например, строк 1 и 2) может сложиться ситуация, когда потоки блокируют сначала свои строки 1 и 2 и только затем переходят к блокировке оставшихся строк (см. рис.
12.6). В этом случае доступ к необходимым строкам не может быть обеспечен ни для одного потока – возникает неразрешимая ситуация, обычно именуемая
тупиком. Как можно показать, необходимым условием тупика является наличие цикла в графе распределения и запросов ресурсов. В рассматриваемом примере уход от цикла может состоять в строго последовательной схеме блокировки строк потока:
// поток обрабатывает i строку сетки
omp_set_lock(row_lock[i+1]);
omp_set_lock(row_lock[i]);
omp_set_lock(row_lock[i-1]);
// <обработка i строку сетки>
omp_unset_lock(row_lock[i+1]);
omp_unset_lock(row_lock[i]);
omp_unset_lock(row_lock[i-1]);
(следует отметить, что и эта схема блокировки строк может оказаться тупиковой, если рассматривать модифицированную задачу Дирихле, в которой горизонтальные границы являются "склеенными").
Поток 1
Поток 2
Строка 1
Строка 2
Рис. 12.6.
Ситуация тупика при доступе к строкам сетки (поток 1 владеет строкой 1 и запрашивает строку 2, поток 2 владеет строкой 2 и запрашивает строку 1)
12.2.5. Исключение неоднозначности вычислений
Подход, рассмотренный в п. 12.2.4, уменьшает эффект состязания потоков, но не гарантирует единственности решения при повторении вычислений. Для достижения однозначности необходимо использование дополнительных вычислительных схем.
Возможный и широко применяемый в практике расчетов способ состоит в разделении места хранения результатов вычислений на предыдущей и текущей итерациях метода сеток. Схема такого подхода может быть представлена в следующем общем виде:
//Алгоритм 12.4
// Параллельный метод Гаусса-Якоби 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 { dm = 0; for ( j=1; j un[i][j] = 0.25*(u[i-1][j]+u[i+1][j]+
9

10
u[i][j-1]+u[i][j+1]–h*h*f[i][j]); d = fabs(temp-un[i][j]) if ( dm < d ) dm = d;
} omp_set_lock(dmax_lock); if ( dmax < dm ) dmax = dm; omp_unset_lock(dmax_lock);
}
} // конец параллельной области
for ( i=1; i // обновление данных
for ( j=1; j
u[i][j] = un[i][j];
} while ( dmax > eps );
Алгоритм 12.4.
Параллельная реализация сеточного метода Гаусса-Якоби
Как следует из приведенного алгоритма, результаты предыдущей итерации запоминаются в массиве
u
, новые вычисления значения запоминаются в дополнительном массиве un. Как результат, независимо от порядка выполнения вычислений для проведения расчетов всегда используются значения величин от предыдущей итерации метода. Такая схема реализации сеточных алгоритмов обычно именуется
методом Гаусса-Якоби. Этот метод гарантирует однозначность результатов независимо от способа распараллеливания, но требует использования большого дополнительного объема памяти и обладает меньшей (по сравнению с алгоритмом Гаусса-Зейделя) скоростью сходимости. Результаты расчетов с последовательным и параллельным вариантами метода приведены в табл. 12.2.
ij
u
Таблица 12.2
. Результаты вычислительных экспериментов для алгоритма Гаусса-Якоби (p=4)
Последовательный метод
Гаусса-Якоби
(алгоритм 12.4)
Параллельный метод, разработанный по аналогии с алгоритмом 12.3
Размер сетки
k T k T
S
100 5257 1,39 5257 0,73 1,90 200 23067 23,84 23067 11,00 2,17 300 26961 226,23 26961 29,00 7,80 400 34377 562,94 34377 66,25 8,50 500 56941 1330,39 56941 191,95 6,93 600 114342 3815,36 114342 2247,95 1,70 700 64433 2927,88 64433 1699,19 1,72 800 87099 5467,64 87099 2751,73 1,99 900 286188 22759,36 286188 11776,09 1,93 1000 152657 14258,38 152657 7397,60 1,93 2000 337809 134140,64 337809 70312,45 1,91 3000 655210 247726,69 655210 129752,13 1,91
(k – количество итераций, T – время в сек., S – ускорение)
Иной возможный подход для устранения взаимозависимости параллельных потоков состоит в применении схемы чередования обработки четных и нечетных строк (red/black row alternation scheme), когда выполнение итерации метода сеток подразделяется на два последовательных этапа, на первом из которых обрабатываются строки только с четными номерами, а затем на втором этапе - строки с нечетными номерами (см. рис. 12.7). Данная схема может быть обобщена на применение одновременно и к строкам, и к столбцам (блочное разбиение) области расчетов.
Рассмотренная схема чередования строк не требует по сравнению с методом Гаусса-Якоби какой- либо дополнительной памяти и обеспечивает однозначность решения при многократных запусках программы. Но следует заметить, что оба рассмотренных в данном пункте подхода могут получать результаты, не совпадающие с решением задачи Дирихле, найденном при помощи последовательного алгоритма. Кроме того, эти вычислительные схемы имеют меньшую область и худшую скорость сходимости, чем исходный вариант метода Гаусса-Зейделя.

граничные значения значения предшествующей итерации
Этап 1
Этап 2 значения после этапа 1 текущей итерации значения после этапа 2 текущей итерации
Рис. 12.7.
Схема чередования обработки четных и нечетных строк
12.2.6. Волновые схемы параллельных вычислений
Рассмотрим теперь возможность построения параллельного алгоритма, который выполнял бы только те вычислительные действия, что и последовательный метод (может быть только в некотором ином порядке) и, как результат, обеспечивал бы получение точно таких же решений исходной вычислительной задачи. Как уже было отмечено выше, в последовательном алгоритме каждое очередное
k-ое приближение значения вычисляется по последнему
k-ому приближению значений и и предпоследнему (
k-1)-ому приближению значений и
. Как результат, при требовании совпадения результатов вычислений последовательных и параллельных вычислительных схем в начале каждой итерации метода только одно значение может быть пересчитано (возможности для распараллеливания нет). Но далее после пересчета вычисления могут выполняться уже в двух узлах сетки и
(в этих узлах выполняются условия последовательной схемы), затем после пересчета узлов и
- в узлах
, и и т.д. Обобщая сказанное, можно увидеть, что выполнение итерации метода сеток можно разбить на последовательность шагов, на каждом из которых к вычислениям окажутся подготовленными узлы вспомогательной диагонали сетки с номером, определяемом номером этапа – см. рис. 12.8. Получаемая в результате вычислительная схема получила наименование
волны или фронта вычислений, а алгоритмы, получаемые на ее основе, - методами
волновой обработки данных (wavefront or hyperplane methods). Следует отметить, что в нашем случае размер волны (степень возможного параллелизма) динамически изменяется в ходе вычислений – волна нарастает до своего пика, а затем затухает при приближении к правому нижнему узлу сетки.
ij
u
j
i
u
,
1
−
1
,
−
j
i
u
j
i
u
,
1
+
1
,
+
j
i
u
11
u
11
u
12
u
21
u
12
u
21
u
13
u
22
u
31
u