Фрагментация алгоритма умножения симметричной разреженной матрицы на вектор Студентка: Ткачёва А.А. ФПМИ 4курс Руководитель: Киреев С.Е. 12.11.2011. - презентация

1 Фрагментация алгоритма умножения симметричной разреженной матрицы на вектор Студентка: Ткачёва А.А. ФПМИ 4курс Руководитель: Киреев С.Е

2 Постановка задачи Реализовать фрагментированный алгоритм перемножения симметричной разреженной матрицы на вектор * = Xf

3 Подзадачи Спроектировать формат хранения разреженной матрицы Создать фрагментированную программу генерации разреженной матрицы Создать фрагментированную программу умножения матрицы на вектор

4 Форматы хранения разреженной матрицы С разрезанием на полоски Матрица Аxf = *

5 Форматы хранения разреженной матрицы С разрезанием на блоки Матрица Аxf = *

6 Алгоритм генерации разреженной матрицы Дано: N – размер матрицы P – плотность заполнения K – количество фрагментов Результат: разреженная матрица в нужном формате фрагментирования.

7 Алгоритм умножения(полоски) X2 d1 d2 u2 u1 X1 f1 f2 Mult_d2 Mult_d1 Mult_g211 Mult_g111 Mult_g212

8 Алгоритм умножения(блоки) f1 X2 f2 d1 d2 u22 u11 u21 Mult_g2 Mult_gg21 Mult_d2 Mult_d1 X1 Mult_g1

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