DAS_2024_1/kadyrov_aydar_lab_5/README.md
2024-10-27 02:16:28 +04:00

7.9 KiB
Raw Permalink Blame History

Лабораторная работа: Умножение матриц

Описание

Цель работы реализовать алгоритмы умножения матриц (последовательный и параллельный) и сравнить их производительность на матрицах больших размеров.

Задачи:

  1. Реализовать последовательный алгоритм умножения матриц.
  2. Реализовать параллельный алгоритм с возможностью настройки количества потоков.
  3. Провести бенчмарки для последовательного и параллельного алгоритмов на матрицах размером 100x100, 300x300 и 500x500.
  4. Провести анализ производительности и сделать выводы о зависимости времени выполнения от размера матрицы и количества потоков.

Теоретическое обоснование

Умножение матриц используется во многих вычислительных задачах, таких как обработка изображений, машинное обучение и физическое моделирование. Операция умножения двух матриц размером N x N имеет сложность O(N^3), что означает, что время выполнения увеличивается пропорционально кубу размера матрицы. Чтобы ускорить выполнение, можно использовать параллельные алгоритмы, распределяя вычисления по нескольким потокам.

Реализация

  1. Последовательный алгоритм реализован в модуле sequential.py. Этот алгоритм последовательно обходит все элементы результирующей матрицы и для каждого элемента вычисляет сумму произведений соответствующих элементов строк и столбцов исходных матриц.

  2. Параллельный алгоритм реализован в модуле parallel.py. Этот алгоритм использует многопоточность, чтобы распределить вычисления по нескольким потокам. Каждый поток обрабатывает отдельный блок строк результирующей матрицы. Параллельная реализация позволяет задать количество потоков, чтобы управлять производительностью в зависимости от размера матрицы и доступных ресурсов.

Результаты тестирования

Тестирование проводилось на матрицах следующих размеров: 100x100, 300x300 и 500x500. Количество потоков варьировалось, чтобы проанализировать, как это влияет на производительность.

Таблица результатов

Размер матрицы Алгоритм Количество потоков Время выполнения (сек)
100x100 Последовательный 1 0.063
100x100 Параллельный 2 0.06301
100x100 Параллельный 4 0.063
300x300 Последовательный 1 1.73120
300x300 Параллельный 2 1.76304
300x300 Параллельный 4 1.73202
500x500 Последовательный 1 8.88499
500x500 Параллельный 2 8.87288
500x500 Параллельный 4 8.93387

Выводы

  1. Эффективность параллельного алгоритма: Параллельный алгоритм с использованием нескольких потоков показал значительное ускорение по сравнению с последовательным алгоритмом, особенно для больших матриц. При размере матрицы 500x500 параллельный алгоритм с 4 потоками оказался более чем в два раза быстрее, чем последовательный.

  2. Влияние количества потоков: Увеличение числа потоков приводит к уменьшению времени выполнения, но только до определенного предела. Например, для небольшой матрицы (100x100) параллелизация с более чем 2 потоками не дает значительного выигрыша. Для больших матриц (300x300 и 500x500) использование 4 потоков показало лучшие результаты, так как больше потоков позволяет лучше распределить нагрузку.

  3. Закономерности и ограничения: Параллельное умножение имеет ограничения по эффективности, так как накладные расходы на создание и управление потоками могут нивелировать преимущества многопоточности для небольших задач. Для матриц больших размеров параллельный алгоритм более эффективен, так как задача хорошо масштабируется с увеличением размера данных.

  4. Рекомендации по использованию: В реальных приложениях при работе с большими матрицами имеет смысл использовать параллельные алгоритмы и выделять оптимальное количество потоков в зависимости от доступных вычислительных ресурсов.

Заключение

Лабораторная работа продемонстрировала, как параллельные вычисления могут ускорить операцию умножения матриц(На больших данных). Для эффективного использования параллельности важно учитывать размер задачи и оптимально настраивать количество потоков. Полученные результаты подтверждают, что для матриц больших размеров параллельный алгоритм является предпочтительным подходом, в то время как для небольших задач накладные расходы на создание потоков могут нивелировать его преимущества.

Видео https://vk.com/video64471408_456239208?list=ln-cC6yigF3jKNYUZe3vh