- •Моделирование и анализ параллельных вычислений.
- •Модель вычислений в виде графа "операции – операнды".
- •Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).
- •Определение времени выполнения параллельного алгоритма.
- •Правила разработки алгоритмов.
- •Программирование параллельных алгоритмов.
- •Технология mpi.
- •Введение в библиотеку mpich.
- •Структура параллельной программы с использованием mpi:
- •Передача/прием сообщений между отдельными процессами.
- •Использование модульной структуры.
- •Определение времени выполнения программ.
- •Контроль выполнения программ.
- •Передача данных от одного процесса всем процессам программы.
- •Передача данных от всех процессов одному процессу. Операция редукции.
- •Пример коллективного вызова (без обмена)- коллективная синхронизация.
- •Аварийное завершение параллельной программы
- •Оценка коммуникационных затрат для кластерных систем.
- •Режимы передачи данных mpi.
- •Организация неблокирующих обменов данными между процессами.
- •Одновременное выполнение передачи и приема.
- •Группа процессоров и коммутаторов.
- •Управление группами.
- •Управление коммуникаторами.
- •Показатели эффективности в параллельных алгоритмах.
- •Модельная задача – вычисление частных сумм последовательности числовых значений.
- •Последовательный алгоритм суммирования
- •Каскадная схема суммирования.
- •Каскадная схема с асимптотически ненулевой эффективностью.
- •Построение частичных сумм.
- •Оценка максимального параллелизма.
- •Закон Амдаля
- •Закон Густавсона-Барсиса
- •Анализ масштабируемости параллельных вычислений.
- •Верхняя граница времени выполнения параллельного алгоритма.
- •Факторы, влияющие на производительность, и способы ее повышения.
- •Принципы разработка параллельных алгоритмов.
- •Моделирование (использование моделей) при проектировании параллельных алгоритмов.
- •Этапы разработки параллельных алгоритмов.
- •Разделение вычислительной схемы на независимые части, на основе ее анализа.
- •Определение информационных зависимостей.
- •Масштабирование набора подзадач.
- •Распределение подзадач между процессорами.
- •Умножение матриц при ленточной схеме разделения данных.
- •Определение подзадач.
- •Выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.
- •Итерация прямого хода алгоритма Гаусса
- •Построение параллельного алгоритма
- •Масштабирование и распределение подзадач по процессорам.
- •Анализ эффективности.
- •Параллельные методы сортировки
- •Принципы распараллеливания
- •Масштабирование параллельных вычислений
- •Пузырьковая сортировка
- •Алгоритм чет-нечетной перестановки
- •Определение подзадач и выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельные вычисления при решении задач на графах.
- •Программная реализация параллельного алгоритма Флойда:
- •Определение подзадач.
- •Анализ эффективности
- •Результаты вычислительных экспериментов для параллельного алгоритма Флойда
- •Работа pvm
- •Структура идентификатора td
- •Модель передачи сообщений
- •Настройка pvm
- •Структура каталога pvm:
- •Наиболее распространенные проблемы
- •Пример простейшей программы
- •Структура программы pvm.
- •Выводы по pvm:
- •Классификация вычислительных систем
- •Алгоритмы предварительного распределения данных (графы)
- •Режимы параллельных вычислений с общей памятью
- •Основные обозначения псевдокода
- •Распределение данных в erew
- •Параллельное программирование с использованием общей памяти
- •Многопоточное программирование
- •Спецификация posix Threads
- •Пример программы с использованием posix Threads
- •Механизмы синхронизации потоков
- •Среда Open mp
- •Основные правила:
- •Синхронизация
- •Обзор средств параллельного и распределенного программирования.
- •Литература:
Режимы параллельных вычислений с общей памятью
CRCW – произвольно много процессоров могут одновременно читать содержимое одной и той же ячейки памяти и произвольно много процессоров могут обращаться для записи в одну и ту же ячейку памяти. Данная модель разделяется на следующие подвиды в зависимости от способа разрешения конфликтов записи:
1) COMMON(CRCW)PRAM, в которой должны быть идентичными все значения, записываемые одновременно;
2) ARBITRARY(CRCW)PRAM, в которой срабатывает любой один из конкурирующих в записи процессоров;
3) PRIORITY(CRCW)PRAM, в которой процессоры линейно упорядочены в соответствии с их приоритетами и выбирается тот из конфликтующих, который имеет наивысший приоритет;
4) COMBINING(CRCW)PRAM, в которой записывается линейная комбинация вычисленных значений, например их сумма. Значения могут комбинироваться с помощью любой ассоциативной и коммутативной операции, которая вычислима за константное время на РАМ.
CREW – произвольно много процессоров могут одновременно читать содержимое одной и той же ячейки памяти, но писать может только один.
ERCW - исключающее считывание/параллельная запись
EREW - только один процессор может читать содержимое ячейки памяти и только один процессор может писать в эту ячейку.
Основные обозначения псевдокода
- i-ый процессор
N –число элементов во входном списке
- j-ое поле памяти
pstart и PEnd – скобки, фрагмент алгоритма, все операции выполняются параллельно.
Пример. Распределение данных в модели CREW
P[1] M[1]; // записывает в первое поле памяти данные
PStart
for (k=z; k≤p; k++)
P[k]←M[1]; // остальные прочитали
PEnd
Распределение совершается в два этапа. На первом значение записывается в память, на втором – все процессоры читают его. Такая скорость возможна только благодаря конкурентному чтению.
Распределение данных в erew
В модели с исключительным чтением значение, записанное процессором Pi, может прочитать лишь один процессор. Если просто организовать цикл поочередного чтения остальными процессорами, то получим последовательный алгоритм, нивелирующий все преимущества параллелизма.
Однако если воспользоваться циклом чтение / обработка / запись на втором процессоре для записи значения в другую ячейку памяти, то на следующем шаге уже два процессора смогут прочитать это значение. Записав его затем еще в две ячейки, мы сможем воспользоваться уже четырьмя процессорами. В результате получается следующий алгоритм.
P[1] M[1];
i=1;
for (j=1; j≤logP; j++)
{
PStart
for (k=i+1; k≤2*i; k++)
{
P[k]←M[k-i];
P[k] M[k];
}
PEnd
i=i*2;
}
Лекция 13
Параллельное программирование с использованием общей памяти
T1, CRCW – наименее жесткий режим.
T2, EREW - чтение и запись невозможны из одного и того же поля (противоположность CRCW).
В CRCW любой алгоритм выполняется в этой модели, при условии, что:
Алгоритм использует p процессоров.
Существует алгоритм, который буде выполняться в модели EREW, реализует ту же самую задачу, с тем же числом процессоров. Время его выполнения не превышает время выполнения одного алгоритма в
Людой алгоритм можно перевести в другой режим.