DAS_2023_1/basharin_sevastyan_lab_5

Лабораторная работа 5

Задание

Реализовать умножение двух больших квадратных матриц

Ход выполнения

• Реализовать алгоритм перемножение матриц для потокового выполнения
• Адаптировать алгоритм для параллельного выполнения:
  • Разделить данные на чанки, сохранив корректность вычислений

Как запустить

В терминале, находясь в корневой директории файлов проекта, выполнить команду:

python main.py

Результат будет выведен в терминале.

Технологии

• numpy: библиотека для работы с многомерными массивами и матрицами в Python.
• multiprocessing: модуль Python, предоставляющий возможность создания и управления процессами, что позволяет реализовать параллельные вычисления.

Описание работы

Обычный алгоритм

def sequential_multiply(A, B):
    # Определение размеров матриц A и B
    rows_A = len(A)
    cols_A = len(A[0])
    rows_B = len(B)
    cols_B = len(B[0])

    # Проверка совместимости матриц для умножения
    if cols_A != rows_B:
        print("Cannot multiply matrices")
        return

    # Создание матрицы C, результат умножения A на B
    C = [[0 for row in range(cols_B)] for col in range(rows_A)]

    # Выполнение умножения матриц
    for i in range(rows_A):
        for j in range(cols_B):
            for k in range(cols_A):
                C[i][j] += A[i][k] * B[k][j]

    return C

Этапы:

1. Определение размеров матриц: Получаются размеры матриц A и B (число строк и столбцов каждой матрицы).
2. Проверка совместимости матриц: Проверяется, можно ли умножить матрицы A и B. Умножение возможно, если количество столбцов матрицы A равно количеству строк матрицы B.
3. Создание матрицы-результата: Создается матрица C, которая будет содержать результат умножения матриц A и B. Размеры матрицы C определяются числом строк матрицы A и числом столбцов матрицы B.
4. Умножение матриц: Вложенные циклы используются для умножения каждого элемента матрицы C. Внешний цикл итерируется по строкам матрицы A, второй цикл по столбцам матрицы B, а третий цикл выполняет суммирование произведений элементов соответствующих ячеек для получения значения элемента в матрице C.
5. Возврат результата: Возвращается матрица C, которая является результатом умножения матриц A и B.

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

import multiprocessing

def parallel_multiply(A, B, num_processes):
    # Определение размеров матриц A и B
    rows_A = len(A)
    cols_A = len(A[0])
    rows_B = len(B)
    cols_B = len(B[0])

    # Проверка совместимости матриц для умножения
    if cols_A != rows_B:
        print("Cannot multiply matrices")
        return

    # Создание матрицы C, результат умножения A на B
    C = [[0 for row in range(cols_B)] for col in range(rows_A)]

    # Разделение работы между процессами
    chunk_size = int(rows_A / num_processes)

    # Создание процессов
    processes = []
    for i in range(num_processes):
        start = chunk_size * i
        end = chunk_size * (i + 1) if i < num_processes - 1 else rows_A

        # Запуск процесса с функцией perform_multiplication
        p = multiprocessing.Process(target=perform_multiplication, args=(A, B, C, start, end))
        processes.append(p)
        p.start()

    # Ожидание завершения всех процессов
    for p in processes:
        p.join()

    return C

def perform_multiplication(A, B, C, start, end):
    # Умножение подматрицы A на матрицу B
    for i in range(start, end):
        for j in range(len(B[0])):
            for k in range(len(A[0])):
                C[i][j] += A[i][k] * B[k][j]

Первые три этапа похожи на обычный алгоритм, поэтому не имеет смысла их описывать. Этапы:

1. Разделение работы между процессами: Матрица A разбивается на несколько частей, и для каждой части создается отдельный процесс.
2. Создание и запуск процессов: Для каждой части матрицы A создается процесс, который вызывает функцию perform_multiplication. Каждый процесс работает с своим подмножеством данных.
3. Ожидание завершения всех процессов: Главный процесс ждет завершения работы всех созданных процессов с помощью метода join().
4. Возврат результата: Возвращается матрица C, которая является результатом умножения матриц A и B.

Результат работы

Видео

https://youtu.be/XIEENJAUPNY