лекции (MPI), страница 10

Учебное пособие. – М.-:ИНФРА-М, 2013.158Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаПостановка задачи.Разностная схема.Численный подход к решению задачи (1) основан назамене производных соответствующими конечнымиразностями (2).ui 1, j ,k  2ui , j ,k  ui 1, j ,kh2ui , j 1,k  2ui , j ,k  ui , j 1,kh2ui , j ,k 1  2ui , j ,k  ui , j ,k 1h2 0, (2)где h  0 - шаг сетки, u i , j ,k - значение функции u(x, y, z) в точкеx  xi  ih, i  0, M  1, y  y j  jh, j  0, N  1, z  z k  kh, h  0, L  1,где M, N, L - количество внутренних узлов по каждой координатев области D.Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаМетод Якоби. итерационный метод Якоби (3).n 1i 1, j , kun 1i 1, j , kun 1i , j 1, kun 1i , j 1, kuni , j ,k (uuni , j ,k g i , j ,k , ( x, y, z )  D , n  1,2,..un 1i , j , k 10где n - номер итерации.Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.Поповаun 1i , j , k 1)/6(3)Уравнение Лапласа (2D)u u 2 02xy22x, y  [0,1](1)Краевые условия:u ( x,0 )  sin (x)u ( x,1)  sin (x)e0x1x0x1u (0, y )  u (1, y )  00y1(2)Аналитическое решение:u( x, y)  sin(x)e xyx, y  [0,1]Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.Попова(3)Дискретизация уравнения Лапласаuin, 1j uin1,j  uin1,j  ui,jn 1  ui,jn 14i  1,2, ,m; j  1,2, ,m(4)где n и n+1 текущий и следующий шаг,ui,jn  u n(xi ,y j )i  0,1,2, ,m  1; j  0,1,2, ,m  1 u n(ix, jy )Для простотыx  y 1m1Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.Попова(5)Вычислительная областьu(x,1)  sin(x)e xy, jx, iu(1,y)  0u(0,y)  0u ( x,0)  sin (x)uin, j 1 uin1,j  uin1,j  ui,jn 1  ui,jn 14i  1,2, ,m; j  1,2, ,mСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.Попова5-точечный шаблонuin, j 1 uin1,j  uin1,j  ui,jn 1  ui,jn 1xx o x4xвнутренняя область, накоторой ищется решениеуравнения(i, j)граничная область.Голубые клетки – неоднородныеграничные условия,Зеленые - однородныеСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.Поповаxx o xxМетод Якоби3.Задать начальные значения u во всех внутренних точках (i,j) вмомент времени n=0.Используя 5-точечный шаблон, вычислить значения воn 1внутренних точках ui , j (i,j).Завершить процесс, если заданная точность достигнута.4.Иначе:5.Перейти на шаг 2.1.2.uin, j  uin, j 1для всех внутренних точек.Это очень простая схема.

Медленно сходится, поэтому не используетсядля решения реальных задач.Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаРешение (линии уровня)Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаМетод последовательной верхнейрелаксации (Successive Over Relaxation)1.2.3.4.5.6.7.Определяем начальное значение u во всехвнутренних точках (i,j).Определяем n (0  ωn  2)'uИспользуя 5-точечный шаблон вычисляем i , j во всехвнутренних точках (i,j).uin, j 1   nui', j  (1   n )uin, jВычисляемЗавершаем процесс, если точность достигнута, иначеОбновляем: uin, j  uin, j 1  i, jПереход на пункт 2.На шаге 3 вычисляем u‘, используя u вмомент n по формуле (4)Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаМетод SOR.

Выбор011   2 / 2n  121   1 / 4121   q 1 / 4for n  0for n  1for n  2for n  q  22  - спектральн ый радиусгде   1   2m  1 Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаRed-Black SORУчитывая 5-точечный шаблон,решение в черных клетках зависят от4-ех красных клеток.Соответственно, красные клеткизависят только от 4-ех черныхклеток. Параллельный алгоритм:1.Вычисляем u в черных клетках вмомент времени n+1 используя u,вычисленные в красных клетках вмомент времени n.2.Вычисляем u в красных клетках вмомент времени n+1, используя uв черных клетках, вычисленныедля n+1.3.xx o xxxx o xx XПовторяем шаги 1 и 2 пока небудет достигнута точность.Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаПорядок выполнения шагов 1 и 2может быть произвольнымxx Oo xXxПараллельная реализация1D Domain Decomposition2D Domain DecompositionПроцесс 3Процесс 2Процесс 3Процесс 2Процесс 1Процесс 0Процесс 0Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаПроцесс 1ИТОГОВОЕ ЗАДАНИЕ.Разработать параллельную программу сиспользованием технологии MPI, реализующуюрешение задачи Дирихле методом SOR.Провести исследование эффективностиразработанной программы на системе Blue Gene/P.Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.Попова.