Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Параллельные методы умножения матрицы на вектор
Раздел: Рефераты по информатике
Тип: реферат Добавлен 13:04:43 10 сентября 2011 Похожие работы
Просмотров: 306 Комментариев: 12 Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать

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

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

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

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

( лаба №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. График зависимости экспериментального и теоретического времени выполнения параллельного алгоритма от объема исходных данных при использовании двух потоков (ленточное разбиение матрицы по строкам)

ВЫВОД:

Замедление работы программы при использовании параллельного алгоритма (библиотека OpenMP) можно объяснить следующим отчётом профилировщика (см. Рисунок 6).

Рисунок 6. Сравнение данных профилировщика последовательной и параллельной программ

Как видно, значительное время при выполнении программы затрачивается в библиотеке libiomp 5 md . dll .

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

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

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

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

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

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

Таким образом, время выполнения параллельного алгоритма умножения матрицы на вектор, основанного на вертикальном разделении матрицы, может быть вычислено по формуле:

.

void ParallelResultCalculation_columns(double* pMatrix, double* pVector, double* pResult, int Size) {

int i, j; // Loop variables

double IterGlobalSum = 0;

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

IterGlobalSum = 0;

#pragma omp parallel for reduction(+:IterGlobalSum)

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

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

pResult[i] = IterGlobalSum;

}

}

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

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

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

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

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

Будем минимизировать величину

Таким образом, получаем = 5,27565E-06 с=5,3 мкс

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

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

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

После перемножения блоков матрицы A и вектора b каждая подзадача (i,j) будет содержать вектор частичных результатов c'(i,j), определяемый в соответствии с выражениями:

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

Будем предполагать, что число блоков матрицы А совпадает по горизонтали и вертикали, т.е. s=q.

Для обозначения числа потоков будем использовать переменную π=q2 . Для эффективного выполнения алгоритма число базовых подзадач должно совпадать с числом выделенных потоков.

Возьмём число потоков π=4.

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

Для задания количества потоков будет использоваться переменная NestedThreadsNum.

void ParallelResultCalculation_blocks(double* pMatrix, double* pVector, double* pResult,

int Size) {

int NestedThreadsNum = 2;

omp_set_num_threads(NestedThreadsNum);

omp_set_nested(true);

#pragma omp parallel for

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

double ThreadResult = 0;

#pragma omp parallel for reduction(+:ThreadResult)

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

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

pResult[i] = ThreadResult;

}

}

При анализе эффективности данного алгоритма воспользуемся следующими формулами.

Время выполнения вычислений ограничено сверху величиной: (количество вычислительных элементов совпадает с числом потоков, т.е. p=π)

При выполнении вычислений, «внутренние» параллельные секции создаются и закрываются много раз, кроме того, дополнительное время тратится на синхронизацию и выполнение операции редукции. Каждый поток создаёт параллельные секции раз. Время выполнения алгоритма может быть вычислено по формуле:

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

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

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

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

Вывод

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита16:36:22 05 ноября 2021
.
.16:36:20 05 ноября 2021
.
.16:36:19 05 ноября 2021
.
.16:36:18 05 ноября 2021
.
.16:36:16 05 ноября 2021

Смотреть все комментарии (12)
Работы, похожие на Реферат: Параллельные методы умножения матрицы на вектор

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(294170)
Комментарии (4230)
Copyright © 2005-2022 BestReferat.ru support@bestreferat.ru реклама на сайте

Рейтинг@Mail.ru