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

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

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

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

Оглавление

Введение

• 
  Массив значений Value (построчно, сверху вниз);
  
• 
  Массив номеров строк Row;
  
• 
  Массив индексов начала столбцов ColIndex.
  

• 
  сформировать N «целых» и N «вещественных» векторов;
  
• 
  в цикле просмотреть все столбцы исходной матрицы, для каждого столбца - все его элементы;
  
• 
  если A[i][j] = v, тогда добавить числа i и v в j-ые «целый» и «вещественный» вектор, тем самым в векторах сформируются столбцы транспонированной матрицы;
  
• 
  скопировать данные из векторов в CSS-структуру транспонированной матрицы (Row и Value), попутно формируя массив ColIndex.
  

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

• 
  встать на начало обоих векторов (ks= …, ls= …);
  
• 
  сравнить текущие элементы AT.Row[ks]и B.Row[ls];
  
• 
  если значения совпадают, просуммировать AT.Value[ks] * B.Value[ls] и увеличить оба индекса, в противном случае – увеличить один из индексов, в зависимости от того, какое значение больше.
  

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.



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

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



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

Заключение

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

Литература

1. 
   Писсанецки С. Технология разреженных матриц.: Пер. с англ. - М.: Мир, 1988.
   
2. 
   Тьюарсон Р. Разреженные матрицы.: Пер. с англ.  М.: Мир, 1977.
   
3. 
   Боресков, А.В. Основы работы с технологией CUDA / А.В. Боресков, А.А. Харламов. – М.: ДМК Пресс, 2011. – 232 с
   

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

4. 
   Разреженные матрицы [http://en.wikipedia.org/wiki/Sparse_matrix]
   
5. 
   Технология CUDA [http://developer.nvidia.com/]