DAS_2023_1/arutunyan_dmitry_lab_5/README.md

Лабораторная работа 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ю матрицу, и, собрав полученные строки-результаты, получить матрицу-результат.

Разработка программы

Для начала создадим функцию умножения строки матрицы на матрицу:

def multiply_row(row, matrix_b): 
    return np.dot(row, matrix_b)

Теперь перейдём к алгоритму параллельного умножения матриц. Для начала найдём сначения строк и столбцов обеих матриц и проверим по 1му правилу, возможно ли их умножить:

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, в который будем передавать желаемое количество потоков:

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ю матрицу.

Создадим тестовый метод и проверим работу калькулятора матриц на грамотность вычислений:

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]]

Алгоритм работает верно.

Сбор данных о вычислениях. Бенчмарки.

Теперь соберём некотрорую статистику о вычислениях. Будем собирать время вычислений, загруженность ЦП и загруженность ОЗУ.

Время работы:

start_time = time.time()

# Вычисления тут 

execution_time = end_time - start_time
return execution_time

Загруженность ЦП:

psutil.cpu_percent(interval=interval)

Где interval - время измерений в секундах.

Загруженность ОЗУ:

memory = psutil.virtual_memory()

# Вычисления тут 

return memory.percent

Теперь создадим бенчмарки. Первым будет бенчмарк умножения 2х матриц, размерностью 100 * 100 с рандомным заполнением числами от 0 до 100 (остальные бенчмарки будут создаваться по аналогии, меняться будет только размерность):

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