Файл: 12. Параллельные методы решения дифференциальных уравнений в частных производных.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.11.2023
Просмотров: 81
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
12.3.2. Обмен информацией между процессорами
Параллельный вариант метода сеток при ленточном разделении данных состоит в обработке полос на всех имеющихся серверах одновременно в соответствии со следующей схемой работы:
//Алгоритм 12.8
// Параллельный метод
Гаусса-Зейделя
(распределенная память,
ленточная схема)
// действия, выполняемые на каждом процессоре do {
// <обмен граничных строк полос с соседями>
// <обработка полосы>
// <вычисление общей погрешности вычислений dmax>} while ( dmax > eps ); // eps - точность решения
Алгоритм 12.8.
Параллельный алгоритм, реализующий метод сеток при ленточном разделении данных
Для конкретизации представленных в алгоритме действий введем обозначения:
- ProcNum – номер процессора, на котором выполняются описываемые действия,
- PrevProc, NextProc – номера соседних процессоров, содержащих предшествующую и следующую полосы,
- NP – количество процессоров,
- M – количество строк в полосе (без учета продублированных граничных строк),
- N – количество внутренних узлов в строке сетки (т.е. всего в строке N+2 узла).
Для нумерации строк полосы будем использовать нумерацию, при которой строки
0 и M+1 есть продублированные из соседних полос граничные строки, а строки собственной полосы процессора имеют номера от
1 до M.
1 этап
2 этап процессор i процессор i+1
Рис. 12.11.
Схема передачи граничных строк между соседними процессорами
Процедура обмена граничных строк между соседними процессорами может быть разделена на две последовательные операции, во время первой из которых каждый процессор передает свою нижнюю граничную строку следующему процессору и принимает такую же строку от предыдущего процессора
(см. рис. 12.11). Вторая часть передачи строк выполняется в обратном направлении: процессоры передают свои верхние граничные строки своим предыдущим соседям и принимают переданные строки от следующих процессоров.
Выполнение подобных операций передачи данных в общем виде может быть представлено следующим образом (для краткости рассмотрим только первую часть процедуры обмена):
// передача нижней граничной строки следующему
// процессору и прием передаваемой строки от
// предыдущего процессора if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc); if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc);
(для записи процедур приема-передачи используется близкий к стандарту MPI (см., например, Group, et al. (1994)) формат, где первый и второй параметры представляют пересылаемые данные и их объем, а третий параметр определяет адресат (для операции
Send) или источник (для операции Receive) пересылки данных).
Для передачи данных могут быть задействованы два различных механизма. При первом из них выполнение программ, инициировавших операцию передачи, приостанавливается до полного завершения всех действий по пересылке данных (т.е. до момента получения процессором-адресатом всех передаваемых ему данных). Операции приема-передачи, реализуемые подобным образом, обычно называются
синхронными или блокирующими. Иной подход – асинхронная или неблокирующая передача - может состоять в том, что операции приема-передачи только инициируют процесс пересылки и на этом завершают свое выполнение. В результате программы, не дожидаясь завершения длительных коммуникационных операций, могут продолжать свои вычислительные действия, проверяя по мере необходимости готовность передаваемых данных. Оба эти варианта операций передачи широко используются при организации параллельных вычислений и имеют свои достоинства и свои недостатки.
Синхронные процедуры передачи, как правило, более просты для использования и более надежны; неблокирующие операции могут позволить совместить процессы передачи данных и вычислений, но обычно приводят к повышению сложности программирования. С учетом всего выше сказанного для организации пересылки данных во всех последующих примерf[ будут использоваться операции приема- передачи блокирующего типа.
Приведенная выше последовательность блокирующих операций приема-передачи данных (вначале
Send, затем Receive) приводит к строго последовательной схеме выполнения процесса пересылок строк, т.к. все процессоры одновременно обращаются к операции
Send и переходят в режим ожидания. Первым процессором, который окажется готовым к приему пересылаемых данных, окажется сервер с номером
NP-1. В результате процессор NP-2 выполнит операцию передачи своей граничной строки и перейдет к приему строки от процессора
NP-3 и т.д. Общее количество повторений таких операций равно NP-1.
19
20
Аналогично происходит выполнение и второй части процедуры пересылки граничных строк перед началом обработки строк (см. рис. 12.11).
Последовательный характер рассмотренных операций пересылок данных определяется выбранным способом очередности выполнения. Изменим этот порядок очередности при помощи чередования приема и передачи для процессоров с четными и нечетными номерами:
// передача нижней граничной строки следующему
// процессору и прием передаваемой строки от
// предыдущего процессора if ( ProcNum % 2 == 1 ) { // нечетный процессор if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc); if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc);
} else { // процессор с четным номером if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc); if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc);
}
Данный прием позволяет выполнить все необходимые операции передачи всего за два последовательных шага. На первом шаге все процессоры с нечетными номерами отправляют данные, а процессоры с четными номерами осуществляют прием этих данных. На втором шаге роли процессоров меняются – четные процессоры выполняют
Send, нечетные процессоры исполняют операцию приема
Receive.
Рассмотренные последовательности операций приема-передачи для взаимодействия соседних процессоров широко используются в практике параллельных вычислений. Как результат, во многих базовых библиотеках параллельных программ имеются процедуры для поддержки подобных действий.
Так, в стандарте MPI (см., например, Group, et al. (1994)) предусмотрена операция
Sendrecv, с использованием которой предыдущий фрагмент программного кода может быть записан более кратко:
// передача нижней граничной строки следующему
// процессору и прием передаваемой строки от
// предыдущего процессора
Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);
Реализация подобной объединенной функции Sendrecv обычно осуществляется таким образом, чтобы обеспечить и корректную работу на крайних процессорах, когда не нужно выполнять одну из операций передачи или приема, и организацию чередования процедур передачи на процессорах для ухода от тупиковых ситуаций, и возможности параллельного выполнения всех необходимых пересылок данных.
12.3.3. Коллективные операции обмена информацией
Для завершения круга вопросов, связанных с параллельной реализацией метода сеток на системах с распределенной памятью, осталось рассмотреть способы вычисления общей для всех процессоров погрешности вычислений. Возможный очевидный подход состоит в передаче всех локальных оценок погрешности, полученных на отдельных полосах сетки, на один какой-либо процессор, вычисления на нем максимального значения и последующей рассылки полученного значения всем процессорам системы. Однако такая схема является крайне неэффективной – количество необходимых операций передачи данных определяется числом процессоров и выполнение этих операций может происходить только в последовательном режиме. Между тем, как показывает анализ требуемых коммуникационных действий, выполнение операций сборки и рассылки данных может быть реализовано с использованием рассмотренной в п. 2.5 пособия
каскадной схемы обработки данных. На самом деле, получение максимального значения локальных погрешностей, вычисленных на каждом процессоре, может быть обеспечено, например, путем предварительного нахождения максимальных значений для отдельных пар процессоров (данные вычисления могут выполняться параллельно), затем может быть снова осуществлен попарный поиск максимума среди полученных результатов и т.д. Всего, как полагается по каскадной схеме, необходимо выполнить
log
2
NP параллельных итераций для получения конечного значения (NP – количество процессоров).
Учитывая большую эффективность каскадной схемы для выполнения коллективных операций передачи данных, большинство базовых библиотек параллельных программ содержит процедуры для поддержки подобных действий. Так, в стандарте MPI (см., например, Group, et al. (1994)) предусмотрены операции:
- Reduce(dm,dmax,op,proc) – процедура сборки на процессоре
proc итогового результата dmax среди локальных на каждом процессоре значений
dm с применением операции op,
21
- Broadcast(dmax,proc) – процедура рассылки с процессора
proc значения dmax всем имеющимся процессорам системы.
С учетом перечисленных процедур общая схема вычислений на каждом процессоре может быть представлена в следующем виде:
//Алгоритм 12.8 – уточненный вариант
// Параллельный метод
Гаусса-Зейделя
(распределенная память,
ленточная схема)
// действия, выполняемые на каждом процессоре do {
// обмен граничных строк полос с соседями
Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);
Sendrecv(u[1][*],N+2,PrevProc,u[M+1][*],N+2,NextProc);
// <обработка полосы с оценкой погрешности dm>
// вычисление общей погрешности вычислений dmax
Reduce(dm,dmax,MAX,0);
Broadcast(dmax,0);
} while ( dmax > eps ); // eps - точность решения
(в приведенном алгоритме переменная
dm представляет локальную погрешность вычислений на отдельном процессоре, параметр
MAX задает операцию поиска максимального значения для операции сборки). Следует отметить, что в составе MPI имеется процедура
Allreduce, которая совмещает действия редукции и рассылки данных. Результаты экспериментов для данного варианта параллельных вычислений для метода Гаусса-Зейделя приведены в табл. 12.4.
12.3.4. Организация волны вычислений
Представленные в пп. 1-3 алгоритмы определяют общую схему параллельных вычислений для метода сеток в многопроцессорных системах с распределенной памятью. Далее эта схема может быть конкретизирована реализацией практически всех вариантов методов, рассмотренных для систем с общей памятью (использование дополнительной памяти для схемы Гаусса-Якоби, чередование обработки полос и т.п.). Проработка таких вариантов не привносит каких-либо новых эффектов с точки зрения параллельных вычислений, и их разбор может использоваться как темы заданий для самостоятельных упражнений.
Таблица 12.4
. Результаты экспериментов для систем с распределенной памятью, ленточная схема разделения данных (p=4)
Последовательный метод Гаусса-Зейделя
(алгоритм 6.1)
Параллельный алгоритм 6.8
Параллельный алгоритм с волновой схемой расчета
(см. п. 6.3.4)
Размер сетки
k T
k
T
S
k
T
S
100 210 0,06 210 0,54 0,11 210 1,27 0,05 200 273 0,35 273 0,86 0,41 273 1,37 0,26 300 305 0,92 305 0,92 1,00 305 1,83 0,50 400 318 1,69 318 1,27 1,33 318 2,53 0,67 500 343 2,88 343 1,72 1,68 343 3,26 0,88 600 336 4,04 336 2,16 1,87 336 3,66 1,10 700 344 5,68 344 2,52 2,25 344 4,64 1,22 800 343 7,37 343 3,32 2,22 343 5,65 1,30 900 358 9,94 358 4,12 2,41 358 7,53 1,32 1000 351 11,87 351 4,43 2,68 351 8,10 1,46 2000 367 50,19 367 15,13 3,32 367 27,00 1,86 3000 364 113,17 364 37,96 2,98 364 55,76 2,03
(k – количество итераций, T – время в сек., S – ускорение)
В завершение рассмотрим возможность организации параллельных вычислений, при которых обеспечивалось бы нахождение таких же решений задачи Дирихле, что и при использовании исходного последовательного метода Гаусса-Зейделя. Как отмечалось ранее, такой результат может быть получен за счет организации волновой схемы расчетов. Для образования волны вычислений представим
1000 351 11,87 351 4,90 2,42 351 11,16 1,06 2000 367 50,19 367 16,07 3,12 367 39,49 1,27 3000 364 113,17 364 39,25 2,88 364 85,72 1,32
(k – количество итераций, T – время в сек., S – ускорение)
При блочном представлении сетки может быть реализован также и волновой метод выполнения расчетов (см. рис. 12.13). Пусть процессоры образуют прямоугольную решетку размером
(
NBxNB
NP
NB
=
) и процессоры пронумерованы от
0 слева направо по строкам решетки.
Общая схема параллельных вычислений в этом случае имеет вид:
//Алгоритм 12.9
// Параллельный метод
Гаусса-Зейделя
(распределенная память,
блочная схема)
// волновая схема расчетов
// действия, выполняемые на каждом процессоре do {
// получение граничных узлов if ( ProcNum / NB != 0 ) { // строка не нулевая
// получение данных от верхнего процессора
Receive(u[0][*],M+2,TopProc); // верхняя строка
Receive(dmax,1,TopProc); // погрешность
} if ( ProcNum % NB != 0 ) { // столбец не нулевой
// получение данных от левого процессора
Receive(u[*][0],M+2,LeftProc); // левый столбец
Receive(dm,1,LeftProc); // погрешность
If ( dm > dmax ) dmax = dm;
}
// <обработка блока с оценкой погрешности dmax>
// пересылка граничных узлов if ( ProcNum / NB != NB-1 ) { // строка решетки не
// последняя
// пересылка данных нижнему процессору
Send(u[M+1][*],M+2,DownProc); // нижняя строка
Send(dmax,1,DownProc); // погрешность
} if ( ProcNum % NB != NB-1 ) { // столбец решетки
// не последний
// пересылка данных правому процессору
Send(u[*][M+1],M+2,RightProc); // правый столбец
Send(dmax,1, RightProc); // погрешность
}
// синхронизация и рассылка погрешности dmax
Barrier();
Broadcast(dmax,NP-1);
} while ( dmax > eps ); // eps - точность решения
Алгоритм 12.9.
Блочная схема разделения данных
(в приведенном алгоритме функция
Barrier() представляет операцию коллективной синхронизации, которая завершает свое выполнение только в тот момент, когда все процессоры осуществят вызов этой процедуры).
Следует обратить внимание, что при реализации алгоритма нужно обеспечить, чтобы в начальный момент времени все процессоры (кроме процессора с нулевым номером) оказались в состоянии ожидания своих граничных узлов (верхней строки и левого столбца). Вычисления должен начинать процессор с левым верхним блоком, после завершения обработки которого обновленные значения правого столбца и нижней строки блока необходимо переправить правому и нижнему процессорам решетки соответственно. Данные действия обеспечат снятие блокировки процессоров второй диагонали процессорной решётки (ситуация слева на рис. 12.13) и т.д.
Анализ эффективности организации волновых вычислений в системах с распределенной памятью
(см. табл. 12.5) показывает значительное снижение полезной вычислительной нагрузки для процессоров, которые занимаются обработкой данных только в моменты, когда их блоки попадают во фронт волны вычислений. При этом балансировка (перераспределение) нагрузки является крайне затруднительной,
23
Параллельный вариант метода сеток при ленточном разделении данных состоит в обработке полос на всех имеющихся серверах одновременно в соответствии со следующей схемой работы:
//Алгоритм 12.8
// Параллельный метод
Гаусса-Зейделя
(распределенная память,
ленточная схема)
// действия, выполняемые на каждом процессоре do {
// <обмен граничных строк полос с соседями>
// <обработка полосы>
// <вычисление общей погрешности вычислений dmax>} while ( dmax > eps ); // eps - точность решения
Алгоритм 12.8.
Параллельный алгоритм, реализующий метод сеток при ленточном разделении данных
Для конкретизации представленных в алгоритме действий введем обозначения:
- ProcNum – номер процессора, на котором выполняются описываемые действия,
- PrevProc, NextProc – номера соседних процессоров, содержащих предшествующую и следующую полосы,
- NP – количество процессоров,
- M – количество строк в полосе (без учета продублированных граничных строк),
- N – количество внутренних узлов в строке сетки (т.е. всего в строке N+2 узла).
Для нумерации строк полосы будем использовать нумерацию, при которой строки
0 и M+1 есть продублированные из соседних полос граничные строки, а строки собственной полосы процессора имеют номера от
1 до M.
1 этап
2 этап процессор i процессор i+1
Рис. 12.11.
Схема передачи граничных строк между соседними процессорами
Процедура обмена граничных строк между соседними процессорами может быть разделена на две последовательные операции, во время первой из которых каждый процессор передает свою нижнюю граничную строку следующему процессору и принимает такую же строку от предыдущего процессора
(см. рис. 12.11). Вторая часть передачи строк выполняется в обратном направлении: процессоры передают свои верхние граничные строки своим предыдущим соседям и принимают переданные строки от следующих процессоров.
Выполнение подобных операций передачи данных в общем виде может быть представлено следующим образом (для краткости рассмотрим только первую часть процедуры обмена):
// передача нижней граничной строки следующему
// процессору и прием передаваемой строки от
// предыдущего процессора if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc); if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc);
(для записи процедур приема-передачи используется близкий к стандарту MPI (см., например, Group, et al. (1994)) формат, где первый и второй параметры представляют пересылаемые данные и их объем, а третий параметр определяет адресат (для операции
Send) или источник (для операции Receive) пересылки данных).
Для передачи данных могут быть задействованы два различных механизма. При первом из них выполнение программ, инициировавших операцию передачи, приостанавливается до полного завершения всех действий по пересылке данных (т.е. до момента получения процессором-адресатом всех передаваемых ему данных). Операции приема-передачи, реализуемые подобным образом, обычно называются
синхронными или блокирующими. Иной подход – асинхронная или неблокирующая передача - может состоять в том, что операции приема-передачи только инициируют процесс пересылки и на этом завершают свое выполнение. В результате программы, не дожидаясь завершения длительных коммуникационных операций, могут продолжать свои вычислительные действия, проверяя по мере необходимости готовность передаваемых данных. Оба эти варианта операций передачи широко используются при организации параллельных вычислений и имеют свои достоинства и свои недостатки.
Синхронные процедуры передачи, как правило, более просты для использования и более надежны; неблокирующие операции могут позволить совместить процессы передачи данных и вычислений, но обычно приводят к повышению сложности программирования. С учетом всего выше сказанного для организации пересылки данных во всех последующих примерf[ будут использоваться операции приема- передачи блокирующего типа.
Приведенная выше последовательность блокирующих операций приема-передачи данных (вначале
Send, затем Receive) приводит к строго последовательной схеме выполнения процесса пересылок строк, т.к. все процессоры одновременно обращаются к операции
Send и переходят в режим ожидания. Первым процессором, который окажется готовым к приему пересылаемых данных, окажется сервер с номером
NP-1. В результате процессор NP-2 выполнит операцию передачи своей граничной строки и перейдет к приему строки от процессора
NP-3 и т.д. Общее количество повторений таких операций равно NP-1.
19
20
Аналогично происходит выполнение и второй части процедуры пересылки граничных строк перед началом обработки строк (см. рис. 12.11).
Последовательный характер рассмотренных операций пересылок данных определяется выбранным способом очередности выполнения. Изменим этот порядок очередности при помощи чередования приема и передачи для процессоров с четными и нечетными номерами:
// передача нижней граничной строки следующему
// процессору и прием передаваемой строки от
// предыдущего процессора if ( ProcNum % 2 == 1 ) { // нечетный процессор if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc); if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc);
} else { // процессор с четным номером if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc); if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc);
}
Данный прием позволяет выполнить все необходимые операции передачи всего за два последовательных шага. На первом шаге все процессоры с нечетными номерами отправляют данные, а процессоры с четными номерами осуществляют прием этих данных. На втором шаге роли процессоров меняются – четные процессоры выполняют
Send, нечетные процессоры исполняют операцию приема
Receive.
Рассмотренные последовательности операций приема-передачи для взаимодействия соседних процессоров широко используются в практике параллельных вычислений. Как результат, во многих базовых библиотеках параллельных программ имеются процедуры для поддержки подобных действий.
Так, в стандарте MPI (см., например, Group, et al. (1994)) предусмотрена операция
Sendrecv, с использованием которой предыдущий фрагмент программного кода может быть записан более кратко:
// передача нижней граничной строки следующему
// процессору и прием передаваемой строки от
// предыдущего процессора
Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);
Реализация подобной объединенной функции Sendrecv обычно осуществляется таким образом, чтобы обеспечить и корректную работу на крайних процессорах, когда не нужно выполнять одну из операций передачи или приема, и организацию чередования процедур передачи на процессорах для ухода от тупиковых ситуаций, и возможности параллельного выполнения всех необходимых пересылок данных.
12.3.3. Коллективные операции обмена информацией
Для завершения круга вопросов, связанных с параллельной реализацией метода сеток на системах с распределенной памятью, осталось рассмотреть способы вычисления общей для всех процессоров погрешности вычислений. Возможный очевидный подход состоит в передаче всех локальных оценок погрешности, полученных на отдельных полосах сетки, на один какой-либо процессор, вычисления на нем максимального значения и последующей рассылки полученного значения всем процессорам системы. Однако такая схема является крайне неэффективной – количество необходимых операций передачи данных определяется числом процессоров и выполнение этих операций может происходить только в последовательном режиме. Между тем, как показывает анализ требуемых коммуникационных действий, выполнение операций сборки и рассылки данных может быть реализовано с использованием рассмотренной в п. 2.5 пособия
каскадной схемы обработки данных. На самом деле, получение максимального значения локальных погрешностей, вычисленных на каждом процессоре, может быть обеспечено, например, путем предварительного нахождения максимальных значений для отдельных пар процессоров (данные вычисления могут выполняться параллельно), затем может быть снова осуществлен попарный поиск максимума среди полученных результатов и т.д. Всего, как полагается по каскадной схеме, необходимо выполнить
log
2
NP параллельных итераций для получения конечного значения (NP – количество процессоров).
Учитывая большую эффективность каскадной схемы для выполнения коллективных операций передачи данных, большинство базовых библиотек параллельных программ содержит процедуры для поддержки подобных действий. Так, в стандарте MPI (см., например, Group, et al. (1994)) предусмотрены операции:
- Reduce(dm,dmax,op,proc) – процедура сборки на процессоре
proc итогового результата dmax среди локальных на каждом процессоре значений
dm с применением операции op,
21
- Broadcast(dmax,proc) – процедура рассылки с процессора
proc значения dmax всем имеющимся процессорам системы.
С учетом перечисленных процедур общая схема вычислений на каждом процессоре может быть представлена в следующем виде:
//Алгоритм 12.8 – уточненный вариант
// Параллельный метод
Гаусса-Зейделя
(распределенная память,
ленточная схема)
// действия, выполняемые на каждом процессоре do {
// обмен граничных строк полос с соседями
Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);
Sendrecv(u[1][*],N+2,PrevProc,u[M+1][*],N+2,NextProc);
// <обработка полосы с оценкой погрешности dm>
// вычисление общей погрешности вычислений dmax
Reduce(dm,dmax,MAX,0);
Broadcast(dmax,0);
} while ( dmax > eps ); // eps - точность решения
(в приведенном алгоритме переменная
dm представляет локальную погрешность вычислений на отдельном процессоре, параметр
MAX задает операцию поиска максимального значения для операции сборки). Следует отметить, что в составе MPI имеется процедура
Allreduce, которая совмещает действия редукции и рассылки данных. Результаты экспериментов для данного варианта параллельных вычислений для метода Гаусса-Зейделя приведены в табл. 12.4.
12.3.4. Организация волны вычислений
Представленные в пп. 1-3 алгоритмы определяют общую схему параллельных вычислений для метода сеток в многопроцессорных системах с распределенной памятью. Далее эта схема может быть конкретизирована реализацией практически всех вариантов методов, рассмотренных для систем с общей памятью (использование дополнительной памяти для схемы Гаусса-Якоби, чередование обработки полос и т.п.). Проработка таких вариантов не привносит каких-либо новых эффектов с точки зрения параллельных вычислений, и их разбор может использоваться как темы заданий для самостоятельных упражнений.
Таблица 12.4
. Результаты экспериментов для систем с распределенной памятью, ленточная схема разделения данных (p=4)
Последовательный метод Гаусса-Зейделя
(алгоритм 6.1)
Параллельный алгоритм 6.8
Параллельный алгоритм с волновой схемой расчета
(см. п. 6.3.4)
Размер сетки
k T
k
T
S
k
T
S
100 210 0,06 210 0,54 0,11 210 1,27 0,05 200 273 0,35 273 0,86 0,41 273 1,37 0,26 300 305 0,92 305 0,92 1,00 305 1,83 0,50 400 318 1,69 318 1,27 1,33 318 2,53 0,67 500 343 2,88 343 1,72 1,68 343 3,26 0,88 600 336 4,04 336 2,16 1,87 336 3,66 1,10 700 344 5,68 344 2,52 2,25 344 4,64 1,22 800 343 7,37 343 3,32 2,22 343 5,65 1,30 900 358 9,94 358 4,12 2,41 358 7,53 1,32 1000 351 11,87 351 4,43 2,68 351 8,10 1,46 2000 367 50,19 367 15,13 3,32 367 27,00 1,86 3000 364 113,17 364 37,96 2,98 364 55,76 2,03
(k – количество итераций, T – время в сек., S – ускорение)
В завершение рассмотрим возможность организации параллельных вычислений, при которых обеспечивалось бы нахождение таких же решений задачи Дирихле, что и при использовании исходного последовательного метода Гаусса-Зейделя. Как отмечалось ранее, такой результат может быть получен за счет организации волновой схемы расчетов. Для образования волны вычислений представим
логически каждую полосу узлов области расчетов в виде набора блоков (размер блоков можно положить, в частности, равным ширине полосы) и организуем обработку полос поблочно в последовательном порядке (см. рис. 12.12). Тогда для полного повторения действий последовательного алгоритма вычисления могут быть начаты только для первого блока первой полосы узлов; после того, как этот блок будет обработан, для вычислений будут готовы уже два блока – блок 2 первой полосы и блок 1 второй полосы (для обработки блока полосы 2 необходимо передать граничную строку узлов первого блока полосы 1). После обработки указанных блоков к вычислениям будут готовы уже 3 блока, и мы получаем знакомый уже процесс волновой обработки данных (результаты экспериментов приведены в табл. 12.4).
П
ро це ссо ры
1 0
2 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 11 3
Рис. 12.12.
Организация волны вычислений при ленточной схеме разделения данных
Интересный момент при организации подобный схемы параллельных вычислений может состоять в попытке совмещения операций пересылки граничных строк и действий по обработке блоков данных.
12.3.5. Блочная схема разделения данных
Ленточная схема разделения данных может быть естественным образом обобщена на блочный способ представления сетки области расчетов (см. рис. 12.9). При этом столь радикальное изменение способа разбиения сетки практически не потребует каких-либо существенных корректировок рассмотренной схемы параллельных вычислений. Основной новый момент при блочном представлении данных состоит в увеличении количества граничных строк на каждом процессоре (для блока их количество становится равным 4), что приводит, соответственно, к большему числу операций передачи данных при обмене граничных строк. Сравнивая затраты на организацию передачи граничных строк, можно отметить, что при ленточной схеме для каждого процессора выполняется 4 операции приема- передачи данных, в каждой из которых пересылается (
N+2) значения. Для блочного же способа происходит 8 операций пересылки и объем каждого сообщения равен (
2
/
+
NP
N
) (
N – количество внутренних узлов сетки,
NP – число процессоров, размер всех блоков предполагается одинаковым). Тем самым, блочная схема представления области расчетов становится оправданной при большом количестве узлов сетки области расчетов, когда увеличение количества коммуникационных операций приводит к снижению затрат на пересылку данных в силу сокращения размеров передаваемых сообщений.
Результаты экспериментов при блочной схеме разделения данных приведены в табл. 12.5.
Таблица 12.5
. Результаты экспериментов для систем с распределенной памятью, блочная схема разделения данных (p=4)
Последовательный метод Гаусса-Зейделя
(алгоритм 6.1)
Параллельный алгоритм с блочной схемой расчета (см. п. 6.3.5)
Параллельный алгоритм 6.9
Размер сетки
k T
k
T
S
k
T
S
100 210 0,06 210 0,71 0,08 210 0,60 0,10 200 273 0,35 273 0,74 0,47 273 1,06 0,33 300 305 0,92 305 1,04 0,88 305 2,01 0,46 400 318 1,69 318 1,44 1,18 318 2,63 0,64 500 343 2,88 343 1,91 1,51 343 3,60 0,80 600 336 4,04 336 2,39 1,69 336 4,63 0,87 700 344 5,68 344 2,96 1,92 344 5,81 0,98 800 343 7,37 343 3,58 2,06 343 7,65 0,96 900 358 9,94 358 4,50 2,21 358 9,57 1,04 22
П
ро це ссо ры
1 0
2 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 11 3
Рис. 12.12.
Организация волны вычислений при ленточной схеме разделения данных
Интересный момент при организации подобный схемы параллельных вычислений может состоять в попытке совмещения операций пересылки граничных строк и действий по обработке блоков данных.
12.3.5. Блочная схема разделения данных
Ленточная схема разделения данных может быть естественным образом обобщена на блочный способ представления сетки области расчетов (см. рис. 12.9). При этом столь радикальное изменение способа разбиения сетки практически не потребует каких-либо существенных корректировок рассмотренной схемы параллельных вычислений. Основной новый момент при блочном представлении данных состоит в увеличении количества граничных строк на каждом процессоре (для блока их количество становится равным 4), что приводит, соответственно, к большему числу операций передачи данных при обмене граничных строк. Сравнивая затраты на организацию передачи граничных строк, можно отметить, что при ленточной схеме для каждого процессора выполняется 4 операции приема- передачи данных, в каждой из которых пересылается (
N+2) значения. Для блочного же способа происходит 8 операций пересылки и объем каждого сообщения равен (
2
/
+
NP
N
) (
N – количество внутренних узлов сетки,
NP – число процессоров, размер всех блоков предполагается одинаковым). Тем самым, блочная схема представления области расчетов становится оправданной при большом количестве узлов сетки области расчетов, когда увеличение количества коммуникационных операций приводит к снижению затрат на пересылку данных в силу сокращения размеров передаваемых сообщений.
Результаты экспериментов при блочной схеме разделения данных приведены в табл. 12.5.
Таблица 12.5
. Результаты экспериментов для систем с распределенной памятью, блочная схема разделения данных (p=4)
Последовательный метод Гаусса-Зейделя
(алгоритм 6.1)
Параллельный алгоритм с блочной схемой расчета (см. п. 6.3.5)
Параллельный алгоритм 6.9
Размер сетки
k T
k
T
S
k
T
S
100 210 0,06 210 0,71 0,08 210 0,60 0,10 200 273 0,35 273 0,74 0,47 273 1,06 0,33 300 305 0,92 305 1,04 0,88 305 2,01 0,46 400 318 1,69 318 1,44 1,18 318 2,63 0,64 500 343 2,88 343 1,91 1,51 343 3,60 0,80 600 336 4,04 336 2,39 1,69 336 4,63 0,87 700 344 5,68 344 2,96 1,92 344 5,81 0,98 800 343 7,37 343 3,58 2,06 343 7,65 0,96 900 358 9,94 358 4,50 2,21 358 9,57 1,04 22
1000 351 11,87 351 4,90 2,42 351 11,16 1,06 2000 367 50,19 367 16,07 3,12 367 39,49 1,27 3000 364 113,17 364 39,25 2,88 364 85,72 1,32
(k – количество итераций, T – время в сек., S – ускорение)
При блочном представлении сетки может быть реализован также и волновой метод выполнения расчетов (см. рис. 12.13). Пусть процессоры образуют прямоугольную решетку размером
(
NBxNB
NP
NB
=
) и процессоры пронумерованы от
0 слева направо по строкам решетки.
Общая схема параллельных вычислений в этом случае имеет вид:
//Алгоритм 12.9
// Параллельный метод
Гаусса-Зейделя
(распределенная память,
блочная схема)
// волновая схема расчетов
// действия, выполняемые на каждом процессоре do {
// получение граничных узлов if ( ProcNum / NB != 0 ) { // строка не нулевая
// получение данных от верхнего процессора
Receive(u[0][*],M+2,TopProc); // верхняя строка
Receive(dmax,1,TopProc); // погрешность
} if ( ProcNum % NB != 0 ) { // столбец не нулевой
// получение данных от левого процессора
Receive(u[*][0],M+2,LeftProc); // левый столбец
Receive(dm,1,LeftProc); // погрешность
If ( dm > dmax ) dmax = dm;
}
// <обработка блока с оценкой погрешности dmax>
// пересылка граничных узлов if ( ProcNum / NB != NB-1 ) { // строка решетки не
// последняя
// пересылка данных нижнему процессору
Send(u[M+1][*],M+2,DownProc); // нижняя строка
Send(dmax,1,DownProc); // погрешность
} if ( ProcNum % NB != NB-1 ) { // столбец решетки
// не последний
// пересылка данных правому процессору
Send(u[*][M+1],M+2,RightProc); // правый столбец
Send(dmax,1, RightProc); // погрешность
}
// синхронизация и рассылка погрешности dmax
Barrier();
Broadcast(dmax,NP-1);
} while ( dmax > eps ); // eps - точность решения
Алгоритм 12.9.
Блочная схема разделения данных
(в приведенном алгоритме функция
Barrier() представляет операцию коллективной синхронизации, которая завершает свое выполнение только в тот момент, когда все процессоры осуществят вызов этой процедуры).
Следует обратить внимание, что при реализации алгоритма нужно обеспечить, чтобы в начальный момент времени все процессоры (кроме процессора с нулевым номером) оказались в состоянии ожидания своих граничных узлов (верхней строки и левого столбца). Вычисления должен начинать процессор с левым верхним блоком, после завершения обработки которого обновленные значения правого столбца и нижней строки блока необходимо переправить правому и нижнему процессорам решетки соответственно. Данные действия обеспечат снятие блокировки процессоров второй диагонали процессорной решётки (ситуация слева на рис. 12.13) и т.д.
Анализ эффективности организации волновых вычислений в системах с распределенной памятью
(см. табл. 12.5) показывает значительное снижение полезной вычислительной нагрузки для процессоров, которые занимаются обработкой данных только в моменты, когда их блоки попадают во фронт волны вычислений. При этом балансировка (перераспределение) нагрузки является крайне затруднительной,
23