Скачать 86.08 Kb.
|
Содержание Постановка задачиОписание алгоритма Параллельная реализация A, а затем перемножить столбцы транспонированной матрицы A A сформирована.Умножение Полученные результаты |
Министерство образования и науки Государственное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского» Факультет вычислительной математики и кибернетикиКафедра: Математического обеспечения ЭВМНаправление: Информационные технологии Отчет по лабораторной работеТема: «Умножение разреженных матриц» Выполнили: студенты группы 85М21 Леденцов Д. К. Орлов Л. М. Нижний Новгород 2010 ОглавлениеОтчет по лабораторной работе 1 Введение 3 Постановка задачи 4 Описание алгоритма 5 Параллельная реализация 8 Полученные результаты 10 Заключение 12 Литература 13 ВведениеПо мере того, как растут производительность и быстродействие вычислительных машин, становится возможным обрабатывать все большего размера матрицы для различного типа задач. Например, обработка матриц необходимо при решении систем линейных уравнений. Но, несмотря на стремительное развитие вычислительной техники, по-прежнему, как и несколько десятков лет назад, основными характеристиками остаются: память, трудоемкость и быстродействие. С ростом порядка матричной задачи растет и стоимость ее решения, становясь решающим фактором. Разреженной матрицей называется матрица с большим числом ненулевых элементов. Для такой матрицы неэффективно хранить и обрабатывать все элементы. Поэтому существуют специальные форматы хранения данных матриц, позволяющие запоминать только ненулевые элементы. Но для каждого такого нового способа хранения необходимо разрабатывать методы для основных операций: умножение матрицы на число, транспонирование, умножение двух матриц. ^ В ходе выполнения лабораторной работы необходимо реализовать умножение разреженных матриц. При этом матрицы должны храниться в разреженном столбцовом формате. Изначально требуется реализовать последовательный вариант алгоритма умножения на языке С++. Далее необходимо разработать параллельную версию алгоритма и реализовать ее с помощью программно-аппаратной платформы CUDA на CUDA C - расширении языка C. В завершении работы должны быть приведены полученные результаты и заключение. ^ Для хранения разреженных матриц используется так называемый разреженный столбцовый формат, широко известным как CSS (Compressed Column Storage) или CSC (Compressed Sparse Columns). В таком формате матрица хранится в виде трех массивов:
При таком хранении 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 необходимо:
Теперь можно непосредственно выполнять умножение. Алгоритм умножение разреженных матриц A и B в форматах CSS состоит в следующем:
При умножении столбцов возникает задача сопоставления с целью выделения пар ненулевых элементов. В простейшем варианте это решается простым перебором для каждого элемента столбца матрицы AT элементов столбца матрицы B до тех пор, пока не будет найден элемент с таким же значением в массиве Row или не закончится строка. Хотя это излишне, ведь вектора упорядочены! Для решения проблемы достаточно:
Этого можно добиться, написав приблизительно следующее: 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 на столбцы матрицы B. Транспонирование Для хранения матрицы A в столбцовом формате используются следующие данные:
Для реализации параллельной версии алгоритма транспонирования необходимо завести вспомогательный массив 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 и матрица B, которые хранятся в столбцовом формате. Чтобы реализовать параллельный алгоритм их умножения, необходимо создать N*N потоков (N – размер матриц). Каждый поток будет считать соответствующий элемент матрицы С. Для этого нужно скалярно умножить I-ый столбец транспонированной матрицы A на J-ый столбец транспонированной матрицы B. ^ Для сравнения последовательной и параллельной реализации алгоритма умножения разреженных матриц была проведена серия экспериментов. Все эксперименты проводились на тестовой системе со следующими основными характеристиками:
На Рис.2. представлен график времени работы каждого варианта алгоритма для соответствующих размеров. Время указано в секундах. Размер перемножаемых матриц меняется от 128 до 2048. ![]() Рис.2. Время работы последовательной и параллельной версий алгоритма Ускорение, соответствующее каждому размеру перемножаемых матриц приведено на Рис.3. ![]() Рис.3. Ускорение параллельной версии ЗаключениеВ ходе выполнения лабораторной работы был успешно реализован последовательный вариант алгоритма умножения разреженных матриц на языке С++; а также разработана и реализована параллельная версия алгоритма с помощью платформы CUDA. Для сравнительного анализа обеих версий была проведена серия экспериментов, которая показала, что с ростом размера перемножаемых матриц, время работы последовательного варианта “стремительно” растет, в то время как время работы параллельного варианта меняется несущественно. Для N=2048 ускорение практически достигает 100. Это говорит о том, что задача "хорошо” ложится под архитектуру графического процессора, а также, что реализация была проведена довольно успешно. Литература
Интернет – ресурсы:
|
![]() | Государственное образовательное учреждение высшего профессионального образования Нижегородский государственный университет | ![]() | Для каждой лабораторной работы приведены перечень теоретических вопросов для сдачи коллоквиумов и перечень вопросов для сдачи отчетов.... |
![]() | В первом окне выводятся различные элементы управления (RadioButton, CheckBox, MaskEdit – в соответствии с заданием) | ![]() | Лабораторная работа Разработка многопроцессного приложения для анализа логов web-сервера 5 |
![]() | Экспертные системы вместе с системами обработки естественных языков являются наиболее важными в коммерческом плане областями использования... | ![]() | Предложения (рекомендации) лицу, ответственному за принятие решений, по оптимальному управленческому поведению 6 |
![]() | В ряде практических задач управления и оптимизации приходится решать системы линейных алгебраических уравнений (слу). В настоящей... | ![]() | Пояснительная записка: с., 22 рис., 17 табл., 11 библиограф источников, 2 приложения |
![]() | Повторить понятие умножения (что умножение есть сумма одинаковых слагаемых), переместительное свойство умножения | ![]() | В качестве симметричного алгоритма используется алгоритм des с режимом шифрования cbc |