Отчет по лабораторной работе Тема: «Умножение разреженных матриц»




Скачать 85.42 Kb.
Название Отчет по лабораторной работе Тема: «Умножение разреженных матриц»
Дата публикации 14.05.2014
Размер 85.42 Kb.
Тип Отчет
literature-edu.ru > Информатика > Отчет
Министерство образования и науки

Государственное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет
им. Н.И. Лобачевского»

Факультет вычислительной математики и кибернетики




Кафедра: Математического обеспечения ЭВМ



Направление: Информационные технологии





Отчет по лабораторной работе


Тема:

«Умножение разреженных матриц»


Выполнили:

студентыгруппы 85М21

Леденцов Д. К.

Орлов Л. М.
Проверил:

Доцент кафедры МО ЭВМ

Мееров И. Б.

Нижний Новгород
2011

Оглавление


Отчет по лабораторной работе 1

Введение 3

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

Описание алгоритма 5

Параллельная реализация 8

Полученные результаты 10

Заключение 12

Литература 13


Введение


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

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

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


В ходе выполнения лабораторной работы необходимо реализовать умножение разреженных матриц. При этом матрицы должны храниться в разреженном столбцовом формате. Изначально требуется реализовать последовательный вариант алгоритма умножения на языке С++. Далее необходимо разработать параллельную версию алгоритма и реализовать ее с помощью программно-аппаратной платформы CUDA на  CUDA C - расширении языка C. В завершении работы должны быть приведены полученные результаты и заключение.

Описание алгоритма


Для хранения разреженных матриц используется так называемый разреженный столбцовый формат, широко известным как CSS (Compressed Column Storage) или CSC (Compressed Sparse Columns). В таком формате матрица хранится в виде трех массивов:

  • Массив значений Value (построчно, сверху вниз);

  • Массив номеров строк Row;

  • Массив индексов начала столбцов ColIndex.

При таком хранении ColIndex[j] указывает на начало j-го столбца в массивах Value и Row, а элементы этого столбца находятся по индексам от ColIndex[j] до ColIndex[j+1]–1 включительно. При этом довольно просто обрабатываются пустые столбцы, для которых ColIndex[j] = ColIndex[j+1]. Для последнего столбца полагается ColIndex[N+1] = NZ, где N - размер матрицы, а NZ - число ненулевых элементов.

Для хранения матрицы N*N с NZ ненулевыми элементами в итоге нам потребуется 8NZ+4NZ+4(N+1) = 12NZ+4N+4 байт, если для хранения значений элементов мы будем использовать 8 байт, а для индексов - 4 байта. Это конечно много меньше N^2 как если бы мы использовали плотный формат.

Ниже представлен пример хранения для матрицы A (6*6).



Рис.1. Столбцовый формат хранения разреженной матрицы

Формат CSS предоставляет быстрый доступ к столбцам, при этом столбцы рассматриваются по порядку, хотя внутри них элементы могут быть, как упорядочены, так и нет. В первом случае достигается быстрый поиск элементов, хотя приходится “платить” за поддержание такой упорядоченности. Во втором же случае ничего поддерживать не надо, но зато поиск осуществляется лишь перебором. Существует также модификация CSS с четырьмя массивами, где последний массив хранит индексы элементов, идущих в конце столбца. Столбцы тогда могут не быть упорядочены, а их перестановка проводится без перепаковки путем изменения индексов. Данная модификация в лабораторной работе не используется.

Для реализации умножения нужно, прежде всего, реализовать транспонирование матрицы. Пусть имеется разреженная матрица A(N*N) в формате CSS. Чтобы получить AT в формате CSS необходимо:

  • сформировать N«целых» и N«вещественных» векторов;

  • в цикле просмотреть все столбцы исходной матрицы, для каждого столбца - все его элементы;

  • если A[i][j] = v, тогда добавить числа i и v в j-ые «целый» и «вещественный» вектор, тем самым в векторах сформируются столбцы транспонированной матрицы;

  • скопировать данные из векторов в CSS-структуру транспонированной матрицы (Row и Value), попутно формируя массив ColIndex.

Теперь можно непосредственно выполнять умножение. Алгоритм умножение разреженных матриц A и B в форматах CSS состоит в следующем:

  • транспонировать матрицу A, т.е. вычислить AT;

  • инициализировать структуру данных для матрицы C = A*B;

  • последовательно перемножить каждый столбец матрицы AT на каждую из строк матрицы B, записывая в C полученные результаты и формируя ее структуру.

При умножении столбцов возникает задача сопоставления с целью выделения пар ненулевых элементов. В простейшем варианте это решается простым перебором для каждого элемента столбца матрицы AT элементов столбца матрицы B до тех пор, пока не будет найден элемент с таким же значением в массиве Row или не закончится строка. Хотя это излишне, ведь вектора упорядочены! Для решения проблемы достаточно:

  • встать на начало обоих векторов (ks= …, ls= …);

  • сравнить текущие элементы AT.Row[ks]и B.Row[ls];

  • если значения совпадают, просуммировать AT.Value[ks] * B.Value[ls] и увеличить оба индекса, в противном случае – увеличить один из индексов, в зависимости от того, какое значение больше.


Этого можно добиться, написав приблизительно следующее:

ks:=AT.ColIndex[i]; kf:=AT.ColIndex[i + 1] -1

ls:= B.ColIndex[j]; lf:= B.ColIndex[j + 1] -1

while ((ks <= kf) && (ls <= lf))

if AT.Row[ks]

else if AT.Row[ks]>B.Row[ls] then ls:=ls+1;

