- •(Вопросы 34-40) содержание
- •5.2. Введение в разработку параллельных программ с использованием mpi
- •5.3. Операции передачи данных между двумя процессами
- •5.1. Mpi: основные понятия и определения
- •5.1.1. Понятие параллельной программы
- •5.1.2. Операции передачи данных
- •5.1.3. Понятие коммуникаторов
- •5.1.4. Типы данных
- •5.1.5. Виртуальные топологии
- •5.2. Введение в разработку параллельных программ с использованием mpi
- •5.2.1. Основы mpi
- •5.2.1.1. Инициализация и завершение mpi-программ
- •5.2.1.2. Определение количества и ранга процессов
- •5.2.1.3. Передача сообщений
- •5.2.1.4. Прием сообщений
- •5.2.1.5. Первая параллельная программа с использованием mpi
- •5.2.2. Определение времени выполнение mpi-программы
- •5.2.3. Начальное знакомство с коллективными операциями передачи данных
- •5.2.3.1. Передача данных от одного процесса всем процессам программы
- •5.2.3.2. Передача данных от всех процессов одному процессу. Операция редукции
- •5.2.3.3. Синхронизация вычислений
- •5.2.3.4. Аварийное завершение параллельной программы
- •5.3. Операции передачи данных между двумя процессами
- •5.3.1. Режимы передачи данных
- •5.3.2. Организация неблокирующих обменов данными между процессами
- •5.3.3. Одновременное выполнение передачи и приема
- •5.4. Коллективные операции передачи данных
- •5.4.1. Обобщенная передача данных от одного процесса всем процессам
- •5.4.2. Обобщенная передача данных от всех процессов одному процессу
- •5.4.3. Общая передача данных от всех процессов всем процессам
- •5.4.4. Дополнительные операции редукции данных
- •5.4.5. Сводный перечень коллективных операций данных
- •5.5. Производные типы данных в mpi
- •5.5.1. Понятие производного типа данных
- •5.5.2. Способы конструирования производных типов данных
- •5.5.2.1. Непрерывный способ конструирования
- •5.5.2.2. Векторный способ конструирования
- •5.5.2.3. Индексный способ конструирования
- •5.5.2.4. Структурный способ конструирования
- •5.5.3. Объявление производных типов и их удаление
- •5.5.4. Формирование сообщений при помощи упаковки и распаковки данных
- •5.6. Управление группами процессов и коммуникаторами
- •5.6.1. Управление группами
- •5.6.2. Управление коммуникаторами
- •5.7. Виртуальные топологии
- •5.7.1. Декартовы топологии (решетки)
- •5.7.2. Топологии графа
- •5.8. Дополнительные сведения о mpi
- •5.8.1. Разработка параллельных программ с использованием mpi на алгоритмическом языке Fortran
- •5.8.2. Общая характеристика среды выполнения mpi-программ
- •5.8.3. Дополнительные возможности стандарта mpi-2
- •5.9. Краткий обзор лекции
- •6. Параллельные методы умножения матрицы на вектор
- •6.1. Принципы распараллеливания
- •6.2. Постановка задачи
- •6.3. Последовательный алгоритм
- •6.4. Разделение данных
- •6.5. Умножение матрицы на вектор при разделении данных по строкам
- •6.5.1. Выделение информационных зависимостей
- •6.5.2. Масштабирование и распределение подзадач по процессорам
- •6.5.3. Анализ эффективности
- •6.5.4. Программная реализация
- •6.5.5. Результаты вычислительных экспериментов
- •6.6. Умножение матрицы на вектор при разделении данных по столбцам
- •6.6.1. Определение подзадач и выделение информационных зависимостей
- •6.6.2. Масштабирование и распределение подзадач по процессорам
- •6.6.3. Анализ эффективности
- •6.6.4. Результаты вычислительных экспериментов
- •6.7. Умножение матрицы на вектор при блочном разделении данных
- •6.7.1. Определение подзадач
- •6.7.2. Выделение информационных зависимостей
- •6.7.3. Масштабирование и распределение подзадач по процессорам
- •6.7.4. Анализ эффективности
- •6.7.5. Результаты вычислительных экспериментов
- •6.8. Краткий обзор лекции
6.7.4. Анализ эффективности
Выполним анализ эффективностипараллельного алгоритма умножения матрицы на вектор при обычных уже предположениях, что матрицаАявляется квадратной, т.е.m=n. Будем предполагать также, что процессоры, составляющие многопроцессорную вычислительную систему, образуют прямоугольную решеткуp=s×q(s– количество строк в процессорной решетке,q– количество столбцов).
Общий анализ эффективностиприводит к идеальным показателям параллельного алгоритма:
(6.16) |
Для уточнения полученных соотношений оценим более точно количество вычислительных операций алгоритма и учтем затраты на выполнение операций передачи данных между процессорами.
Общее время умножения блоков матрицы Аи вектораbможет быть определено как
(6.17) |
Операция редукции данных может быть выполнена с использованием каскадной схемы и включает, тем самым, log2qитераций передачи сообщений размера. Как результат, оценка коммуникационных затрат параллельного алгоритма при использовании модели Хокни может быть определена при помощи следующего выражения
(6.18) |
Таким образом, общее время выполнения параллельного алгоритма умножения матрицы на вектор при блочном разделении данных составляет
(6.19) |
6.7.5. Результаты вычислительных экспериментов
Вычислительные экспериментыдля оценкиэффективностипараллельного алгоритма проводились при тех же условиях, что и ранее выполненные расчеты (см. п. 6.5.5). Результаты экспериментов приведены втаблице 6.5. Вычисления проводились с использованием четырех и девяти процессоров.
Сравнение экспериментального времени выполнения эксперимента и теоретического времениT p, вычисленного в соответствии с выражением (6.19), представлено втаблице 6.5и нарис. 6.10.
Таблица 6.5. Результаты вычислительных экспериментов по исследованию параллельного алгоритма умножения матрицы на вектор при блочном разделении данных | |||||
Размер матриц |
Последовательный алгоритм |
Параллельный алгоритм | |||
4 процессора |
9 процессоров | ||||
Время |
Ускорение |
Время |
Ускорение | ||
1000 |
0,0041 |
0,0028 |
1,4260 |
0,0011 |
3,7998 |
2000 |
0,016 |
0,0099 |
1,6127 |
0,0095 |
3,2614 |
3000 |
0,031 |
0,0214 |
1,4441 |
0,0095 |
3,2614 |
4000 |
0,062 |
0,0381 |
1,6254 |
0,0175 |
3,5420 |
5000 |
0,11 |
0,0583 |
1,8860 |
0,0263 |
4,1755 |
Рис. 6.9. Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма умножения матрицы на вектор (блочное разбиение матрицы) для разных размеров матриц
Таблица 6.5. Сравнение экспериментального и теоретического времени выполнения параллельного алгоритма умножения матрицы на вектор при блочном разделении данных | ||||
Размер матриц |
Последовательный алгоритм |
Параллельный алгоритм | ||
1000 |
0,0025 |
0,0028 |
0,0012 |
0,0011 |
2000 |
0,0095 |
0,0099 |
0,0043 |
0,0042 |
3000 |
0,0212 |
0,0214 |
0,0095 |
0,0095 |
4000 |
0,0376 |
0,0381 |
0,0168 |
0,0175 |
5000 |
0,0586 |
0,0583 |
0,0262 |
0,0263 |
Рис. 6.10. График зависимости экспериментального и теоретического времени проведения эксперимента на четырех процессорах от объема исходных данных (блочное разбиение матрицы)