Введение
1. Описание форматов хранения разреженных матриц и операций над матрицами в различных форматах
1.1 Описание форматов
1.1.1 Формат хранения разреженной матрицы COO
1.1.2 Формат хранения разреженной матрицы CRS(CSR)
1.2 Последовательные алгоритмы умножения матрицы на вектор...
1.2.1 Умножение матрицы на вектор в формате COO
1.2.2 Умножение матрицы на вектор в формате CRS
1.3 Последовательные алгоритмы транспонирования матрицы
1.3.1 Транспонирование матрицы в формате COO
1.3.2 Транспонирование матрицы в формате CRS
1.4 Последовательные алгоритмы умножения матрицы на матрицу .
1.4.1 Умножение матрицы на матрицу в формате COO
1.4.2 Умножение матрицы на матрицу в формате CRS
2. Реализация с помощью технологии OpenMP операций с разреженными матрицами, хранящихся в специальных форматах
2.1 Особенности реализации с помощью технологии OpenMP операций с разреженными матрицами для формата COO
2.2 Особенности реализации с помощью технологии OpenMP операций с разреженными матрицами для формата CRS
2.3 Численное исследование работы алгоритмов с помощью технологии OpenMP
2.3.1 Численные исследования работы алгоритмов с помощью технологии OpenMP для формата COO
2.3.2 Численные исследования работы алгоритмов с помощью технологии OpenMP для формата CRS
3. Численные эксперименты над коллекцией разреженных матриц возникающих в реальных задачах
3.1 Описание коллекции матриц
3.1.1 Первая коллекция матриц
3.1.2 Вторая коллекция матриц
3.1.3 Третья коллекция матриц
3.2. Результат счетов
3.3 Результаты расчетов с помощью технологии OpenMP
3.3.1 Результаты расчетов с помощью технологии OpenMP для первой коллекции матриц
3.3.2 Результаты расчетов с помощью технологии OpenMP для второй коллекции матриц
3.3.3 Результаты расчетов с помощью технологии OpenMP для третей коллекции матриц
Вывод
Список использованных источников
Алгебра разреженных матриц один из важных разделов современной математики, который необходим для многих практических задач. Разреженная матрица - матрица, в которой количество ненулевых элементов много меньше нулевых элементов. Задачи, связанные с разреженными матрицами, встречаются во многих областях наук, таких как математика, физика, биология, экономика и другие. В математике такие задачи довольно часто встречаются при решении дифференциальных уравнений в частных производных и теории графов.
В современных задачах матрицы имеют большие размеры, такие что хранить и работать с матрицей, хранящейся в классическом формате двумерного массива, очень сложно, а иногда и невозможно, так как требуется много памяти для их хранения. Для задач с разреженными матрицами были придуманы специальные форматы хранения матриц, которые решают эту проблему. Такие форматы требуют меньше памяти для хранения матрицы, что позволяет работать с матрицами большего размера.
Несмотря на то, что были придуманы специальные форматы для хранения разреженных матриц, которые направлены на уменьшение занимаемой памяти при хранении матрицы, эти форматы могу потребовать большое количество времени для операций над матрицами, поэтому для более быстрого выполнения операций над матрицами можно воспользоваться технологией OpenMP для распараллеливания алгоритмов операций над матрицами.
Цель работы: сравнительный анализ эффективности распараллеливания алгоритмов основных операций над матрицами, хранящихся в специальных форматах COO и CRS с помощью технологии OpenMP.
Для достижения указанной цели были поставлены следующие задачи.
- Реализовать алгоритмы основных операций над матрицами (умножение матрицы на вектор, транспонирование матрицы, умножение матрицы на матрицу), хранящихся в форматах COO и CRS.
- Реализовать распараллеливание алгоритмов основных операций над матрицами с помощью технологии OpenMP.
- Провести вычислительные эксперименты на многоядерном процессоре на тестовых наборах данных, определить ускорение и эффективность каждого формата в зависимости от размерности.
- Провести вычислительные эксперименты на матрицах, полученных в реальных задачах.
- Провести сравнительный анализ выбранных форматов хранения по объему занимаемой памяти и эффективности распараллеливания.
Благодарность научному руководителю, кандидату физико-математических наук Евгении Дмитриевне Кареповой, за оказанную помощь и наставления в выпускной квалификационной работе.
В ходе проделанной работы были реализованы на языке Си++ алгоритмы умножения матрицы на вектор, транспонирования матрицы, умножения матрицы на матрицу для специальных форматов хранения разреженных матриц COO и CRS. Хранение матриц в форматах COO и CRS требуют меньше памяти для хранения матриц, чем обычное хранение матрицы в виде двумерного массива. Алгоритмы для операций над матрицами в форматах COO и CRS требует меньшее время, чем алгоритмы для формата хранения матрицы в двумерном массиве, поскольку не обрабатывают нулевые элементы.
Произведено исследование об эффективности и ускорении параллельных алгоритмов, реализованных с помощью технологии OpenMP. В результате можно указать следующее.
1. Алгоритм умножения матрицы на вектор при хранении матрицы как в формате COO, так и в формате CRS работает достаточно быстро и при последовательной реализации, поэтому параллельные версии алгоритмов, реализованных с помощью технологии OpenMP, имеет смысл использовать только при очень большом размере матрицы и большом количестве ненулевых элементов. При этом надо понимать, что максимальное ускорение достигается уже при небольшом количестве нитей.
2. Алгоритм транспонирования матрицы при хранении матрицы в формате COO работает достаточно быстро и при последовательной реализации, поэтому параллельные версии алгоритмов, реализованных с помощью технологии OpenMP, имеет смысл использовать только при очень большом размере матрицы и большом количестве ненулевых элементов.
В свою очередь алгоритм транспонирования матрицы, хранящейся в формате CRS, достаточно трудоемкий процесс, который при использовании технологии OpenMP показывает хорошие ускорение и эффективность.
3. Параллельные версии алгоритмов умножения матрицы на матрицу при хранении матриц в обоих форматах COO и CRS показало практически линейное ускорении и эффективность близкую к 1, т.е. оптимальную.
4. Исследование об эффективности и ускорении параллельных алгоритмов, реализованных с помощью технологии OpenMP на матрицах, встречающихся в реальных задачах, подтверждают результаты, полученные при исследовании на заданной матрице.
