- •Моделирование и анализ параллельных вычислений.
- •Модель вычислений в виде графа "операции – операнды".
- •Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).
- •Определение времени выполнения параллельного алгоритма.
- •Правила разработки алгоритмов.
- •Программирование параллельных алгоритмов.
- •Технология mpi.
- •Введение в библиотеку mpich.
- •Структура параллельной программы с использованием mpi:
- •Передача/прием сообщений между отдельными процессами.
- •Использование модульной структуры.
- •Определение времени выполнения программ.
- •Контроль выполнения программ.
- •Передача данных от одного процесса всем процессам программы.
- •Передача данных от всех процессов одному процессу. Операция редукции.
- •Пример коллективного вызова (без обмена)- коллективная синхронизация.
- •Аварийное завершение параллельной программы
- •Оценка коммуникационных затрат для кластерных систем.
- •Режимы передачи данных mpi.
- •Организация неблокирующих обменов данными между процессами.
- •Одновременное выполнение передачи и приема.
- •Группа процессоров и коммутаторов.
- •Управление группами.
- •Управление коммуникаторами.
- •Показатели эффективности в параллельных алгоритмах.
- •Модельная задача – вычисление частных сумм последовательности числовых значений.
- •Последовательный алгоритм суммирования
- •Каскадная схема суммирования.
- •Каскадная схема с асимптотически ненулевой эффективностью.
- •Построение частичных сумм.
- •Оценка максимального параллелизма.
- •Закон Амдаля
- •Закон Густавсона-Барсиса
- •Анализ масштабируемости параллельных вычислений.
- •Верхняя граница времени выполнения параллельного алгоритма.
- •Факторы, влияющие на производительность, и способы ее повышения.
- •Принципы разработка параллельных алгоритмов.
- •Моделирование (использование моделей) при проектировании параллельных алгоритмов.
- •Этапы разработки параллельных алгоритмов.
- •Разделение вычислительной схемы на независимые части, на основе ее анализа.
- •Определение информационных зависимостей.
- •Масштабирование набора подзадач.
- •Распределение подзадач между процессорами.
- •Умножение матриц при ленточной схеме разделения данных.
- •Определение подзадач.
- •Выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.
- •Итерация прямого хода алгоритма Гаусса
- •Построение параллельного алгоритма
- •Масштабирование и распределение подзадач по процессорам.
- •Анализ эффективности.
- •Параллельные методы сортировки
- •Принципы распараллеливания
- •Масштабирование параллельных вычислений
- •Пузырьковая сортировка
- •Алгоритм чет-нечетной перестановки
- •Определение подзадач и выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельные вычисления при решении задач на графах.
- •Программная реализация параллельного алгоритма Флойда:
- •Определение подзадач.
- •Анализ эффективности
- •Результаты вычислительных экспериментов для параллельного алгоритма Флойда
- •Работа pvm
- •Структура идентификатора td
- •Модель передачи сообщений
- •Настройка pvm
- •Структура каталога pvm:
- •Наиболее распространенные проблемы
- •Пример простейшей программы
- •Структура программы pvm.
- •Выводы по pvm:
- •Классификация вычислительных систем
- •Алгоритмы предварительного распределения данных (графы)
- •Режимы параллельных вычислений с общей памятью
- •Основные обозначения псевдокода
- •Распределение данных в erew
- •Параллельное программирование с использованием общей памяти
- •Многопоточное программирование
- •Спецификация posix Threads
- •Пример программы с использованием posix Threads
- •Механизмы синхронизации потоков
- •Среда Open mp
- •Основные правила:
- •Синхронизация
- •Обзор средств параллельного и распределенного программирования.
- •Литература:
Режимы передачи данных mpi.
Реализуется в стандартном режиме, т.е. процесс –отправитель блокируется, после завершения можно использовать буфер опять, возможные состояния сообщения:
п ринадлежность процессу-отправителю;
состояние передачи;
принадлежность процессу-получателю;
принято, завершится после Recv;
Синхронный вызов:
MPI_Send Стандартный(Standart)–обеспечивается функциейMPI_Send, на время выполнения функции процесс-отправитель сообщения блокируется, после завершения функции буфер может быть использован повторно, состояние отправленного сообщения может быть различным сообщение может располагаться в процессе-отправителе, может находиться в процессе передачи, может храниться в процессе-получателе или же может быть принято процессом-получателем при помощи функции MPI_Recv.
MPI_Ssend Синхронный (Synchronous) режим–завершение функции отправки сообщения происходит только при получении от процесса-получателя подтверждения о начале приема отправленного сообщения.
MPI_Rsend – самый быстрый вариант обмена, выполнится, если к моменту вызова инициирована операция приема сообщения ( если Recv не вызван, то Rsend считается ошибкой)
MPI_Bsend – завершится во всех случаях, если неинициирована, в буфер помещает сообщение и завершается, если инициирована операция приема - просто завершится, так как сообщение передано. Для его использования нужно создать буфер:
int MPI_Buffer_attach (void*buf, int size)
выделить память
int MPI_Buffer_detech (void*buf, int size)
очистить память
Режимы передачи данных
Режим передачи по готовности формально является наиболее быстрым, но используется остаточно редко, т.к. обычно сложно гарантировать готовность операции приема.
Стандартный и буферизованный режимы также выполняются достаточно быстро, но могут приводить к большим расходам ресурсов (памяти), могут быть рекомендованы для передачи коротких сообщений.
Синхронный режим является наиболее медленным, т.к. требует подтверждения приема. В тоже время, этот режим наиболее надежен – можно рекомендовать его для передачи длинных сообщений.
Лекция 5
Всегда используется буфер и должны быть выполнены следующие операции:
int MPI_Pac_size(int count, MPI_Datatype type, MPI_Comm comm, int *size ); - функция возвращает размер буфера.
+ предопределенная константа (к длине буфера)
MPI_BSEND_OVERHEAD – служебная область сообщений.
Необходимо учесть: в буфере могут располагаться несколько сообщений.
Распределение памяти под буфер.
malloc, calloc.
Для применения буферизованного режима передачи может быть создан и передан MPI буфер памяти, используемая для этого функция имеет вид:
int MPI_Buffer_attach(void *buf, int size),
где
buf — адрес буфера памяти;
size — размер буфера.
Перессылки (использование буфера).
После завершения работы с буфером он должен быть отключен от MPI при помощи функции:
int MPI_Buffer_detach(void *buf, int *size),
где
buf — адрес буфера памяти;
size — возвращаемый размер буфера.
Освобождение памяти.
free();
Используя соответствующие режимы Bsend, Rsend можно исключить задержки, блокировки процесса-отправителя не будет.
Если запрос на прием выполнен, а сообщение не передано, то процесс получателя блокируется – MPI_Recv.