Н., Пескова Е. Е., Шаманаев П. А. Основы параллельного программирования с использованием технологий mpi и openmp учебное пособие саранск издательство свмо 2013 2
Алгоритм умножения матрицы на вектор
жүктеу/скачать 6.58 Mb. Pdf көрінісі
|
| 2.7.2 Алгоритм умножения матрицы на вектор
Для многих методов матричных вычислений характерным является повторение одних и тех же вычислительных действий для разных элементов матриц. Данное свойство свидетельствует о наличии параллелизма по данным при выполнении матричных расчетов, и, как результат, распараллеливание матричных операций сводится в большинстве случаев к разделению обрабатываемых матриц между процессорами используемой вычислительной системы. Выбор способа разделения матриц приводит к определению конкретного метода параллельных вычислений; существование разных схем распределения данных порождает целый ряд параллельных алгоритмов матричных вычислений. Наиболее общие и широко используемые способы разделения матриц состоят в разбиении данных на полосы (по вертикали или горизонтали) или на прямоугольные фрагменты (блоки). Рис. 2.5. Варианты разбиения данных матрицы Рассмотрим подробнее вариант разбиения данных на полосы (ленточное разбиение). При ленточном (block-striped) разбиении каждому процессору выделяется то или иное подмножество строк (rowwise или горизонтальное разбиение) или столбцов (columnwise или вертикальное разбиение) матрицы. Разделение строк и столбцов на полосы в большинстве случаев происходит на непрерывной (последовательной) основе. При таком подходе для горизонтального разбиения по строкам, например, матрица представляется в виде где , есть -я строка матрицы (предполагается, что количество строк m кратно числу процессоров p, т.е. ). Здесь применяется разделение данных на непрерывной основе. Другой возможный подход к формированию полос состоит в применении той или иной схемы чередования (цикличности) строк или 31 столбцов. Как правило, для чередования используется число процессоров p – в этом случае при горизонтальном разбиении матрица принимает вид В результате умножения матрицы A размерности n m и вектора b , состоящего из n элементов, получается вектор c размера m , каждый i -й элемент которого есть результат скалярного умножения i -й строки матрицы A (обозначим эту строчку ) и вектора : . Тем самым получение результирующего вектора c предполагает повторение m однотипных операций по умножению строк матрицы A и вектора b . Последовательный алгоритм умножения матрицы на вектор может быть представлен следующим образом. for (i = 0; i < m; i++){ c[i] = 0; for (j = 0; j < n; j++){ c[i] += A[i][j]*b[j] }} Рассмотрим алгоритм умножения матрицы на вектор, основанный на представлении матрицы непрерывными наборами (горизонтальными полосами) строк. При таком способе разделения данных в качестве базовой подзадачи может быть выбрана операция скалярного умножения одной строки матрицы на вектор. Для выполнения базовой подзадачи скалярного произведения процессор должен содержать соответствующую строку матрицы A и копию вектора b . После завершения вычислений каждая базовая подзадача определяет один из элементов вектора результата c . Для объединения результатов расчета и получения полного вектора c на каждом из процессоров вычислительной системы необходимо выполнить операцию обобщенного сбора данных, в которой каждый процессор передает свой вычисленный элемент вектора c всем остальным процессорам. В общем виде схема информационного взаимодействия подзадач в ходе выполняемых вычислений показана на рисунке 2.6. 32 Рис. 2.6. Схема взаимодействия подзадач В процессе умножения матрицы на вектор количество вычислительных операций для получения скалярного произведения одинаково для всех базовых подзадач. Поэтому в случае, когда число процессоров p меньше числа базовых подзадач m , мы можем объединить базовые подзадачи таким образом, чтобы каждый процессор выполнял несколько таких задач, соответствующих непрерывной последовательности строк матрицы A . В этом случае по окончании вычислений каждая базовая подзадача определяет набор элементов результирующего вектора c [5,10]. жүктеу/скачать 6.58 Mb. Достарыңызбен бөлісу:
|