- •(Вопросы 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.2. Постановка задачи
В результате умножения матрицы Аразмерностиm × nи вектораb, состоящего изnэлементов, получается векторcразмераm, каждыйi-й элемент которого есть результат скалярного умноженияi-й строки матрицыА(обозначим эту строчкуai) и вектораb:
(6.4) |
Тем самым получение результирующего вектора cпредполагает повторениеmоднотипных операций по умножению строк матрицыAи вектораb. Каждая такая операция включает умножение элементов строки матрицы и вектораb(nопераций) и последующее суммирование полученных произведений (n-1операций). Общее количество необходимых скалярных операций есть величина
T1=m·(2n-1)
6.3. Последовательный алгоритм
Последовательный алгоритм умножения матрицы на вектор может быть представлен следующим образом.
Алгоритм 6.1. Последовательный алгоритм умножения матрицы на вектор
// Алгоритм 6.1
// Поcледовательный алгоритм умножения матрицы на вектор
for (i = 0; i < m; i++){
c[i] = 0;
for (j = 0; j < n; j++){
c[i] += A[i][j]*b[j]
}
}
Матрично-векторное умножение – это последовательность вычисления скалярных произведений. Поскольку каждое вычисление скалярного произведения векторов длины nтребует выполненияnопераций умножения иn-1операций сложения, его трудоемкость порядкаO(n). Для выполнения матрично-векторного умножения необходимо осуществитьmопераций вычисления скалярного произведения, таким образом, алгоритм имеет трудоемкость порядкаO(mn).
6.4. Разделение данных
При выполнении параллельных алгоритмов умножения матрицы на вектор, кроме матрицы А, необходимо разделить еще векторbи вектор результатаc. Элементы векторов можнопродублировать, то есть скопировать все элементы вектора на все процессоры, составляющие многопроцессорную вычислительную систему, или разделить между процессорами. Приблочномразбиении вектора изnэлементов каждый процессор обрабатывает непрерывную последовательность изkэлементов вектора (мы предполагаем, что размерность вектораnнацело делится на число процессоров, т.е.n= k·p).
Поясним, почему дублирование векторов bиcмежду процессорами является допустимым решением (далее для простоты изложения будем полагать, чтоm=n). Векторыbиссостоят изnэлементов, т.е. содержат столько же данных, сколько и одна строка или один столбец матрицы. Если процессор хранит строку или столбец матрицы и одиночные элементы векторовbис, то общее число сохраняемых элементов имеет порядокO(n). Если процессор хранит строку (столбец) матрицы и все элементы векторовbис, то общее число сохраняемых элементов также порядкаO(n). Таким образом, при дублировании и при разделении векторов требования к объему памяти из одного класса сложности.
6.5. Умножение матрицы на вектор при разделении данных по строкам
Рассмотрим в качестве первого примера организации параллельных матричных вычислений алгоритм умножения матрицы на вектор, основанный на представлении матрицы непрерывными наборами (горизонтальными полосами) строк. При таком способе разделения данных в качестве базовой подзадачи может быть выбрана операция скалярного умножения одной строки матрицы на вектор.
6.5.1. Выделение информационных зависимостей
Для выполнения базовой подзадачи скалярного произведения процессор должен содержать соответствующую строку матрицы Аи копию вектораb. После завершения вычислений каждая базовая подзадача определяет один из элементов вектора результатаc.
Для объединения результатов расчета и получения полного вектора c на каждом из процессоров вычислительной системы необходимо выполнить операцию обобщенного сбора данных (см. лекцию 4), в которой каждый процессор передает свой вычисленный элемент вектораcвсем остальным процессорам. Этот шаг можно выполнить, например, с использованием функцииMPI_Allgatherиз библиотекиMPI.
В общем виде схема информационного взаимодействия подзадач в ходе выполняемых вычислений показана на рис. 6.2.
Рис. 6.2. Организация вычислений при выполнении параллельного алгоритма умножения матрицы на вектор, основанного на разделении матрицы по строкам