99 lines
8.9 KiB
Markdown
99 lines
8.9 KiB
Markdown
# Кашин Максим ПИбд-42
|
||
|
||
# Отчет по умножению матриц
|
||
|
||
## Описание
|
||
|
||
В данной лабораторной работе реализованы два алгоритма для умножения больших квадратных матриц: последовательный и параллельный.
|
||
|
||
### Алгоритмы
|
||
|
||
1. **Последовательное умножение**:
|
||
- Для умножения используется функция `sequential_multiply`, которая принимает две матрицы \( A \) и \( B \) и возвращает их произведение \( C = A \cdot B \). Умножение реализовано с помощью функции NumPy `np.dot()`.
|
||
|
||
2. **Параллельное умножение**:
|
||
- Для параллельного умножения используется функция `parallel_multiply`, которая делит задачу на несколько процессов, каждый из которых умножает свои строки матрицы \( A \) на матрицу \( B \).
|
||
- Результат записывается в разделяемый массив `C`, который создается с помощью `multiprocessing.Array`.
|
||
- Каждому процессу передается диапазон строк, которые он должен обработать.
|
||
|
||
### Структура кода
|
||
|
||
- **Функции**:
|
||
- `sequential_multiply(A, B)`: Выполняет последовательное умножение.
|
||
- `parallel_multiply(A, B, num_processes)`: Выполняет параллельное умножение с заданным количеством процессов.
|
||
- `perform_multiplication(A, B, C, start, end, rows_A, cols_B)`: Вспомогательная функция, выполняющая умножение строк матрицы.
|
||
|
||
## Результаты
|
||
|
||
Результаты выполнения программы для разных размеров матриц и количества потоков:
|
||
|
||
### Время выполнения для 2 потоков
|
||
```
|
||
Введите количество потоков: 2
|
||
Последовательное умножение 100x100: 0.001003 секунд
|
||
Параллельное умножение 100x100: 0.900024 секунд
|
||
Последовательное умножение 300x300: 0.015999 секунд
|
||
Параллельное умножение 300x300: 1.078092 секунд
|
||
Последовательное умножение 500x500: 0.096649 секунд
|
||
Параллельное умножение 500x500: 1.450420 секунд
|
||
```
|
||
|
||
### Время выполнения для 4 потоков
|
||
```
|
||
Введите количество потоков: 4
|
||
Последовательное умножение 100x100: 0.001000 секунд
|
||
Параллельное умножение 100x100: 1.686326 секунд
|
||
Последовательное умножение 300x300: 0.015986 секунд
|
||
Параллельное умножение 300x300: 1.749842 секунд
|
||
Последовательное умножение 500x500: 0.087000 секунд
|
||
Параллельное умножение 500x500: 1.960365 секунд
|
||
```
|
||
|
||
### Время выполнения для 8 потоков
|
||
```
|
||
Введите количество потоков: 8
|
||
Последовательное умножение 100x100: 0.000000 секунд
|
||
Параллельное умножение 100x100: 3.307927 секунд
|
||
Последовательное умножение 300x300: 0.016013 секунд
|
||
Параллельное умножение 300x300: 3.321677 секунд
|
||
Последовательное умножение 500x500: 0.086618 секунд
|
||
Параллельное умножение 500x500: 3.446928 секунд
|
||
```
|
||
|
||
### Время выполнения для 16 потоков
|
||
```
|
||
Введите количество потоков: 16
|
||
Последовательное умножение 100x100: 0.000000 секунд
|
||
Параллельное умножение 100x100: 6.534394 секунд
|
||
Последовательное умножение 300x300: 0.016131 секунд
|
||
Параллельное умножение 300x300: 6.787100 секунд
|
||
Последовательное умножение 500x500: 0.086582 секунд
|
||
Параллельное умножение 500x500: 7.096588 секунд
|
||
```
|
||
|
||
## Анализ результатов
|
||
|
||
1. **Сравнение времени выполнения**:
|
||
- Последовательное умножение показывает значительно более быстрое время выполнения по сравнению с параллельным умножением для всех размеров матриц. Например, при умножении матриц размером 100x100, время последовательного умножения составляет всего 0.001003 секунд, в то время как параллельное умножение занимает 0.900024 секунд при использовании 2 потоков. Это указывает на то, что накладные расходы на создание и управление потоками значительно превышают выгоды от параллельной обработки на малом размере матриц.
|
||
|
||
2. **Увеличение размеров матриц**:
|
||
- Время выполнения параллельного умножения становится менее эффективным по мере увеличения размеров матриц. Например, при умножении матриц размером 500x500 время параллельного умножения увеличивается до 1.450420 секунд при 2 потоках, в то время как последовательное умножение занимает всего 0.096649 секунд. Это происходит из-за того, что при больших размерах матриц накладные расходы на распределение задач между потоками становятся более значительными.
|
||
|
||
3. **Влияние количества потоков**:
|
||
- Увеличение количества потоков также негативно сказывается на времени выполнения параллельного алгоритма. Например, при 4 потоках время выполнения для 100x100 матриц составляет 1.686326 секунд, а при 8 потоках — 3.307927 секунд. Это объясняется тем, что количество потоков, превышающее количество доступных ядер процессора, приводит к дополнительным накладным расходам на переключение контекста между потоками, что замедляет выполнение.
|
||
|
||
4. **Эффективность последовательного алгоритма**:
|
||
- Последовательный алгоритм показывает стабильную производительность, которая не зависит от накладных расходов, связанных с многопоточностью. Он использует оптимизированные алгоритмы NumPy, что также способствует высокой производительности.
|
||
|
||
## Выводы
|
||
|
||
1. **Эффективность**:
|
||
- Последовательное умножение матриц показывает значительно более высокую производительность по сравнению с параллельным умножением для малых и средних размеров матриц.
|
||
- Параллельное умножение начинает терять эффективность при увеличении количества потоков, что может быть связано с накладными расходами на создание процессов и синхронизацию между ними.
|
||
|
||
2. **С увеличением размера матриц**:
|
||
- Время выполнения параллельного алгоритма увеличивается, особенно для больших матриц и большого количества потоков, что указывает на ограниченную эффективность параллельного подхода в данной реализации.
|
||
|
||
|
||
## Ссылка на видео
|
||
[Видео-отчёт Кашин Максим ПИбд-42](https://disk.yandex.ru/i/0g-KQ5FarFGtqg) |