- •Моделирование и анализ параллельных вычислений.
- •Модель вычислений в виде графа "операции – операнды".
- •Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).
- •Определение времени выполнения параллельного алгоритма.
- •Правила разработки алгоритмов.
- •Программирование параллельных алгоритмов.
- •Технология mpi.
- •Введение в библиотеку mpich.
- •Структура параллельной программы с использованием mpi:
- •Передача/прием сообщений между отдельными процессами.
- •Использование модульной структуры.
- •Определение времени выполнения программ.
- •Контроль выполнения программ.
- •Передача данных от одного процесса всем процессам программы.
- •Передача данных от всех процессов одному процессу. Операция редукции.
- •Пример коллективного вызова (без обмена)- коллективная синхронизация.
- •Аварийное завершение параллельной программы
- •Оценка коммуникационных затрат для кластерных систем.
- •Режимы передачи данных mpi.
- •Организация неблокирующих обменов данными между процессами.
- •Одновременное выполнение передачи и приема.
- •Группа процессоров и коммутаторов.
- •Управление группами.
- •Управление коммуникаторами.
- •Показатели эффективности в параллельных алгоритмах.
- •Модельная задача – вычисление частных сумм последовательности числовых значений.
- •Последовательный алгоритм суммирования
- •Каскадная схема суммирования.
- •Каскадная схема с асимптотически ненулевой эффективностью.
- •Построение частичных сумм.
- •Оценка максимального параллелизма.
- •Закон Амдаля
- •Закон Густавсона-Барсиса
- •Анализ масштабируемости параллельных вычислений.
- •Верхняя граница времени выполнения параллельного алгоритма.
- •Факторы, влияющие на производительность, и способы ее повышения.
- •Принципы разработка параллельных алгоритмов.
- •Моделирование (использование моделей) при проектировании параллельных алгоритмов.
- •Этапы разработки параллельных алгоритмов.
- •Разделение вычислительной схемы на независимые части, на основе ее анализа.
- •Определение информационных зависимостей.
- •Масштабирование набора подзадач.
- •Распределение подзадач между процессорами.
- •Умножение матриц при ленточной схеме разделения данных.
- •Определение подзадач.
- •Выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.
- •Итерация прямого хода алгоритма Гаусса
- •Построение параллельного алгоритма
- •Масштабирование и распределение подзадач по процессорам.
- •Анализ эффективности.
- •Параллельные методы сортировки
- •Принципы распараллеливания
- •Масштабирование параллельных вычислений
- •Пузырьковая сортировка
- •Алгоритм чет-нечетной перестановки
- •Определение подзадач и выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельные вычисления при решении задач на графах.
- •Программная реализация параллельного алгоритма Флойда:
- •Определение подзадач.
- •Анализ эффективности
- •Результаты вычислительных экспериментов для параллельного алгоритма Флойда
- •Работа pvm
- •Структура идентификатора td
- •Модель передачи сообщений
- •Настройка pvm
- •Структура каталога pvm:
- •Наиболее распространенные проблемы
- •Пример простейшей программы
- •Структура программы pvm.
- •Выводы по pvm:
- •Классификация вычислительных систем
- •Алгоритмы предварительного распределения данных (графы)
- •Режимы параллельных вычислений с общей памятью
- •Основные обозначения псевдокода
- •Распределение данных в erew
- •Параллельное программирование с использованием общей памяти
- •Многопоточное программирование
- •Спецификация posix Threads
- •Пример программы с использованием posix Threads
- •Механизмы синхронизации потоков
- •Среда Open mp
- •Основные правила:
- •Синхронизация
- •Обзор средств параллельного и распределенного программирования.
- •Литература:
Работа pvm
Создание параллельной виртуальной машины. На каждом хосте при этом запускается демон (pvmd). Каждому процессу присваивается идентификатор TD (аналогично рангу в MPI, но на системном уровне есть отличия).
Идентификатор – это ссылка на служебную информацию с описание процесса. TD назначается локальным демоном. Доступ к TD осуществляется с помощью библиотечной функции.
Каждому компьютеру присваивается имя, связанное с его архитектурой. Каждый процесс может передавать сообщения другому процессу. Так же, можно создавать динамические группы (эквивалент коммуникаторам).
При запуске демона в каталоге /tmp (служебный каталог временного хранения) создается файл pvmd.UTD, расширение которого совпадает с числовым идентификатором пользователя. Этот файл является блокирующим – если демон не работает, то такой хост нельзя добавить в систему виртуальной машины. Чтобы удалить pvd.UID, необходимо с помощью консоли ввести команду halt (остановить всё).
Демон параллельной виртуальной машины – это гибкое средство, позволяющее на одном компьютере работать нескольким пользователям PVM. Причем, для каждого пользователя запускается свой демон, и они работают независимо.
Демон играет роль маршрутизатора сообщений. Он управляет процессами, обеспечивает продолжение работы при аварийном завершении. pvmd, запущенный вручную - называется главным (master). Остальные называются исполнителями (slave). Главный демон запускает остальные slave.
Демон принимает запросы на управление конфигурацией.
Структура идентификатора td
31 30 18 12 0
|
|
Н-хост
|
Идентификатор процесса
|
n – номер задачи |
S G
S, G, H – глобальные параметры интерпретируются всеми демонами одинаково.
При запуске N хостов относительно виртуальной машины, каждый демон конфигурирует с собственным номером хоста.
На каждом хосте можно запустить (218 - 1) задач.
4095 – ограничение на номер хоста.
Взаимооднозначное соответствие между номерами и физическими хостами необязательно; устанавливается глобальной таблицей.
Модель передачи сообщений
Сообщениями обмениваются задачи под управлением демонов. При обмене данные преобразуются в формат XDR, т.о. преодолевается гетерогенность. При отправке сообщения отправитель не блокируется.
Сообщение передается в коммуникационную сеть, откуда попадает в буфер приема (адресата).
Буферы обмены выделяются динамически.
Последовательность сообщений от одного отправителя сохраняются при приеме.
Настройка pvm
Для установки PVM не требуется быть администратором; установить можно в личный каталог.
Настраиваются переменные окружения:
PVM_ROOT – путь к каталогу, в котором размещается система PVM.
PVM_ARCH – сюда прописываются идентификаторы архитектуры.