DAS_2023_1/podkorytova_yulia_lab_5/README.md

Лабораторная работа 5. Параллельное умножение матриц

Задание на лабораторную работу

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

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

---

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

Обычный алгоритм реализован в методе multiplySequential:

public static int[][] multiplySequential(int[][] m1, int[][] m2) {
    int size = m1.length;
    int[][] res = new int[size][size];
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            for (int k = 0; k < size; k++) {
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }

    return res;
}

Параллельный алгоритм реализован в методе multiplyParallel:

public static int[][] multiplyParallel(int[][] m1, int[][] m2, int threadCount) throws InterruptedException {
    int size = m1.length;
    int[][] res = new int[size][size];
    ExecutorService executor = Executors.newFixedThreadPool(threadCount);
    for (int i = 0; i < size; i++) {
        int r = i;
        executor.submit(() -> {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    res[r][j] += m1[r][k] * m2[k][j];
                }
            }
        });
    }
    executor.shutdown();
    executor.awaitTermination(Long.MAX_VALUE, TimeUnit.MILLISECONDS);

    return res;
}

В методе создается пул потоков с помощью ExecutorService и указанным количеством потоков threadCount. Затем для каждой строки матрицы m1, создается задача, которая будет выполняться параллельно в отдельном потоке. Каждый поток берет на себя определенную строку матрицы m1 и умножает ее на соответствующие столбцы матрицы m2, результат умножения записывается в соответствующую ячейку результирующей матрицы res. Так каждый поток работает над своей зоной ответственности в матрицах и выполняет умножение независимо от других потоков.

---

Результаты

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

На матрицах размером 100x100 последовательный алгоритм справляется быстрее параллельного, а на матрицах размером 300x300 и 500x500 наоборот - параллельный алгоритм справляется быстрее последовательного.

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

Ссылка на видео:

https://drive.google.com/file/d/1jnSD5FNua2payHZc3k18vfhxaAN31Q4A/view?usp=sharing