Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Основные подходы к решению задачи умножения разреженных матриц Мееров И.Б., Кустикова В.Д., Козинов Е.А., Сиднев А.А., Сысоев А.В.

Результаты конкурса Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 2 Фамилия участника N = 100 N = 400 N = 2000N = Гиркин М. 0,0050,0460,5541,1022,25814,4530,0563,8 2.Крыжановский Д. 0,0190,1571,0563,8516,9323,27599,724463,3 3.Сафонова Я. 0,002 0,4920,6570,858 4.Губарев И. 0,0633,343250,64458,02906,22 5.Яппарова А. 0,0691,677 6.Протасов С. 0,0050,044 7.Васильев Р. 0,0340,701 Еще 7 работ считают неправильно, либо падают при размерах N > 100

Введение Умножение разреженных матриц – сложная задача. Есть библиотечные реализации (MKL и др.) Эффективная реализация на параллельных архитектурах – предмет исследования, освещается в ряде публикаций в ведущих журналах. В рамках данной реализации рассмотрены стартовые варианты реализации, с которых можно начать понимать задачу. Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 3

Подход #1. Перегрузка операций (1) Перегрузка операции получения элемента (i, j) из разреженной матрицы: float Get(CRSMatrix a, int i, int j); Перегрузка операции добавления к текущему значению элемента (i, j): –в плотную матрицу void Set(Matrix c, int i, int j, float aik, float bkj); –в разреженную матрицу (перепаковка ) void Set(CRSMatrix c, int i, int j, float aik, float bkj); Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 4

Подход #1. Перегрузка операций (2) Псевдокод алгоритма: for (int i = 0; i < n; i++){ for (int k = 0; k < n; k++){ Set(c, i, j, Get(a,i,k), Get(b,k,j)); } Очень долго (не менее n^4). Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 5

Выделение элементов столбца для каждой строки. Формируем массивы матрицы С по порядку. Проблема – крайне неэффективно работаем с памятью. Возможный выход: получить в итоге C T. Но по-прежнему неудобно выбирать из B столбец. Подход #2. Выделение столбца Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 6 A B

Подход #3. Транспонирование (1) Транспонирование матрицы, на которую производится умножение. Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 7 BBTBT

Подход #3. Транспонирование (2) Умножение строки на столбец заменяем умножением строки на строку. Результирующие элементы сохраняются –в плотную матрицу, –в разреженную матрицу (в наивной версии не знаем результирующее количество элементов строки; но можно улучшить: цикл по строкам B T ). Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 8 A BTBT

Подход #4. Двухфазное умножение Символическая (символьная, symbolic) фаза: –определение структуры результирующей матрицы. Численная (numeric) фаза: –заполнение построенной структуры. Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 9 BAC x =

Подход #5. Блочное умножение Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 10 x BA

Параллелизм Проблемы: –Нужно балансировать вычисления. –Нужно избежать распараллеливания мелкими гранулами – накладные расходы могут оказаться значимыми на фоне вычислений. Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 11

Вопросы ??? Н.Новгород, 2010 г. Основные подходы к решению задачи умножения разреженных матриц. 12