Введение 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), включающий в себя подходы, основанные на многопоточности и повышении эффективности за счет разгрузки внутреннего цикла.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
