Самарский государственный технический университет филиал в г. Сызрани
Электротехнический Факультет
Дисциплина
Методы параллельных
вычислений
Лекция 14.
Параллельные методы решения дифференциальных уравнений в частных производных
Тараканов А.В., доцент, к.п.н. Кафедра Информатики и систем управления
Содержание…
Постановка задачи
Методы решения дифференциальных уравнений в частных производных
Организация параллельных вычислений для систем с общей памятью
–Проблема блокировки при взаимоисключении
–Проблема неоднозначности вычислений в параллельных программах
–Состязание потоков
–Проблема взаимоблокировки
–Разрешение тупиков
–Исключение неоднозначности вычислений
–Волновые схемы параллельных вычислений
–Блочное представление данных
–Балансировка вычислительной нагрузки процессоров
2 из 66
Содержание
Организация параллельных вычислений для систем с распределенной памятью
–Разделение данных
–Ленточная схема разделения данных
–Параллельное выполнение операций передачи данных
–Коллективные операции обмена информацией
–Блочная схема разделения данных
–Вычислительный конвейер (множественная волна)
–Операции передачи данных
Заключение
3 из 66
Введение
Дифференциальные уравнения в частных производных широко используется при разработке моделей в самых разных областях науки и техники
Анализ математических моделей, построенных на основе дифференциальных уравнений, обеспечивается при помощи приближенных численных методов решения
Объем выполняемых при этом вычислений является значительным.
Проблематика численного решения дифференциальных уравнений в частных производных является областью интенсивных исследований
4 из 66
Постановка задачи
Вкачестве учебного примера рассматривается проблема численного решения задачи Дирихле для уравнения Пуассона
|
2 |
u |
|
2 |
u |
|
|
|
|
|
|
|
|
f (x, y), |
(x, y) D, |
||||
x2 |
y2 |
||||||||
|
|
|
|
|
|||||
|
u(x, y) g(x, y), |
0 |
, |
||||||
|
(x, y) D |
||||||||
D {(x, y) D : 0 x, y 1}
5 из 66
Последовательные методы решения
Метод конечных разностей
Область решения представляется в виде дискретного набора (сетки) точек (узлов)
Последовательность решений равномерно сходится к
решению задачи Дирихле, а погрешность решения имеет порядок h2
Dh {(xi , y j ) : xi ih, yi jh, 0 i, j N 1, |
||||||||
|
|
h 1/(N 1), |
|
|
|
|
||
|
|
|
|
|
|
|||
|
ui 1, j ui 1, j ui, j 1 ui, j 1 4uij |
fij |
|
|
||||
|
|
|
h2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
u |
0.25(u |
u |
u |
u |
h2 f |
ij |
) |
|
|
ij |
i 1, j |
i 1, j |
i, j 1 |
i, j 1 |
|
|
|
6 из 66
Итерационные схемы
Метод Гаусса-Зейделя
uk 0.25(uk |
uk 1 |
uk |
uk 1 |
h2 f |
ij |
) |
|
ij |
i 1, j |
i 1, j |
i , j 1 |
i , j 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Трудоемкость |
|
|
|
|
|
(i,j-1) |
|
|
|
|
T = kmN2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N - число узлов по каждой |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
(i,j) |
|
|
|
|
|
|
|
|
(i-1,j) |
(i+1,j) |
|
|
|
координате |
||
|
|
|
|
(i,j+1) |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
m - число операций на узел k - количество итераций
7 из 66
Алгоритм 1: Последовательный алгоритм Гаусса-Зейделя
// Алгоритм 12.1 do {
dmax = 0; // максимальное изменение значений u for ( i=1; i<N+1; i++ )
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]);
dm = fabs(temp-u[i][j]); if ( dmax < dm ) dmax = dm;
}
} while ( dmax > eps );
Программа
8 из 66
Пример расчетов
f (x, y) 0, |
(x, y) D, |
||
|
100 |
200x, |
y 0, |
|
|||
|
100 |
200y, |
x 0, |
|
|||
|
100 |
200x, |
y 1, |
|
100 |
200y, |
x 1, |
|
|||
N = 100= 0.1 k = 210
9 из 66
Организация параллельных вычислений для систем с общей памятью…
Возможный способ получение ПО для параллельных вычислений – переработка существующих последовательных программ
Такая переработка выполняется или автоматически компилятором или непосредственно программистом
Второй подход является преобладающим, т.к. возможности автоматического построения параллельных программ достаточно ограничены
Использование новых алгоритмических языков параллельного программирования приводит к необходимости значительной переработки существующего программного обеспечения
10 из 66