else sum:=sum + AT.Value[ks]*B.Value[ls];

ks:=ks+1;ls:=ls+1;

endif;

endif

endwile

Параллельная реализация


Предположим, что нам нужно умножить две разреженные матрицы размера N*N, которые хранятся в столбцовом формате.

C = A * B

Для этого сначала нужно транспонировать матрицу A, а затем перемножить столбцы транспонированной матрицы Aна столбцы матрицы B.

Транспонирование

Для хранения матрицы A в столбцовом формате используются следующие данные:

  • массив value– ненулевые элементы матрицы;

  • массив row – номера строк ненулевых элементов;

  • массив colIndex – индекс первых элементов для каждого столбца.

Для реализации параллельной версии алгоритма транспонирования необходимо завести вспомогательный массив data размера N*N и проинициализировать его нулями. В данный массив будем записывать элементы транспонированной матрицы.Также создадим три массива valueT, rowT, colIndexT – соответствующие массивы транспонированной матрицы.

Создадим Nпотоков. Каждый J-ый поток находит все ненулевые элементы в J-ом столбце матрицы Aи записывает их в массив data.

for (int i=colIndex[i]; i

{

data[J * N + row[i]] = value[i]

}

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

int t;

int sum = 0;

for (inti =0; I <=N; i++) {

t = colIndexT[i];

colIndexT[i] = sum;

sum += t;

}

На последнем шаге необходимо сформировать массивы valueT иrowT. Для этого каждый поток перебирает все элементы в своем столбце транспонированной матрицы, вычисляет их индекс по формуле:

n = colIndex[J] + c, гдеc–номер элемента в соответствующем столбце;

и записывает в n-ые элементы массивов valueTи rowTсам элемент и номер строки. После этого транспонированная матрица Aсформирована.

Умножение

Имеется транспонированная матрица Aи матрица B, которые хранятся в столбцовом формате. Чтобы реализовать параллельный алгоритм их умножения, необходимо создать N*Nпотоков (N–размер матриц). Каждый поток будет считать соответствующий элемент матрицы С. Для этого нужно скалярно умножить I-ый столбец транспонированной матрицы Aна J-ый столбец транспонированной матрицы B.

Полученные результаты


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

  1. CPU–Intel(R) Core(TM) Quad 2.4 GHz

  2. RAM– 4 GB

  3. GPU – NVidia GeForce 8600GT

  4. OS–Windows Seven

На Рис.2. представлен график времени работы каждого варианта алгоритма для соответствующих размеров. Время указано в секундах. Размер перемножаемых матриц меняется от 128 до 2048.



Рис.2. Время работы последовательной и параллельной версий алгоритма

Ускорение, соответствующее каждому размеру перемножаемых матриц приведено на Рис.3.



Рис.3. Ускорение параллельной версии

Заключение


В ходе выполнения лабораторной работы был успешно реализован последовательный вариант алгоритма умножения разреженных матриц на языке С++; а также разработана и реализована параллельная версия алгоритма с помощью платформы CUDA. Для сравнительного анализа обеих версий была проведена серия экспериментов, которая показала, что с ростом размера перемножаемых матриц, время работы последовательного варианта “стремительно” растет, в то время каквремя работы параллельного варианта меняется несущественно. Для N=2048 ускорение практически достигает 100. Это говорит о том, что задача "хорошо” ложится под архитектуру графического процессора, а также, что реализация была проведена довольно успешно.

Литература


  1. Писсанецки С. Технология разреженных матриц.: Пер. с англ. - М.: Мир, 1988.

  2. Тьюарсон Р. Разреженные матрицы.: Пер. с англ.  М.: Мир, 1977.

  3. Боресков, А.В. Основы работы с технологией CUDA / А.В. Боресков, А.А. Харламов. – М.: ДМК Пресс, 2011. – 232 с

Интернет – ресурсы:

  1. Разреженные матрицы [http://en.wikipedia.org/wiki/Sparse_matrix]

  2. Технология CUDA [http://developer.nvidia.com/]

Добавить документ в свой блог или на сайт

Похожие:

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Отчет по лабораторной работе Тема: «Умножение разреженных матриц»
Государственное образовательное учреждение высшего профессионального образования Нижегородский государственный университет
Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Отчет по лабораторной работе Тема: «Умножение разреженных матриц»
Государственное образовательное учреждение высшего профессионального образования Нижегородский государственный университет
Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Отчет по лабораторной работе должен содержать следующие материалы...
Отчет по лабораторной работе должен содержать следующие материалы по каждой задаче
Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Методические указания к выполнению лабораторной работе «решение систем...
В ряде практических задач управления и оптимизации приходится решать системы линейных алгебраических уравнений (слу). В настоящей...
Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Отчет по лабораторной работе должен содержать следующие материалы...
Аналитическое решение тестового примера и результат вычислительного эксперимента по тесту
Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon «Умножение положительных и отрицательных чисел»
Цель урока: знать правила умножения чисел с разными знаками, умножение двух отрицательных чисел
Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Отчёт по воспитательной работе за 2012-13 учебный год
Школа ставит своей целью стать для ребёнка местом, в котором ему хорошо, комфортно и интересно каждому, поэтому мы в своей работе...
Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Отчет по итогам организации процесса воспитания в мбоу «сош№40»
Аналитический отчет заместителя директора по воспитательной работе по итогам организации процесса воспитания
Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Отчет о методической работе за 2012-2013 учебный год мбоу оош с. Старотатышево

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» icon Отчет о работе гоу спо «забайкальский техникум искусств» за 2012-2013 уч. Год
Дополнительное образование, маркетинг и связи с общественностью стр. 35
Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции