🔍 Поиск готовых работ

🔍 Поиск работ

Разработка эффективных алгоритмов матричного умножения

Работа №116540

Тип работы

Бакалаврская работа

Предмет

информатика

Объем работы51
Год сдачи2022
Стоимость4270 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
190
Не подходит работа?

Узнай цену на написание


Введение 5
Термины и определения. Перечень сокращений и обозначений 7
1 Теоретическое обоснование задачи 8
1.1 Развитие алгоритмов матричного умножения 8
1.2 Многопоточные методы повышения скорости расчета 11
1.3 Эффективное использование вычислительных ресурсов 20
2 Разработка алгоритмов и программ эффективного умножения матриц 24
2.1 Базовый вариант матричного умножения 24
2.2 Разработка программ эффективного использования
вычислительных ресурсов при умножении матриц 26
2.3 Разработка программ многопоточного умножении матриц 28
3 Экспериментальное исследование эффективности разработанных
программ 32
3.1 Планирование эксперимента 32
3.2 Результаты эксперимента 34
3.3 Анализ результатов эксперимента 38
Заключение 44
Список используемой литературы и используемых источников 45
Приложение А Результаты экспериментов 48
Приложение Б Результаты экспериментов 49
Приложение В Результаты экспериментов 50
Приложение Г Результаты экспериментов 51


Актуальность исследуемой темы обуславливается тем, что умножение матриц — это один из базовых алгоритмов, который широко применяется в различных численных методах, и в частности в алгоритмах машинного обучения. Многие реализации прямого и обратного распространения сигнала в сверхточных слоях нейронной сети базируются на этой операции. Так порой до 90-95% всего времени, затрачиваемого на машинное обучение, приходится именно на эту операцию.
Матрицы находят много применений в научных областях, а также используются при решении практических проблем реальной жизни, тем самым решая значительную часть практических задач.
Одним из наиболее важных применений матриц в компьютерных приложениях является шифрование кодов сообщений. Сообщение выглядит как последовательность чисел в двоичном формате. Они используются для построения графиков, статистических данных, а также для исследований в самых различных областях.
Во многих организациях для записи данных экспериментов; в робототехнике и автоматизации матрицы являются базовыми элементами движений роботов. Движения роботов программируются с вычислением строк и столбцов матриц. Данные для управляющих роботов приведены на основе вычислений из матриц.
Матричное умножение — один из немногих алгоритмов, которые позволяет эффективно задействовать все вычислительные ресурсы современных процессоров и графических ускорителей. Поэтому многие алгоритмы стараются свести к матричному умножению — дополнительная расходы, связанные с подготовкой данных, как правило с лихвой окупаются общим ускорением алгоритмов.
Объектом исследования данной работы являются алгоритмы и программы матричного умножения.
Предметом исследования является быстродействие алгоритмов и программ матричного умножения.
Цель исследования - разработать эффективные алгоритмы матричного умножения.
Для достижения установленной задачи необходимо решить следующие задачи:
- Исследовать современное состояние вопроса.
- Разработать алгоритмы и программы повышения эффективности умножения матриц.
- Исследовать эффективность разработанных программ путем компьютерного эксперимента.
В работе использованы теоретические методы исследования, методы сравнительного анализа.
Практическая значимость состоит в том, что разработан алгоритм эффективного умножения матриц.
Бакалаврская работа состоит из введения, трех разделов, заключения списка использованной литературы и источников, приложения.
Первый раздел работы посвящен развитию алгоритмов матричного умножения, анализу существующих параллельных технологий, а также увеличению эффективности использования вычислительных ресурсов в одном потоке.
Во втором разделе описаны алгоритмы и программы, реализующих различные подходы к ускорению умножения матриц и их тестирование.
Третий раздел посвящен экспериментальному исследованию влияния размера матрицы на ускорение вычислений. Получены экспериментальные зависимости изменения коэффициента ускорения для различных компьютеров. Проведен анализ результатов и предложены пути совершенствования.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

В процессе выполнения бакалаврской работы разработаны эффективные алгоритмы матричного умножения. В ходе данной работы были поставлены и выполнены следующие задачи.
Исследовано современное состояние в области теории и практики матричного умножения. Установлены основные направления практических подходов к ускорению умножения матриц, области применения, достоинства и недостатки используемых приемов. Определены приемы для практической реализации матричного умножения.
Практически реализованы программы, позволяющие ускорить умножение матриц за счет изменения вычислительного алгоритма (за счет вынесение постоянных действий из внутреннего цикла) и за счет параллельных вычислений. Параллельным вычислениям уделяется большое внимание в связи с распространением систем с большим количеством потоков у процессора. По результатам анализа существующих параллельных технологий определено, что в работе наиболее целесообразно применение параллельной технологии OMP.
С применением разработанных программ экспериментально исследовано влияние размера матрицы на ускорение вычислений. Получены экспериментальные зависимости изменения коэффициента ускорения для различных компьютеров. Проведен анализ результатов и предложены пути совершенствования.
В результате проведенного сравнительного анализа, были сделаны следующие выводы из проделанной работы:
Наиболее эффективным алгоритмом матричного умножения является разработанный комплексный алгоритм (вариант 3), включающий в себя подходы, основанные на многопоточности и повышении эффективности за счет разгрузки внутреннего цикла.



