Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Лекция 13. Параллельные методы решения дифференциальных уравнений в частных производных Образовательный комплекс Введение в методы параллельного программирования Гергель В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 2 из 69 Постановка задачи Методы решения дифференциальных уравнений в частных производных Организация параллельных вычислений для систем с общей памятью –Проблема блокировки при взаимоисключении –Проблема неоднозначности вычислений в параллельных программах –Состязание потоков –Проблема взаимоблокировки –Разрешение тупиков –Исключение неоднозначности вычислений –Волновые схемы параллельных вычислений –Блочное представление данных –Балансировка вычислительной нагрузки процессоров Содержание…

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 3 из 69 Организация параллельных вычислений для систем с распределенной памятью –Разделение данных –Ленточная схема разделения данных –Параллельное выполнение операций передачи данных –Коллективные операции обмена информацией –Блочная схема разделения данных –Вычислительный конвейер (множественная волна) –Операции передачи данных Заключение Содержание

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 4 из 69 Введение Дифференциальные уравнения в частных производных широко используется при разработке моделей в самых разных областях науки и техники Анализ математических моделей, построенных на основе дифференциальных уравнений, обеспечивается при помощи приближенных численных методов решения Объем выполняемых при этом вычислений является значительным. Проблематика численного решения дифференциальных уравнений в частных производных является областью интенсивных исследований

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 5 из 69 Постановка задачи В качестве учебного примера рассматривается проблема численного решения задачи Дирихле для уравнения Пуассона

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 6 из 69 Последовательные методы решения Метод конечных разностей Область решения представляется в виде дискретного набора (сетки) точек (узлов) Последовательность решений равномерно сходится к решению задачи Дирихле, а погрешность решения имеет порядок h 2

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 7 из 69 Итерационные схемы Метод Гаусса-Зейделя Трудоемкость T = kmN 2 N - число узлов по каждой координате m - число операций на узел k - количество итераций

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 8 из 69 Алгоритм 1: Последовательный алгоритм Гаусса-Зейделя // Алгоритм 12.1 do { dmax = 0; // максимальное изменение значений u for ( i=1; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 9 из 69 Пример расчетов N = 100 = 0.1 k = 210

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 10 из 69 Организация параллельных вычислений для систем с общей памятью… Возможный способ получение ПО для параллельных вычислений – переработка существующих последовательных программ Такая переработка выполняется или автоматически компилятором или непосредственно программистом Второй подход является преобладающим, т.к. возможности автоматического построения параллельных программ достаточно ограничены Использование новых алгоритмических языков параллельного программирования приводит к необходимости значительной переработки существующего программного обеспечения

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 11 из 69 Организация параллельных вычислений для систем с общей памятью Возможный решение проблемы – использование тех или иных внеязыковых средств языка программирования – например, в виде директив или комментариев, которые обрабатываются специальным препроцессором до начала компиляции программы Директивы дают указания на возможные способы распараллеливания программы, при этом исходный текст программы остается неизменным (!!!) Препроцессор при обработке текста программы заменяет директивы параллелизма на некоторый дополнительный программный код (как правило, в виде обращений к процедурам какой-либо параллельной библиотеки) При отсутствии препроцессора компилятор построит исходный последовательный программный код (!!!) Единство программного кода для последовательных и параллельных вычислений снижает сложность развития и сопровождения программ Определение параллелизма при помощи директив позволяет осуществлять поэтапную разработку параллельных программ

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 12 из 69 Технология OpenMP Для организации параллельных вычислений программистом в программу добавляются указания в виде директив (C/C++) или комментариев (Fortran) Вилочный (fork-join) –пульсирующий - параллелизм - выделение в программе параллельных областей В результате такого подхода программа представляется в виде набора последовательных (однопотоковых) и параллельных (многопотоковых) участков программного кода

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 13 из 69 Алгоритм 1.2: Первый вариант параллельного алгоритма Гаусса-Зейделя //Алгоритм 12.2 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

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 14 из 69 Результаты вычислительных экспериментов Размер сетки Последовательный метод Гаусса-Зейделя (алгоритм 12.1) Параллельный алгоритм 12.2 k T kTS ,062101,970, , ,220, , ,090, , ,200, , ,840, , ,380, , ,300, , ,700, , ,030, , ,160, , ,840, , ,530,07

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 15 из 69 Оценка подхода Разработанный параллельный алгоритм обеспечивает решение поставленной задачи Может быть задействовано до N 2 процессоров. Чрезмерно высокая синхронизация параллельных участков программы Слабая загрузка процессоров Низкая эффективность

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 16 из 69 Проблема: блокировки при взаимоисключении Каждый параллельный поток после усреднения значений должен проверить значение величины dmax Разрешение на использование переменной получает один поток, другие в это время блокируются. После освобождения общей переменной управление может получить следующий поток и т.д.

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 17 из 69 Проблема: блокировки при взаимоисключении В результате многопотоковая параллельная программа превращается в последовательно выполняемый код

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 18 из 69 Алгоритм 1.3: Второй вариант параллельного алгоритма Гаусса-Зейделя //Алгоритм 12.3 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

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 19 из 69 Результаты вычислительных экспериментов Размер сетки Последовательный метод Гаусса-Зейделя (алгоритм 12.1) Параллельный алгоритм 12.2 Параллельный алгоритм 12.3 k T kTSkTS ,062101,970,032100,032, , ,220,032730,142, , ,090,033050,362, , ,200,073180,645, , ,840,073431,065, , ,380,073361,505, , ,300,073442,425, , ,700,073438,082, , ,030, ,031, , ,160, ,691, , ,840, ,631, , ,530, ,661,89

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 20 из 69 Оценка подхода Существенное снижение обращений к общей переменной Снижение показателя максимально возможного параллелизма до N Как результат существенное снижению затрат на синхронизацию потоков и уменьшению проявления эффекта сериализации вычислений. Лучшие показатели ускорения

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 21 из 69 Возможность неоднозначности вычислений в параллельных программах При вычислениях последовательность обработки данных может различаться при разных запусках программы Взаиморасположение потоков по области расчетов может быть различным: одни потоки могут опережать другие и, обратно, часть потоков могут отставать Причина - состязанием потоков (race condition) Временная динамика выполнения параллельных потоков не должна учитываться при разработке параллельных алгоритмов и программ

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 22 из 69 Состязание потоков Выход: захват и блокировка используемых строк

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 23 из 69 Проблема: взаимоблокировка Потоки блокируют сначала строки 1 и 2 и только затем переходят к блокировке оставшихся строк - Тупик (!!!) Для ограничения доступа к узлам сетки можно ввести набор семафоров 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]);

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 24 из 69 Разрешение тупиков Решение: соблюдение строгой последовательности блокировки строк // поток обрабатывает i строку сетки omp_set_lock(row_lock[i+1]); omp_set_lock(row_lock[i]); omp_set_lock(row_lock[i-1]); // omp_unset_lock(row_lock[i+1]); omp_unset_lock(row_lock[i]); omp_unset_lock(row_lock[i-1]); Однозначность вычислений не обеспечивается

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 25 из 69 Исключение неоднозначности вычислений Для исключения неоднозначности вычислений применяют способ, который состоит в разделение места хранения результатов вычислений на предыдущей и текущей итерациях метода сеток (метод Гаусса-Якоби)

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 26 из 69 Алгоритм 1.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

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 27 из 69 Результаты вычислительных экспериментов Размер сетки Последовательный метод Гаусса- Якоби (алгоритм 12.4) Параллельный метод, разработанный по аналогии с алгоритмом 12.3 k T kTS , ,731, , ,002, , ,007, , ,258, , ,956, , ,951, , ,191, , ,731, , ,091, , ,601, , ,451, , ,131,91

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 28 из 69 Оценка подхода Однозначность вычислений Использование дополнительной памяти Меньшая скорость сходимости Возможный иной способ устранения взаимозависимости параллельных потоков состоит в использовании схемы чередования обработки строк, при которой выполнение каждой итерации подразделяется на два последовательных этапа: На первом этапе обрабатываются строки только с четными номерами, На втором этапе - строки с нечетными номерами

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 29 из 69 Схема чередования обработки строк

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 30 из 69 Оценка подхода Не требуется дополнительной памяти Алгоритм обеспечивает однозначность вычислений, но не совпадающие с результатами последовательных расчетов Меньшая скорость сходимости Возможность повышения эффективности расчетов

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 31 из 69 Оценка подхода Метод Гаусса-Якоби Схема чередования обработки строк Использование дополнительной памяти Не требуется дополнительной памяти Алгоритмы обеспечивают однозначность вычислений, но получаемые решения могут не совпадать с результатами последовательных расчетов Вычислительные схемы имеют меньшую скорость сходимости, чем исходный вариант метода Гаусса- Зейделя

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 32 из 69 Волновые схемы параллельных вычислений Рассмотрим параллельные алгоритмы обладающими следующими свойствами: –выполняемые вычислительные действия, что и исходный последовательный метод –полученные решения совпадали с решением исходной вычислительной задачи. Один из таких методов - метод волновой обработки данных Вычислительная схема состоит в выполнение итерации метода сеток которые разбиваются на последовательность шагов

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 33 из 69 Волновые схемы параллельных вычислений На каждом шаге к вычислениям окажутся подготовленными узлы вспомогательной диагонали сетки с номером, определяемом номером этапа

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 34 из 69 Алгоритм 1.5: Параллельный алгоритм реализующий волновую схему вычислений… //Алгоритм 12.5 omp_lock_t dmax_lock; omp_init_lock(dmax_lock); do { dmax = 0; // максимальное изменение значений u // нарастание волны ( nx – размер волны) for ( nx=1; nx

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 35 из 69 Алгоритм 1.5: Параллельный алгоритм реализующий волновую схему вычислений // затухание волны for ( nx=N-1; nx>0; nx-- ) { #pragma omp parallel for shared(u,nx,dm) private(i,j,temp,d) for ( i=N-nx+1; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 36 из 69 Волновые схемы параллельных вычислений Последняя часть расчетов для определения максимальной погрешности неэффективна из-за высоких затрат на синхронизацию Фрагментирование (chucking) - уменьшения синхронизации за счет увеличения размера последовательных участков Возможный вариант реализации такого подхода может состоять в следующем: chunk = 200; // размер последовательного участка #pragma omp parallel for shared(n,dm,dmax)private(i,d) for ( i=1; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 37 из 69 Результаты экспериментов

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 38 из 69 Оценка подхода Неэффективность использования кэша Для повышения быстродействия вычисления за счет кэша необходимо следующее: –выполняемые вычисления использовали одни и те же данные многократно (локальность обработки данных), –выполняемые вычисления осуществляли доступ к элементам памяти с последовательно возрастающими адресами (последовательность доступа) Для эффективного использования кэша в качестве распределяемых между процессорами действий процедуру обработки некоторой прямоугольной подобласти (блока) сетки области расчетов

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 39 из 69 Блочное представление данных

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 40 из 69 Алгоритм 1.6: Блочный подход к методу волновой обработки данных //Алгоритм 12.6 do { // нарастание волны (размер волны равен nx+1) for ( nx=0; nx

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 41 из 69 Результаты вычислительных экспериментов Размер сетки Последовательный метод Гаусса-Зейделя (алгоритм 12.1) Параллельный алгоритм 12.5 Параллельный алгоритм 12.6 K T kTSkTS ,062100,300,212100,160, ,342730,860,402730,590, ,883051,630,543051,530, ,783182,501,513182,361, ,003433,531,703434,031, ,813365,201,693365,341, ,113448,131, ,001, , ,081, ,641, , ,981, ,591, , ,271, ,301, , ,081, ,721, , ,361, ,891,72

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 42 из 69 Оценка подхода Обработка блоков выполняется на разных процессорах и блоки не пересекаются по данным, тогда будут отсутствовать накладные расходы для обеспечения однозначности (когерентности) кэшей разных процессоров. Возможность простоев процессоров Возможность повышения эффективности расчетов

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 43 из 69 Балансировка вычислительной нагрузки процессоров Размер блока определяет степень разбиения (granularity) вычислений для распараллеливания Подбирая значение степени разбиения можно управлять эффективностью параллельных вычислений Для обеспечения равномерности (балансировки) загрузки процессоров - вычислительные действия организуются в виде очереди заданий В ходе вычислений освободившийся процессор может запросить для себя работу из этой очереди Очередь заданий является общим подходом организации параллельных вычислений для систем с общей памятью

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 44 из 69 Алгоритм 1.7:Общая схема балансировки вычислений с использованием очереди //Алгоритм 12.7 // // взять блок из очереди (если очередь не пуста) while ( (pBlock=GetBlock()) != NULL ) { // // отметка готовности соседних блоков omp_set_lock(pBlock->pNext.Lock); // сосед справа pBlock->pNext.Count++; if ( pBlock->pNext.Count == 2 ) PutBlock(pBlock->pNext); omp_unset_lock(pBlock->pNext.Lock); omp_set_lock(pBlock->pDown.Lock); // сосед снизу pBlock->pDown.Count++; if ( pBlock->pDown.Count == 2 ) PutBlock(pBlock->pDown); omp_unset_lock(pBlock->pDown.Lock); } // завершение вычислений, т.к. очередь пуста

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 45 из 69 Организация параллельных вычислений для систем с распределенной памятью Многие проблемы параллельного программирования (состязание вычислений, тупики, сериализация) являются общими для систем с общей и распределенной памятью Взаимодействие параллельных участков программы на разных процессорах может быть обеспечено только при помощи передачи сообщений (message passing)

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 46 из 69 Разделение данных В рассматриваемой учебной задаче по решению задачи Дирихле возможны два различных способа разделения данных: –одномерная или ленточная схема разбиения вычислительной сетки, –двухмерное или блочное разбиение вычислительной сетки. При ленточном разбиении область расчетов делится на горизонтальные или вертикальные полосы Число полос определяется количеством процессоров, размер полос обычно является одинаковым Полосы для обработки распределяются между процессорам

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 47 из 69 Ленточная схема разделения данных Важно отметить следующее: –процессор, выполняющий обработку какой-либо полосы, должны быть продублированы граничные строки предшествующей и следующей полос вычислительной сетки, –дублирование граничных строк должно осуществляться перед началом выполнения каждой очередной итерации метода сеток

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 48 из 69 Алгоритм 1.8: Схема Гаусса-Зейделя, ленточное разделение данных //Алгоритм 12.8 // схема Гаусса-Зейделя, ленточное разделение данных // действия, выполняемые на каждом процессоре do { // // } while ( dmax > eps ); // eps - точность решения Программа

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 49 из 69 Схема обмена данными между процессорами На первом этапе каждый процессор передает свою нижнюю граничную строку следующему процессору и принимает такую же строку от предыдущего процессора. На втором этапе каждый процессор передает свою верхнюю граничную строку своим предыдущим соседям и принимает переданные строки от следующих процессоров.

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 50 из 69 Схема обмена данными между процессорами Выполнение операций передачи данных в общем виде может быть представлено следующим образом: // передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc); if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc); Для передачи данных могут быть задействованы два различных механизма – блокирующая и неблокирующая передача Оба эти варианта операций передачи широко используются при организации параллельных вычислений и имеют свои достоинства и свои недостатки

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 51 из 69 Параллельное выполнение операций передачи данных На первом шаге все процессоры с нечетными номерами отправляют данные, а процессоры с четными номерами осуществляют прием этих данных На втором шаге роли процессоров меняются – четные процессоры выполняют Send, нечетные процессоры исполняют операцию приема Receive // передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора 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); }

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 52 из 69 Коллективные операции обмена информацией Выполнение операций сборки и рассылки данных может быть реализовано с использованием каскадной схемы обработки данных Получение максимального значения локальных погрешностей, вычисленных на каждом процессоре –предварительного нахождения максимальных значений для отдельных пар процессоров (данные вычисления могут выполняться параллельно), –попарный поиск максимума среди полученных результатов и т.д. Общее количество параллельных итераций по каскадной схеме log 2 р для получения конечного значения (р – количество процессоров).

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 53 из 69 Алгоритм 1.8: Уточненный вариант Гаусса-Зейделя, ленточное разделение данных //Алгоритм 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 ); // // вычисление общей погрешности вычислений dmax Reduce(dm,dmax,MAX,0); Broadcast(dmax,0); } while ( dmax > eps ); // eps - точность решения

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 54 из 69 Результаты вычислительных экспериментов Размер сетки Последовательный метод Гаусса-Зейделя Параллельный алгоритм 1.8 k t ktS ,062100,54 0, ,352730,86 0, ,923050,92 1, ,693181,27 1, ,883431,72 1, ,043362,16 1, ,683442,52 2, ,373433,32 2, ,943584,12 2, ,873514,43 2, , ,13 3, , ,96 2,98

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 55 из 69 Волновые вычисления при ленточной схеме разделения данных Для образования волны вычислений представим логически каждую полосу узлов области расчетов в виде набора блоков и организуем обработку полос поблочно в последовательном порядке

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 56 из 69 Блочная схема разделения данных При блочном представлении данных увеличивается количество граничных строк на каждом процессоре, что приводит, к большему числу операций передачи данных при обмене граничных строк Блочная схема представления области расчетов становится оправданной при большом количество узлов сетки области расчетов

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 57 из 69 Блочная схема разделения данных //Алгоритм 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; }

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 58 из 69 Блочная схема разделения данных // // пересылка граничных узлов 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 - точность решения Программа

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 59 из 69 Вычислительный конвейер (множественная волна) Эффективность организации волновых вычислений снижается для процессоров, которые занимаются обработкой данных только в моменты, когда их блоки попадают во фронт волны вычислений Для улучшения балансировки вычислительной нагрузки между процессорами применяют организацию множественной волны вычислений Идея организации состоит в следующем - процессоры после отработки волны текущей итерации расчетов могут приступить к выполнению волны следующей итерации метода сеток

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 60 из 69 Вычислительный конвейер (множественная волна)

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 61 из 69 Операции передачи данных

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 62 из 69 Рассмотрены способы построения параллельных алгоритмов для систем с общей и разделяемой памяти на примере решения дифференциальных уравнений в частных производных При изложении организации параллельных вычислений для систем с общей памятью основное внимание уделяется технологии OpenMP, также приводятся проблемы, возникающие при применении этой технологии и решения этих проблем При изложении организации параллельных вычислений для систем с распределенной памятью основное внимание уделяется разделению данных и обмену информацией между процессорами Заключение…

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 63 из 69 Рассматриваются различные механизмы приема - передачи данных, такие как синхронные и асинхронные Теоретические оценки позволяют достаточно точно определить показатели эффективности параллельных вычислений Заключение

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 64 из 69 Как повысить эффективность методов волновой обработки данных? Как очередь заданий позволяет балансировать нагрузку процессорам? Какие проблемы приходится решать при организации параллельных вычислений на системах с распределенной памяти? Какие основные операции передачи данных используются в параллельных методах решения задачи Дирихле ? Вопросы для обсуждения

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 65 из 69 Выполните реализацию параллельного алгоритма реализующий волновую схему вычислений и параллельный метод, в котором реализуется блочный подход к методу волновой обработки данных Постройте теоретические оценки времени работы этих алгоритмов с учетом параметров используемой вычислительной системы Проведите вычислительные эксперименты. Сравните результаты реальных экспериментов с полученными теоретическими оценками Темы заданий для самостоятельной работы

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 66 из 69 Гергель В.П. Теория и практика параллельных вычислений. – М.: Интернет- Университет, БИНОМ. Лаборатория знаний, Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем – СПб.: БХВ-Петербург,2002. Березин И.С., Жидков И.П. Методы вычислений.-М.:Наука,1966 Тихонов А.Н., Самарский А.А. Уравнения математической физики. – М.: Наука,1977 Pfister, G.P. In Search of Clusters. Prentice Hall PTR, Upper Saddle River, NJ Kumar V., Grama, A., Gupta, A., Karypis, G. Introduction to Parallel Computing. - The Benjamin/Cummings Publishing Company, Inc., (2nd edn., 2003) Quinn, M. J. Parallel Programming in C with MPI and OpenMP. – New York, NY: McGraw-Hill, Roosta, S.H. Parallel Processing and Parallel Algorithms: Theory and Computation. Springer-Verlag,NY Литература

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 67 из 69 Следующая тема Параллельные методы глобальной оптимизации

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 68 из 69 Гергель В.П., профессор, д.т.н., руководитель Гришагин В.А., доцент, к.ф.м.н. Сысоев А.В., ассистент (раздел 1) Лабутин Д.Ю., ассистент (система ПараЛаб) Абросимова О.Н., ассистент (раздел 10) Гергель А.В., аспирант (раздел 12) Лабутина А.А., магистр (разделы 7,8,9, система ПараЛаб) Сенин А.В. (раздел 11) Авторский коллектив

Н.Новгород, 2005 г. Основы параллельных вычислений: Решение дифференциальных уравнений в частных производных © Гергель В.П. 69 из 69 Целью проекта является создание образовательного комплекса "Многопроцессорные вычислительные системы и параллельное программирование", обеспечивающий рассмотрение вопросов параллельных вычислений, предусматриваемых рекомендациями Computing Curricula 2001 Международных организаций IEEE-CS и ACM. Данный образовательный комплекс может быть использован для обучения на начальном этапе подготовки специалистов в области информатики, вычислительной техники и информационных технологий. Образовательный комплекс включает учебный курс "Введение в методы параллельного программирования" и лабораторный практикум "Методы и технологии разработки параллельных программ", что позволяет органично сочетать фундаментальное образование в области программирования и практическое обучение методам разработки масштабного программного обеспечения для решения сложных вычислительно-трудоемких задач на высокопроизводительных вычислительных системах. Проект выполнялся в Нижегородском государственном университете им. Н.И. Лобачевского на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики ( Выполнение проекта осуществлялось при поддержке компании Microsoft. О проекте