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




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

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

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




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



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





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


Тема:

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

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

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

Орлов Л. М.

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

Оглавление


Отчет по лабораторной работе 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).

https://lh6.googleusercontent.com/0g6ue7agfiw99rhe9ihq2qdt4kj3lnd093jyvpkh2qsjiatjsphsx5m6jlan4ddzodeep9iaynqiykwny0e363xhmmszshwox9pqygcg8ryxdkdn0xo

Рис.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 (int i = 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.

c:\users\orlov.leonid\desktop\pne5.png

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

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

c:\users\orlov.leonid\desktop\l7ah.png

Рис.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Отчет по лабораторной работе Отчет представляет собой таблицу вида
В первом окне выводятся различные элементы управления (RadioButton, CheckBox, MaskEdit – в соответствии с заданием)

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» iconОтчет по лабораторной работе №2 Ревизия
Лабораторная работа Разработка многопроцессного приложения для анализа логов web-сервера 5

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» iconОтчёт По лабораторной работе №1 По курсу «Основы проектирования систем...
Экспертные системы вместе с системами обработки естественных языков являются наиболее важными в коммерческом плане областями использования...

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» iconОтчет по лабораторной работе №1 по предмету «Экономико-математические...
Предложения (рекомендации) лицу, ответственному за принятие решений, по оптимальному управленческому поведению 6

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» iconМетодические указания к выполнению лабораторной работе «решение систем...
В ряде практических задач управления и оптимизации приходится решать системы линейных алгебраических уравнений (слу). В настоящей...

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» iconОтчет по лабораторной работе по дисциплине "Технологии программирования"...
Пояснительная записка: с., 22 рис., 17 табл., 11 библиограф источников, 2 приложения

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» iconУрок математики во 2-м классе "Умножение числа Умножение на 2"
Повторить понятие умножения (что умножение есть сумма одинаковых слагаемых), переместительное свойство умножения

Отчет по лабораторной работе Тема: «Умножение разреженных матриц» iconОтчёт по лабораторной работе №4 по курсу «Безопасность программ и...
В качестве симметричного алгоритма используется алгоритм des с режимом шифрования cbc



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница