DAS_2024_1/nikolaeva_yana_lab_5

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

Описание

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

Задачи:

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

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

Умножение матриц — вычислительно сложная операция с асимптотической сложностью O(N³) для матриц размером N×N. Для ускорения вычислений используется параллелизация, где каждая часть вычислений выполняется в отдельном потоке. Однако эффективность параллельного подхода зависит от размеров задачи и числа потоков.

Реализация

1. Последовательный алгоритм:

   • Выполняет вычисления поэлементно для каждой строки первой матрицы и каждого столбца второй.
   • Этот алгоритм не использует дополнительные ресурсы, кроме одного потока, и подходит для небольших задач.

2. Параллельный алгоритм:

   • Делит строки первой матрицы на группы, каждая из которых обрабатывается в отдельном потоке.
   • Реализован с использованием модуля multiprocessing для управления потоками.
   • Число потоков задается вручную для возможности анализа производительности.

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

Условия тестирования

• Размеры матриц: 100x100, 300x300, 500x500.
• Количество потоков: 1 (последовательное выполнение), 2, 4.
• Диапазон значений элементов матриц: от 0 до 200.

Выводы

1. Последовательный алгоритм:

   • Подходит для матриц небольшого размера (100x100), где накладные расходы на параллелизацию превышают выигрыши от многопоточности.

2. Параллельный алгоритм:

   • Значительно ускоряет умножение матриц с увеличением их размера.
   • Для матриц 500x500 ускорение в 2–2.5 раза при переходе от 1 потока к 4 потокам.

3. Влияние числа потоков:

   • Оптимальное число потоков зависит от размера задачи и доступных ресурсов.
   • Слишком большое количество потоков может привести к росту накладных расходов.

4. Закономерности:

   • Накладные расходы на управление потоками минимальны для больших задач.
   • Параллельные алгоритмы демонстрируют преимущество на задачах с высокой вычислительной сложностью.

Заключение

Лабораторная работа подтвердила, что параллельные алгоритмы значительно эффективнее на больших данных. Однако для небольших задач последовательный алгоритм остается предпочтительным из-за отсутствия накладных расходов. В реальных приложениях важно учитывать баланс между размером задачи и доступными вычислительными ресурсами.

Видео

https://cloud.mail.ru/public/fykM/jy3KEZBZM