- •(Вопросы 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.6.4. Результаты вычислительных экспериментов
Вычислительные экспериментыдля оценкиэффективностипараллельного алгоритма умножения матрицы на вектор при разбиении данных по столбцам проводились при условиях, указанных в п. 6.5.5. Результатывычислительных экспериментовприведены втаблице 6.3.
Таблица 6.3. Результаты вычислительных экспериментов по исследованию параллельного алгоритма умножения матрицы на вектор, основанного на разбиении матрицы по столбцам | |||||||
Размер матрицы |
Последовательный алгоритм |
Параллельный алгоритм | |||||
2 процессора |
4 процессора |
8 процессоров | |||||
Время |
Ускорение |
Время |
Ускорение |
Время |
Ускорение | ||
1000 |
0,0041 |
0,0022 |
1,8352 |
0,0015 |
3,1538 |
0,0008 |
4,9409 |
2000 |
0,016 |
0,0085 |
1,8799 |
0,0046 |
3,4246 |
0,0029 |
5,4682 |
3000 |
0,031 |
0,019 |
1,6315 |
0,0095 |
3,2413 |
0,0055 |
5,5456 |
4000 |
0,062 |
0,0331 |
1,8679 |
0,0168 |
3,6714 |
0,0090 |
6,8599 |
5000 |
0,11 |
0,0518 |
2,1228 |
0,0265 |
4,1361 |
0,0136 |
8,0580 |
Сравнение экспериментального времени выполнения эксперимента и времениTp, вычисленного по соотношениям (6.14), (6.15), представлено втаблице 6.4и на рис.6.6и6.7. Теоретическое времявычисляется согласно (6.14), а теоретическое время– в соответствии с (6.15).
Рис. 6.6. График зависимости теоретического и экспериментального времени выполнения параллельного алгоритма на четырех процессорах от объема исходных данных (ленточное разбиение матрицы по столбцам)
Таблица 6.4. Сравнение экспериментального и теоретического времени выполнения параллельного алгоритма умножения матрицы на вектор, основанного на разбиении матрицы по столбцам | |||||||||
Размер матрицы |
2 процессора |
4 процессора |
8 процессоров | ||||||
1000 |
0,0022 |
0,0021 |
0,0021 |
0,0013 |
0,0013 |
0,0014 |
0,0008 |
0,0011 |
0,0015 |
2000 |
0,0085 |
0,0082 |
0,0080 |
0,0046 |
0,0044 |
0,0044 |
0,0029 |
0,0027 |
0,0031 |
3000 |
0,019 |
0,0177 |
0,0177 |
0,0095 |
0,0094 |
0,0094 |
0,0055 |
0,0054 |
0,0056 |
4000 |
0,0331 |
0,0313 |
0,0313 |
0,0168 |
0,0163 |
0,0162 |
0,0090 |
0,0090 |
0,0091 |
5000 |
0,0518 |
0,0487 |
0,0487 |
0,0265 |
0,0251 |
0,0251 |
0,0136 |
0,0135 |
0,0136 |
Рис. 6.7. Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма умножения матрицы на вектор (ленточное разбиение матрицы по столбцам) для разных размеров матриц
6.7. Умножение матрицы на вектор при блочном разделении данных
Рассмотрим теперь параллельный алгоритм умножения матрицы на вектор, который основан на ином способе разделения данных – на разбиении матрицы на прямоугольные фрагменты (блоки).
6.7.1. Определение подзадач
Блочная схема разбиения матриц подробно рассмотрена в подразделе 6.1. При таком способе разделения данных исходная матрица Aпредставляется в виде набора прямоугольных блоков:
где Aij, 0i<s, 0j<q, есть блок матрицы:
(здесь, как и ранее, предполагается, что p=s·q, количество строк матрицы является кратным s, а количество столбцов – кратным q, то есть m=k·s и n=l·q).
При использовании блочного представления матрицы Aбазовые подзадачи целесообразно определить на основе вычислений, выполняемых над матричными блоками. Для нумерации подзадач могут применяться индексы располагаемых в подзадачах блоков матрицыA, т.е. подзадача(i,j)содержит блокAij. Помимо блока матрицыAкаждая подзадача должна содержать также и блок вектораb. При этом для блоков одной и той же подзадачи должны соблюдаться определенные правила соответствия – операция умножения блока матрицыA ijможет быть выполнена только, если блок вектораb'(i,j) имеет вид