- •Моделирование и анализ параллельных вычислений.
- •Модель вычислений в виде графа "операции – операнды".
- •Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).
- •Определение времени выполнения параллельного алгоритма.
- •Правила разработки алгоритмов.
- •Программирование параллельных алгоритмов.
- •Технология mpi.
- •Введение в библиотеку mpich.
- •Структура параллельной программы с использованием mpi:
- •Передача/прием сообщений между отдельными процессами.
- •Использование модульной структуры.
- •Определение времени выполнения программ.
- •Контроль выполнения программ.
- •Передача данных от одного процесса всем процессам программы.
- •Передача данных от всех процессов одному процессу. Операция редукции.
- •Пример коллективного вызова (без обмена)- коллективная синхронизация.
- •Аварийное завершение параллельной программы
- •Оценка коммуникационных затрат для кластерных систем.
- •Режимы передачи данных mpi.
- •Организация неблокирующих обменов данными между процессами.
- •Одновременное выполнение передачи и приема.
- •Группа процессоров и коммутаторов.
- •Управление группами.
- •Управление коммуникаторами.
- •Показатели эффективности в параллельных алгоритмах.
- •Модельная задача – вычисление частных сумм последовательности числовых значений.
- •Последовательный алгоритм суммирования
- •Каскадная схема суммирования.
- •Каскадная схема с асимптотически ненулевой эффективностью.
- •Построение частичных сумм.
- •Оценка максимального параллелизма.
- •Закон Амдаля
- •Закон Густавсона-Барсиса
- •Анализ масштабируемости параллельных вычислений.
- •Верхняя граница времени выполнения параллельного алгоритма.
- •Факторы, влияющие на производительность, и способы ее повышения.
- •Принципы разработка параллельных алгоритмов.
- •Моделирование (использование моделей) при проектировании параллельных алгоритмов.
- •Этапы разработки параллельных алгоритмов.
- •Разделение вычислительной схемы на независимые части, на основе ее анализа.
- •Определение информационных зависимостей.
- •Масштабирование набора подзадач.
- •Распределение подзадач между процессорами.
- •Умножение матриц при ленточной схеме разделения данных.
- •Определение подзадач.
- •Выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.
- •Итерация прямого хода алгоритма Гаусса
- •Построение параллельного алгоритма
- •Масштабирование и распределение подзадач по процессорам.
- •Анализ эффективности.
- •Параллельные методы сортировки
- •Принципы распараллеливания
- •Масштабирование параллельных вычислений
- •Пузырьковая сортировка
- •Алгоритм чет-нечетной перестановки
- •Определение подзадач и выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельные вычисления при решении задач на графах.
- •Программная реализация параллельного алгоритма Флойда:
- •Определение подзадач.
- •Анализ эффективности
- •Результаты вычислительных экспериментов для параллельного алгоритма Флойда
- •Работа pvm
- •Структура идентификатора td
- •Модель передачи сообщений
- •Настройка pvm
- •Структура каталога pvm:
- •Наиболее распространенные проблемы
- •Пример простейшей программы
- •Структура программы pvm.
- •Выводы по pvm:
- •Классификация вычислительных систем
- •Алгоритмы предварительного распределения данных (графы)
- •Режимы параллельных вычислений с общей памятью
- •Основные обозначения псевдокода
- •Распределение данных в erew
- •Параллельное программирование с использованием общей памяти
- •Многопоточное программирование
- •Спецификация posix Threads
- •Пример программы с использованием posix Threads
- •Механизмы синхронизации потоков
- •Среда Open mp
- •Основные правила:
- •Синхронизация
- •Обзор средств параллельного и распределенного программирования.
- •Литература:
Программирование параллельных алгоритмов.
Существуют подходы, основанные на специальных языках программирования
Расширение обычных языков программирования (последовательное программирование)
Использование специальных библиотек. Этот способ нашел наибольше распространение для программирования распределенных вычислений. Программы, реализующиеся для кластеров. Здесь используются уже существующие компоненты + дополнительные библиотеки.
Наибольшее распространение получили:
Технология MPI (Message Passing Interface – интерфейс передачи сообщений) . Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу.
Технология PVM (Parallel Virtual Machine - виртуальная параллельная машина)
Главное отличие: PVM позволяет более гибко управлять параллельными процессами. MPI такой гибкости не достигла.
Технология mpi.
Разработана в середине 90-х годов. Основная идея: порождение нескольких процессов. Программа реализуется параллельно в виде вызова функции специальной библиотеки. Проблемы переносимости практически нет. Технология MPI снижает сложность разработки. Стандарт MPI фиксирует интерфейс, который должен соблюдаться как системой программирования на каждой вычислительной платформе, так и пользователем при создании своих программ. Современные реализации, чаще всего, соответствуют стандарту MPI версии 1.1. В 1997—1998 годах появился стандарт MPI-2.0, значительно расширивший функциональность предыдущей версии. Однако до сих пор этот вариант MPI не получил широкого распространения и в полном объеме не реализован ни на одной системе. MPI поддерживает работу с языками Фортран и Си.
Все дополнительные объекты: имена процедур, константы, предопределенные типы данных и т.п., используемые в MPI, имеют префикс MPI_. Если пользователь не будет использовать в программе имен с таким префиксом, то конфликтов с объектами MPI заведомо не будет. В языке Си, кроме того, является существенным регистр символов в названиях функций. Обычно в названиях функций MPI первая буква после префикса MPI_ пишется в верхнем регистре, последующие буквы – в нижнем регистре, а названия констант MPI записываются целиком в верхнем регистре. Все описания интерфейса MPI собраны в файле mpif.h (mpi.h).
Наиболее практической библиотекой является MPICH (англ. «Message Passing Interface Chameleon») — это одна из самых первых разработанных библиотек MPI.
Введение в библиотеку mpich.
Библиотека вызывается из программы и представляет собой набор функций. Достаточно использовать 6 функций.
Основные:
MPI_INIT (INTEGER IERR) (init arg с, char *arg v[]) Инициализация параллельной части программы. Все другие процедуры MPI могут быть вызваны только после вызова MPI_INIT. Инициализация параллельной части для каждого приложения должна выполняться только один раз. В языке Си функции MPI_Init передаются указатели на аргументы командной строки программы argc и argv, из которых системой могут извлекаться и передаваться в параллельные процессы некоторые параметры запуска программы.
MPI_FINALIZE (INTEGER IERR). Завершение параллельной части приложения. Все последующие обращения к любым процедурам MPI, в том числе к MPI_INIT, запрещены. К моменту вы-зова MPI_FINALIZE каждым процессом программы все действия, требующие его участия в обмене сообщениями, должны быть завершены.
Общая схема MPI-программы на языке Си выглядит примерно следующим образом:
#include “mpi.h”
main(int argc, char **argv)
{
…
MPI_Init(&argc, &argv);
…
MPI_Finalize();
…
}
MPI_INITIALIZED(FLAG, IERR)
LOGICAL FLAG INTEGER IERR. Процедура возвращает в
аргументе FLAG значение .TRUE., если вызвана из параллельной части приложения, и значение .FALSE. - в противном случае. Это единственная процедура MPI, которую можно вызвать до вызова MPI_INIT.
MPI_COMM_SIZE(COMM, SIZE, IERR)
INTEGER COMM, SIZE, IERR. В аргументе SIZE процедура возвращает число параллельных процессов в коммуникаторе COMM.
MPI_COMM_RANK(COMM, RANK, IERR)
INTEGER COMM, RANK, IERR. В аргументе RANK процедура возвращает номер процесса в коммуникаторе COMM. Если процедура MPI_COMM_SIZE для того же коммуникатора COMM вернула значение SIZE, то значение, возвращаемое процедурой MPI_COMM_RANK через переменную RANK, лежит в диапазоне от 0 до SIZE-1.