173 lines
12 KiB
Markdown
173 lines
12 KiB
Markdown
|
||
## Лабораторная работа 5. Вариант 4.
|
||
### Задание
|
||
Реализовать умножение двух больших квадратных матриц
|
||
|
||
- Создать алгоритм параллельного умножения матриц,
|
||
- Предусмотреть задание потоков вручную, для работы параллельного алгоритма умжожения как обычного.
|
||
|
||
### Как запустить
|
||
Для запуска программы необходимо с помощью командной строки в корневой директории файлов прокета прописать:
|
||
```
|
||
python main.py
|
||
```
|
||
Результат работы программы будет выведен в консоль.
|
||
|
||
### Используемые технологии
|
||
- Библиотека `numpy`, используемая для обработки массивов данных и вычислений.
|
||
- Библиотека `concurrent.futures`- высокоуровневый интерфейс для выполнения параллельных и асинхронных задач.
|
||
- `ThreadPoolExecutor` - класс пула потоков для выполнения задач в нескольких потоках. Он использует пул потоков, чтобы автоматически управлять созданием и выполнением потоков, что обеспечивает простой способ распараллеливания задач. Метод `submit()` позволяет отправлять задачи в пул потоков, и возвращает объект `Future`, который представляет результат выполнения задачи.
|
||
- Библиотека `time`, используемая для измерения времени работы программы.
|
||
- Библиотека `psutil`, используемая для отслеживания нагрузки на процессор и количества загруженной оперативной памяти.
|
||
|
||
### Описание работы
|
||
#### Распараллеливание задачи перемножения матриц
|
||
Возьмём несколько базовых правил из высшей математики:
|
||
- Умножение матриц выполнимо, если число столбцов 1го множителя равно числу строк 2го множителя.
|
||
- При умножении матрицы размерностью `[m, n]`, на матрицу размерностью `[n, m]` матрица-результат будет иметь размерность `[n, n]`.
|
||
- Умножение матриц не подчиняется переместительному закону умножения.
|
||
|
||
Возьмём пример умножения двух матриц:
|
||
```
|
||
[[1, 2, 3], [[7, 8], [[58, 64],
|
||
4, 5, 6]] x [9, 10], = [139, 154]]
|
||
[11, 12]]
|
||
```
|
||
Чтобы безболезненно разделить данную операцию на несколько, можно брать каждую строку 1й матрицы и умножать её на 2ю матрицу. а после собрать полученные промежуточные матрицы в матрицу-результат:
|
||
|
||
```
|
||
[[7, 8],
|
||
[[1, 2, 3]] x [9, 10], = [[58, 64]]
|
||
[11, 12]]
|
||
```
|
||
```
|
||
[[7, 8],
|
||
[[4, 5, 6]] x [9, 10], = [[139, 154]]
|
||
[11, 12]]
|
||
```
|
||
Таким образом, мы можем параллельно умножать все строки 1й матрицы на 2ю матрицу, и, собрав полученные строки-результаты, получить матрицу-результат.
|
||
|
||
#### Разработка программы
|
||
Для начала создадим функцию умножения строки матрицы на матрицу:
|
||
```python
|
||
def multiply_row(row, matrix_b):
|
||
return np.dot(row, matrix_b)
|
||
```
|
||
Теперь перейдём к алгоритму параллельного умножения матриц. Для начала найдём сначения строк и столбцов обеих матриц и проверим по 1му правилу, возможно ли их умножить:
|
||
```python
|
||
num_rows_a, num_cols_a = matrix_a.shape
|
||
num_rows_b, num_cols_b = matrix_b.shape
|
||
assert num_cols_a == num_rows_b, "Размеры матриц несовместимы для перемножения"
|
||
```
|
||
После этого, создадим пул потоков с помощью класса `concurrent.futures.ThreadPoolExecutor`, в который будем передавать желаемое количество потоков:
|
||
```python
|
||
with concurrent.futures.ThreadPoolExecutor(max_workers=num_threads) as executor:
|
||
results = []
|
||
for i in range(num_rows_a):
|
||
result = executor.submit(multiply_row, matrix_a[i], matrix_b)
|
||
results.append((i, result))
|
||
sorted_results = sorted(results, key=lambda x: x[0])
|
||
result_matrix = np.vstack([result.result() for _, result in sorted_results])
|
||
```
|
||
В пул потоков в качестве задач мы передаём последовательно строки 1й матрицы и 2ю матрицу, а в качестве их обработчика указываем ранее созданный метод `multiply_row`. Результаты выполнения задач в пуле потоков могут возвращаться в произвольном порядке, поэтому для каждого ожидаемого результата зададим индекс. После этого. массив строк-результатов отсортируем по индексу и последовательно вложим в матрицу-результат методом `vstack`.
|
||
|
||
> **Note**
|
||
>
|
||
> Поскольку умножение матриц распараллеливается по строкам 1й матрицы, задавать значение кол-ва потоков больше числа строк 1й матрицы не имеет значения. По сути, самым оптимальным решение мудет являться состояние, когда каждый поток умножает свою строку 1й матрицы на 2ю матрицу.
|
||
|
||
Создадим тестовый метод и проверим работу калькулятора матриц на грамотность вычислений:
|
||
```python
|
||
a = np.array([[1, 2, 3], [4, 5, 6]])
|
||
b = np.array([[7, 8], [9, 10], [11, 12]])
|
||
return parallel_matrix_multiplication(a, b, num_threads=1)
|
||
```
|
||
Результат вычислений:
|
||
```
|
||
[[58, 64]
|
||
[139, 154]]
|
||
```
|
||
Теперь поменяем местами матрицы a и b и проверим результат:
|
||
```
|
||
[[39, 54, 69]
|
||
[49, 68, 87]
|
||
[59, 82, 105]]
|
||
```
|
||
Алгоритм работает верно.
|
||
|
||
#### Сбор данных о вычислениях. Бенчмарки.
|
||
|
||
Теперь соберём некотрорую статистику о вычислениях. Будем собирать время вычислений, загруженность ЦП и загруженность ОЗУ.
|
||
|
||
Время работы:
|
||
```python
|
||
start_time = time.time()
|
||
|
||
# Вычисления тут
|
||
|
||
execution_time = end_time - start_time
|
||
return execution_time
|
||
```
|
||
Загруженность ЦП:
|
||
```python
|
||
psutil.cpu_percent(interval=interval)
|
||
```
|
||
Где `interval` - время измерений в секундах.
|
||
|
||
Загруженность ОЗУ:
|
||
```python
|
||
memory = psutil.virtual_memory()
|
||
|
||
# Вычисления тут
|
||
|
||
return memory.percent
|
||
```
|
||
Теперь создадим бенчмарки. Первым будет бенчмарк умножения 2х матриц, размерностью 100 * 100 с рандомным заполнением числами от 0 до 100 (остальные бенчмарки будут создаваться по аналогии, меняться будет только размерность):
|
||
```python
|
||
def bench100x100(parallel):
|
||
a = np.random.randint(0, 100, size=(100, 100))
|
||
b = np.random.randint(0, 100, size=(100, 100))
|
||
if parallel:
|
||
result = parallel_matrix_multiplication(a, b, num_threads=100, interval=1)
|
||
else:
|
||
result = parallel_matrix_multiplication(a, b, num_threads=1, interval=1)
|
||
print("Результат умножения:")
|
||
print(result[0])
|
||
print("Время выполнения: " + str(result[1]) + " сек.")
|
||
print("Загрузка ЦП: " + str(result[2]) + "%")
|
||
print("Использование ОЗУ: " + str(result[3]) + "%")
|
||
```
|
||
|
||
#### Замеры параметров
|
||
Прогоним все бенчмарки и сравним измеряемые показатели при максимальной многопоточности (кол-во потоков = кол-ву строк матрицы) и монопоточности.
|
||
|
||
Результаты (параллельный - справа, обычный - слева):
|
||
```
|
||
100 * 100
|
||
_________________________________________________________________
|
||
|
||
Время выполнения: 0.0099.. сек. | Время выполнения: 0.0110.. сек.
|
||
Загрузка ЦП: 0.8% | Загрузка ЦП: 4.1%
|
||
Использование ОЗУ: 64.0% | Использование ОЗУ: 64.1%
|
||
|
||
300 * 300
|
||
_________________________________________________________________
|
||
|
||
Время выполнения: 0.0369.. сек. | Время выполнения: 0.0340.. сек.
|
||
Загрузка ЦП: 0.6% | Загрузка ЦП: 1.2%
|
||
Использование ОЗУ: 63.5% | Использование ОЗУ: 63.6%
|
||
|
||
500 * 500
|
||
_________________________________________________________________
|
||
|
||
Время выполнения: 0.1360.. сек. | Время выполнения: 0.0529.. сек.
|
||
Загрузка ЦП: 0.6% | Загрузка ЦП: 1.7%
|
||
Использование ОЗУ: 62.6% | Использование ОЗУ: 62.9%
|
||
```
|
||
|
||
### Вывод
|
||
По результатам замеров видно, что до матриц с размерностью 100 наиболее быстро обрабатывались вычисления в одном потоке, при размерности матриц в 300 многопоточные вычисления начали незначительно лидировать по скорости, а при размерности матриц в 500 превзошли однопоточные в скорости более чем в два раза. По нагрузке процессора, многопоточные вычисления всегда нагружали его чуть больше, загруженность ОЗУ оставатась примерно одинаковый во всех экспериментах.
|
||
|
||
Получается, можно сделать вывод, что параллельные вычисления ресурсозатратнее, чем обычные и работают эффективнее последних только при достаточно больших наборах данных.
|
||
|
||
### Видео
|
||
https://youtu.be/A8aYkuwn4yU |