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

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

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

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

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

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

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

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

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