- •Моделирование и анализ параллельных вычислений.
- •Модель вычислений в виде графа "операции – операнды".
- •Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).
- •Определение времени выполнения параллельного алгоритма.
- •Правила разработки алгоритмов.
- •Программирование параллельных алгоритмов.
- •Технология mpi.
- •Введение в библиотеку mpich.
- •Структура параллельной программы с использованием mpi:
- •Передача/прием сообщений между отдельными процессами.
- •Использование модульной структуры.
- •Определение времени выполнения программ.
- •Контроль выполнения программ.
- •Передача данных от одного процесса всем процессам программы.
- •Передача данных от всех процессов одному процессу. Операция редукции.
- •Пример коллективного вызова (без обмена)- коллективная синхронизация.
- •Аварийное завершение параллельной программы
- •Оценка коммуникационных затрат для кластерных систем.
- •Режимы передачи данных mpi.
- •Организация неблокирующих обменов данными между процессами.
- •Одновременное выполнение передачи и приема.
- •Группа процессоров и коммутаторов.
- •Управление группами.
- •Управление коммуникаторами.
- •Показатели эффективности в параллельных алгоритмах.
- •Модельная задача – вычисление частных сумм последовательности числовых значений.
- •Последовательный алгоритм суммирования
- •Каскадная схема суммирования.
- •Каскадная схема с асимптотически ненулевой эффективностью.
- •Построение частичных сумм.
- •Оценка максимального параллелизма.
- •Закон Амдаля
- •Закон Густавсона-Барсиса
- •Анализ масштабируемости параллельных вычислений.
- •Верхняя граница времени выполнения параллельного алгоритма.
- •Факторы, влияющие на производительность, и способы ее повышения.
- •Принципы разработка параллельных алгоритмов.
- •Моделирование (использование моделей) при проектировании параллельных алгоритмов.
- •Этапы разработки параллельных алгоритмов.
- •Разделение вычислительной схемы на независимые части, на основе ее анализа.
- •Определение информационных зависимостей.
- •Масштабирование набора подзадач.
- •Распределение подзадач между процессорами.
- •Умножение матриц при ленточной схеме разделения данных.
- •Определение подзадач.
- •Выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.
- •Итерация прямого хода алгоритма Гаусса
- •Построение параллельного алгоритма
- •Масштабирование и распределение подзадач по процессорам.
- •Анализ эффективности.
- •Параллельные методы сортировки
- •Принципы распараллеливания
- •Масштабирование параллельных вычислений
- •Пузырьковая сортировка
- •Алгоритм чет-нечетной перестановки
- •Определение подзадач и выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельные вычисления при решении задач на графах.
- •Программная реализация параллельного алгоритма Флойда:
- •Определение подзадач.
- •Анализ эффективности
- •Результаты вычислительных экспериментов для параллельного алгоритма Флойда
- •Работа pvm
- •Структура идентификатора td
- •Модель передачи сообщений
- •Настройка pvm
- •Структура каталога pvm:
- •Наиболее распространенные проблемы
- •Пример простейшей программы
- •Структура программы pvm.
- •Выводы по pvm:
- •Классификация вычислительных систем
- •Алгоритмы предварительного распределения данных (графы)
- •Режимы параллельных вычислений с общей памятью
- •Основные обозначения псевдокода
- •Распределение данных в erew
- •Параллельное программирование с использованием общей памяти
- •Многопоточное программирование
- •Спецификация posix Threads
- •Пример программы с использованием posix Threads
- •Механизмы синхронизации потоков
- •Среда Open mp
- •Основные правила:
- •Синхронизация
- •Обзор средств параллельного и распределенного программирования.
- •Литература:
Алгоритм чет-нечетной перестановки
Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения используется не сам этот алгоритм, а его модификация, известная в литературе как метод чет-нечетной перестановки ( the odd-even transposition method ). Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода: в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Таким образом, на всех нечетных итерациях сравниваются пары
(a1, a2), (a3, a4), ..., (an-1,an) (при четном n),
а на четных итерациях обрабатываются элементы
(a2, a3), (a4, a5), ..., (an-2,an-1).
После n -кратного повторения итераций сортировки исходный набор данных оказывается упорядоченным.
Определение подзадач и выделение информационных зависимостей
Получение параллельного варианта для метода чет-нечетной перестановки уже не представляет каких-либо затруднений – сравнения пар значений на итерациях сортировки являются независимыми и могут быть выполнены параллельно. В случае p<n, когда количество процессоров меньше числа упорядочиваемых значений, процессоры содержат блоки данных размера n/p и в качестве базовой подзадачи может быть использована операция "сравнить и разделить”.
// Параллельный алгоритм чет-нечетной перестановки
ParallelOddEvenSort(double A[], int n) {
int id = GetProcId(); // номер процесса
int np = GetProcNum(); // количество процессов
for (int i = 0; i < np; i++ ) {
if (i % 2 == 1) { // нечетная итерация
if (id % 2 == 1) { // нечетный номер процесса
// Cравнение-обмен с процессом — соседом справа
if (id < np - 1) compare_split_min(id + 1);
}
else
// Cравнение-обмен с процессом — соседом слева
if (id > 0) compare_split_max(id - 1);
}
else { // четная итерация
if(id % 2 == 0) { // четный номер процесса
// Cравнение-обмен с процессом — соседом справа
if (id < np - 1) compare_split_min(id + 1);
}
else
// Cравнение-обмен с процессом — соседом слева
compare_split_max(id - 1);
}
}
}
Для пояснения такого параллельного способа сортировки в табл. 3 приведен пример упорядочения данных при n=16, p=4 (т.е. блок значений на каждом процессоре содержит n/p=4 элемента). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессов, для которых параллельно выполняются операции "сравнить и разделить". Взаимодействующие пары процессов выделены в таблице рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.
В общем случае выполнение параллельного метода может быть прекращено, если в течение каких-либо двух последовательных итераций сортировки состояние упорядочиваемого набора данных не было изменено. Как результат, общее количество итераций может быть сокращено, и для фиксации таких моментов необходимо введение некоторого управляющего процессора, который определял бы состояние набора данных после выполнения каждой итерации сортировки. Однако трудоемкость такой коммуникационной операции (сборка на одном процессоре сообщений от всех процессоров) может оказаться столь значительной, что весь эффект от возможного сокращения итераций сортировки будет поглощен затратами на реализацию операций межпроцессорной передачи данных.
Таблица 9.1. Пример сортировки данных параллельным методом чет-нечетной перестановки |
||||
№ и тип итераци |
Процессоры |
|||
1 |
2 |
3 |
4 |
|
Исходные данные |
13 55 59 88 |
29 43 71 85 |
2 18 40 75 |
4 14 22 43 |
1 нечет (1, 2), (3, 4) |
13 55 59 88 |
29 43 71 85 |
2 18 40 75 |
4 14 22 43 |
13 29 43 55 |
59 71 85 88 |
2 4 14 18 |
22 40 43 75 |
|
2 чет (2, 3) |
13 29 43 55 |
59 71 85 88 |
2 4 14 18 |
22 40 43 75 |
13 29 43 55 |
2 4 14 18 |
59 71 85 88 |
22 40 43 75 |
|
3 нечет (1, 2), (3, 4) |
13 29 43 55 |
2 4 14 18 |
59 71 85 88 |
22 40 43 75 |
2 4 13 14 |
18 29 43 55 |
22 40 43 59 |
71 75 85 88 |
|
4 чет (2, 3) |
2 4 13 14 |
18 29 43 55 |
22 40 43 59 |
71 75 85 88 |
2 4 13 14 |
18 22 29 40 |
43 43 55 59 |
71 75 85 88 |
Табл. 3