- •Моделирование и анализ параллельных вычислений.
- •Модель вычислений в виде графа "операции – операнды".
- •Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).
- •Определение времени выполнения параллельного алгоритма.
- •Правила разработки алгоритмов.
- •Программирование параллельных алгоритмов.
- •Технология mpi.
- •Введение в библиотеку mpich.
- •Структура параллельной программы с использованием mpi:
- •Передача/прием сообщений между отдельными процессами.
- •Использование модульной структуры.
- •Определение времени выполнения программ.
- •Контроль выполнения программ.
- •Передача данных от одного процесса всем процессам программы.
- •Передача данных от всех процессов одному процессу. Операция редукции.
- •Пример коллективного вызова (без обмена)- коллективная синхронизация.
- •Аварийное завершение параллельной программы
- •Оценка коммуникационных затрат для кластерных систем.
- •Режимы передачи данных mpi.
- •Организация неблокирующих обменов данными между процессами.
- •Одновременное выполнение передачи и приема.
- •Группа процессоров и коммутаторов.
- •Управление группами.
- •Управление коммуникаторами.
- •Показатели эффективности в параллельных алгоритмах.
- •Модельная задача – вычисление частных сумм последовательности числовых значений.
- •Последовательный алгоритм суммирования
- •Каскадная схема суммирования.
- •Каскадная схема с асимптотически ненулевой эффективностью.
- •Построение частичных сумм.
- •Оценка максимального параллелизма.
- •Закон Амдаля
- •Закон Густавсона-Барсиса
- •Анализ масштабируемости параллельных вычислений.
- •Верхняя граница времени выполнения параллельного алгоритма.
- •Факторы, влияющие на производительность, и способы ее повышения.
- •Принципы разработка параллельных алгоритмов.
- •Моделирование (использование моделей) при проектировании параллельных алгоритмов.
- •Этапы разработки параллельных алгоритмов.
- •Разделение вычислительной схемы на независимые части, на основе ее анализа.
- •Определение информационных зависимостей.
- •Масштабирование набора подзадач.
- •Распределение подзадач между процессорами.
- •Умножение матриц при ленточной схеме разделения данных.
- •Определение подзадач.
- •Выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.
- •Итерация прямого хода алгоритма Гаусса
- •Построение параллельного алгоритма
- •Масштабирование и распределение подзадач по процессорам.
- •Анализ эффективности.
- •Параллельные методы сортировки
- •Принципы распараллеливания
- •Масштабирование параллельных вычислений
- •Пузырьковая сортировка
- •Алгоритм чет-нечетной перестановки
- •Определение подзадач и выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельные вычисления при решении задач на графах.
- •Программная реализация параллельного алгоритма Флойда:
- •Определение подзадач.
- •Анализ эффективности
- •Результаты вычислительных экспериментов для параллельного алгоритма Флойда
- •Работа pvm
- •Структура идентификатора td
- •Модель передачи сообщений
- •Настройка pvm
- •Структура каталога pvm:
- •Наиболее распространенные проблемы
- •Пример простейшей программы
- •Структура программы pvm.
- •Выводы по pvm:
- •Классификация вычислительных систем
- •Алгоритмы предварительного распределения данных (графы)
- •Режимы параллельных вычислений с общей памятью
- •Основные обозначения псевдокода
- •Распределение данных в erew
- •Параллельное программирование с использованием общей памяти
- •Многопоточное программирование
- •Спецификация posix Threads
- •Пример программы с использованием posix Threads
- •Механизмы синхронизации потоков
- •Среда Open mp
- •Основные правила:
- •Синхронизация
- •Обзор средств параллельного и распределенного программирования.
- •Литература:
Построение параллельного алгоритма
Поскольку решение методом Гаусса сводится к последовательности однотипных вычислительных операций умножения и сложения над строками матрицы, в качестве подзадач можно принять вычисления, связанные с обработкой одной или нескольких строк матрицы A и соответствующего элемента вектора b.
нужно собрать ведущие элементы на первом процессоре и выбрать ведущую строку;
затем надо ведущую строку разослать всем процессорам, в которых есть к –ые строки;
получив ведущую строку, все процессоры выполняют вычитание строк и исключают из системы переменную .
В обратном ходе метода Гаусса, как только какая-либо, например i–я подзадача,
0 ≤i<n-1, определила свою переменную ., это значение рассылается всем подзадачам с номерами k, k<i. В каждой подзадаче полученное значение неизвестной умножается на соответствующий коэффициент и выполняется корректировка соответствующего элемента вектора b.
Масштабирование и распределение подзадач по процессорам.
В качестве подзадач могут быть взяты строки матрицы A, каждая из которых при этом закрепляется за одним процессором. Если число строк матрицы больше, чем число доступных процессоров (p<n), подзадачи можно укрупнить, объединив несколько строк матрицы. Если при этом используется последовательная схема разделения данных, при которой в одной подзадаче оказываются соседние строки матрицы, по мере исключения (в прямом ходе) или определения (в обратном ходе) неизвестных, все большая часть процессоров, для которой вычисления завершены, окажется простаивающей.
Пример использования ленточной циклической схемы разделения строк матрицы между тремя процессорами:
Рис. 10
Распределение подзадач между процессорами должно также учитывать характер обмена данными между подзадачами. В рассматриваемом методе Гаусса взаимодействие подзадач заключается в передаче данных от одного процессора всем процессорам вычислительной системы. Поэтому в данном случае целесообразна топология сети передачи данных в виде гиперкуба или полного графа.
Анализ эффективности.
Пусть n – порядок системы линейных уравнений, а p, p<n – число используемых процессоров, т.е. матрица А имеет размер n×n, а n/p – размер полосы на каждом процессоре (для простоты полагаем, что n/p – целое число). Определим сложность параллельного варианта метода Гаусса.
В прямом ходе алгоритма для выбора ведущей строки на каждой итерации и каждом процессоре должно быть определено максимальное значение в столбце с исключаемой неизвестной в пределах закрепленной за ним полосы. По мере исключения неизвестных количество строк в полосах сокращается. После сбора полученных максимальных значений, определения и рассылки ведущей строки на каждом процессоре выполняется вычитание ведущей строки из каждой строки оставшейся части строк своей полосы матрицы A.
Общие затраты на выполнение действий в одной строке на i-й итерации, 0 ≤i<n-2 составляет 2(n-i)+1 операций. Если применена циклическая схема распределения данных между процессорами, то на i-й итерации каждый процессор будет обрабатывать примерно (n-i)/s строк. С учетом этого, общее число операций параллельного варианта прямого хода метода Гаусса определяется выражением :
=
Обратный ход. После рассылки очередного сообщения:
Ускорение :
Эффективность :
Затраты при обратном ходе:
Лекция 9