1. Алексеев, В.Б. Умножения матриц размеров 5x2 И 2x2 / В.Б.
Алексеев // Ученые записки Казанского университета. Серия Физико - математические науки. - 2014. - № 3. - С. 19-29. - Текст: электронный // Лань : электронно-библиотечная система. - URL:
https:ZZe.lanbook.com/journal/issue/296338(дата обращения: 13.05.2022).
2. Белоусов, И.В. Матрицы и Определители: учеб. Пособие. Кишинев, 2006. 101 с.
3. Биллиг, В. А. Параллельные вычисления и многопоточное программирование : учебное пособие / В. А. Биллиг. — 2-е изд. — Москва : ИНТУИТ, 2016. — 310 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100361(дата обращения: 07.05.2022).
4. Ефимов, Н. В. Квадратичные формы и матрицы : учебное пособие
/ Н. В. Ефимов. — Москва : ФИЗМАТЛИТ, 2012. — 168 с. - Текст : электронный // Лань : электронно-библиотечная система. — URL:
https://e4anbook.com/book/59543(дата обращения: 03.0 5.2022.
5. Игонина, Е. В. Основы алгебры матриц и векторов. Линейное программирование : учебное пособие / Е. В. Игонина, О. Н. Прокуратова. — Елец : ЕГУ им. И.А. Бунина, 2008. - 75 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https:ZZe.lanbook.com/book/195891(дата обращения: 13.05.2022).
6. Корчевская, Е.А. Автоматизированная система распределённых вычислений для численного решения алгебраических задач / Е.А. Корчевская, Л.В. Маркова , А.Н. Красоткина // Математические структуры имоделирование 2014. - №4. - С. 69 - 72
7. Матричное умножение. Медленное достижение мифической цели - URL: https://habr.com/ru/companv/timeweb/blog/549360/(дата обращения: 04.05.2022).
8. Немцова, Т.И. Программирование на языке высокого уровня. Программирование на языке C++ : учебное пособие / Т.И. Немцова, С.Ю. Голова, А.И. Терентьев ; под ред. Л.Г. Гагариной. — Москва : ФОРУМ : ИНФРА-М, 2021. — 512 с. + Доп. материалы [Электронный ресурс]. — (Среднее профессиональное образование). Текст : электронный. - URL: https://znanium.Com/catalog/product/1172261 (дата обращения: 23.05.2022).
9. Пан, В.Я. Быстрое умножение матриц и смежные вопросы алгебры // Математический сборник. - 2017. - №11.
10. Панкратов, Е. Л. Операции над матрицами. решение систем линейных алгебраических уравнений : учебно-методическое пособие / Е. Л. Панкратов. — Нижний Новгород : ННГУ им. Н. И. Лобачевского, 2020. — 17 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/191782(дата обращения: 03.05.2022).
11. Тыртышников, Е. Е. Матричный анализ и линейная алгебра : учебное пособие / Е. Е. Тыртышников. — Москва : ФИЗМАТЛИТ, 2007. — 480 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https:ZZe.lanbook.com/book/2352(дата обращения: 21.05.2022).
12. Умнов А.Е. Аналитическая геометрия и линейная алгебра: Учеб. Пособие/ Умнов А.Е./ - 3е. изд., испр. и доп. - М.: МФТИ, 2011. - 544 с.
13. Умножение матриц: эффективная реализация шаг за шагом. - Режим доступа:https://habr.com/ru/post/359272/(дата обращения: 4.05.2022).
14. Федотов, И. Е. Параллельное программирование. Модели и
приемы : практическое пособие / И. Е. Федотов. - Москва : СОЛОН-Пресс, 2020. - 390 с. - (Серия «Библиотека профессионала»). Текст : электронный. - URL: https://znanium.com/catalog/product/1858781 (дата обращения:
13.05.2022).
15. Чубариков В. Н., Добровольский Н. Н., Реброва И. Ю., Добровольский Н. М. - Информатика, компьютер, сложность вычислений // Чебышевский сборник. — 2021. — №1 (77).
16. Энтони, У. Параллельное программирование на C++ в действии. Практика разработки многопоточных программ : учебное пособие / У. Энтони ; перевод с английского А. А. Слинкин. — Москва : ДМК Пресс, 2012. — 672 с. - Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/4813(дата обращения: 07.05.2022).
17. Alman, Josh &Williams, Virginia. (2021). A Refined Laser Method
and Faster Matrix Multiplication. 10.1137/1.9781611976465.32.
- https://arxiv.org/abs/2010.05846 (дата обращения: 07.05.2022).
18. Coppersmith D. and Winograd S.. Matrix multiplication via arithmetic progressions. J. Symbolic Computation, 9:251-280, 1990.
19. Divide&Conquer над алгоритмом Штрассена
https://habr.com/ru/post/313258/(датаобращения: 04.05.2022).
20. Henry Cohn and Christopher Umans. Fast matrix multiplication using coherent configurations. pages 1074-1086, 2013.
21. Joseph M. Landsberg and Giorgio Ottaviani. New lower bounds for the border rank of matrix multiplication. Theory of Computing, 11(1):285-298, 2015.
22. Matrix Multiplication Inches Closer to Mythic Goal [Электронный
ресурс] URL: https://science-education.ru/ru/article/view?id=25956(дата
обращения: 27.05.2021).
23. Strassen V. Gaussian Elimination is not Optimal (англ.) //Numer.Math /F. Brezzi — Springer Science+Business Media, 1969. — Vol. 13, Iss. 4. — P. 354—356.


Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2025 Cервис помощи студентам в выполнении работ
.