Параллельные методы умножения матрицы на вектор (стр. 1 из 2)

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО “ПЕРМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”

Кафедра прикладной математики и информатики

Параллельные методы умножения матрицы на вектор

(лаба №1)

Выполнили студенты 1 курса магистратуры,

группы ПМИ

механико-математического факультета

Габдуллин Артём _______________

Моисеенков Максим_____________Нурбакова Диана _______________

Принял:

доцент кафедры прикладной

математики и информатики ПГУ,

к.ф.-м.н., доц.

Деменев А.Г.____________________________

Пермь 2010

Цель лабораторной работы.

Реализация последовательного и параллельных алгоритмов умножения матрицы на вектор при использовании 2-х ядерной вычислительной системы с общей памятью.

Постановка задачи.

В результате умножения матрицы

и вектора , получается вектор , каждый i-ый элемент которого есть результат скалярного умножения i-й строки матрицы (обозначим эту строчку ) и вектора .

Тем самым получение результирующего вектора

предполагает повторение однотипных операций по умножению строк матрицы и вектора . Каждая такая операция включает умножение элементов строки матрицы и вектора ( операций) и последующее суммирование полученных произведений ( операций).

Общее количество необходимых скалярных операций есть величина

.

Поcледовательный алгоритм умножения матрицы на вектор

void SerialResultCalculation(double* pMatrix, double* pVector,

double* pResult, int Size) {

int i, j; // Loop variables

for (i=0; i<Size; i++) {

pResult[i]=0;

for (j=0; j<Size; j++)

pResult[i] += pMatrix[i*Size+j]*pVector[j];

}

}

Умножение матрицы на вектор при разделении данных по строкам.

Базовая подзадача - скалярное умножение одной строки матрицы на вектор. После завершения вычислений каждая базовая подзадача определяет один из элементов вектора результата c.

В общем виде схема информационного взаимодействия подзадач в ходе выполняемых вычислений показана на рис.1. Количество вычислительных операций для получения скалярного произведения одинаково для всех базовых подзадач.

Рисунок 1. Организация вычислений при выполнении параллельного алгоритма умножения матрицы на вектор, основанного на разделении матрицы по строкам.

Каждый поток параллельной программы использует только «свои» данные, ему не требуются данные, которые в данный момент обрабатывает другой поток, нет обмена данными между потоками, не возникает необходимости синхронизации. Т.е. практически нет накладных расходов на организацию параллелизма (за исключением расходов на организацию и закрытие параллельной секции), и можно ожидать линейного ускорения. Однако, как будет видно из представленных результатов, ускорение далеко от линейного.

Время решения задачи одним потоком складывается из времени, когда процессор непосредственно выполняет вычисления, и времени, которое тратится на чтение необходимых для вычислений данных из ОП в кэш. При этом время, необходимое на чтение данных, может в несколько раз превосходить время счета.

Процесс выполнения последовательного алгоритма умножения матрицы на вектор может быть представлен диаграммой, изображенной на рис.2.

Рисунок 2. Диаграмма состояний процесса выполнения последовательного алгоритма

умножения матрицы на вектор.

Время выполнения последовательного алгоритма складывается из времени вычислений и времени доступа к памяти:

, где - это количество выполненных операций, - время выполнения одной операции, - размерность матрицы.

, где - объем данных, которые необходимо закачать в кэш процессора, - скорость доступа (пропускная способность канала доступа) ОП.

Таким образом,

.

Для оценки

, измерим время выполнения последовательного алгоритма при
, т.к. матрица и вектор полностью поместятся в кэш ВЭ. (У нас размер кэш равен 2048 кбайт, поэтому ). Чтобы исключить необходимость выборки данных из ОП, перед началом вычислений заполним матрицу и вектор случайными числами – выполнение этого действия гарантирует закачку данных в кэш. Далее при решении задачи все время будет тратиться на вычисления, так как нет необходимости загружать данные из ОП.

Получим

0,00000308.

Тогда

Теперь, оценим

при : 8 121 537 238,29

В таблице 1 и на рис.3 представлено сравнение реального времени последовательного алгоритма умножения матрицы на вектор и теоретического.

Таблица 1. Сравнение экспериментального и теоретического времени выполнения последовательного

алгоритма умножения матрицы на вектор.

Рисунок 3. График зависимости экспериментального и теоретического времени выполнения последовательного алгоритма от объема исходных данных (ленточное разбиение матрицы по строкам

В многоядерных процессорах Intel архитектуры Core 2 Duo ядра процессоров разделяют общий канал доступа к памяти. Т.е., несмотря на то, что вычисления могут выполняться ядрами параллельно, доступ к памяти осуществляется строго последовательно. Следовательно, время

выполнения параллельного алгоритма в системе с вычислительными элементами, с использованием потоков и при описанной выше схеме доступа к памяти может быть оценено при помощи следующего соотношения: .

void ParallelResultCalculation_rows (double* pMatrix, double* pVector,

double* pResult, int Size) {

int i, j; // Loop variables

#pragma omp parallel private (i,j)

#pragma omp for

for (i=0; i<Size; i++) {

for (j=0; j<Size; j++)

pResult[i] += pMatrix[i*Size+j]*pVector[j];

}

}

Результаты вычислительных экспериментов приведены в таблице 2. Времена выполнения алгоритмов указаны в секундах.

Ускорение есть результат деления времени работы последовательного алгоритма на время работы параллельного.

Таблица 2. Результаты вычислительных экспериментов для параллельного алгоритма умножения

матрицы на вектор при ленточной схеме разделении данных по строкам.

Рисунок 4. Зависимость ускорения от количества исходных данных при выполнении параллельного алгоритма умножения матрицы на вектор, основанного на ленточном горизонтальном разбиении матрицы

Рисунок 5. График зависимости экспериментального и теоретического времени выполнения параллельного алгоритма от объема исходных данных при использовании двух потоков (ленточное разбиение матрицы по строкам)