Умножение матриц в параллельных потоках

Рассмотрим алгоритм перемножения прямоугольных матриц с использованием потоков Java Stream. Возьмём оптимизированный вариант алгоритма на трёх вложенных циклах и заменим внешний цикл на поток. Сравним время работы двух алгоритмов.

Строки результирующей матрицы обрабатываем в параллельном режиме, а каждую строку заполняем слоями. За счёт параллельного использования кеша среды выполнения на многоядерных машинах время вычислений можно сократить более чем в два раза. Для проверки возьмём две прямоугольные матрицы: {L×M} и {M×N}.

Дальнейшая оптимизация: Алгоритм Винограда — Штрассена.

Параллельный поток #

Строки первой матрицы L обходим в параллельном режиме. Внутри каждого потока два вложенных цикла: по общей стороне двух матриц M и по колонкам второй матрицы N. Обработка строк результирующей матрицы происходит независимо друг от друга в параллельных потоках.

/**
 * @param l строки матрицы 'a'
 * @param m колонки матрицы 'a'
 *          и строки матрицы 'b'
 * @param n колонки матрицы 'b'
 * @param a первая матрица 'l×m'
 * @param b вторая матрица 'm×n'
 * @return результирующая матрица 'l×n'
 */
public static int[][] parallelMatrixMultiplication(int l, int m, int n, int[][] a, int[][] b) {
    // результирующая матрица
    int[][] c = new int[l][n];
    // обходим индексы строк матрицы 'a' в параллельном режиме
    IntStream.range(0, l).parallel().forEach(i -> {
        // обходим индексы общей стороны двух матриц:
        // колонок матрицы 'a' и строк матрицы 'b'
        for (int k = 0; k < m; k++)
            // обходим индексы колонок матрицы 'b'
            for (int j = 0; j < n; j++)
                // сумма произведений элементов i-ой строки
                // матрицы 'a' и j-ой колонки матрицы 'b'
                c[i][j] += a[i][k] * b[k][j];
    });
    return c;
}

Три вложенных цикла #

Возьмём оптимизированный вариант алгоритма, который лучше прочих использует кеш среды выполнения. Внешний цикл обходит строки первой матрицы L, далее идёт цикл по общей стороне двух матриц M и за ним цикл по колонкам второй матрицы N. Запись в результирующую матрицу происходит построчно, а каждая строка заполняется слоями.

/**
 * @param l строки матрицы 'a'
 * @param m колонки матрицы 'a'
 *          и строки матрицы 'b'
 * @param n колонки матрицы 'b'
 * @param a первая матрица 'l×m'
 * @param b вторая матрица 'm×n'
 * @return результирующая матрица 'l×n'
 */
public static int[][] sequentialMatrixMultiplication(int l, int m, int n, int[][] a, int[][] b) {
    // результирующая матрица
    int[][] c = new int[l][n];
    // обходим индексы строк матрицы 'a'
    for (int i = 0; i < l; i++)
        // обходим индексы общей стороны двух матриц:
        // колонок матрицы 'a' и строк матрицы 'b'
        for (int k = 0; k < m; k++)
            // обходим индексы колонок матрицы 'b'
            for (int j = 0; j < n; j++)
                // сумма произведений элементов i-ой строки
                // матрицы 'a' и j-ой колонки матрицы 'b'
                c[i][j] += a[i][k] * b[k][j];
    return c;
}

Тестирование #

Для проверки возьмём две матрицы: A=[900×1000] и B=[1000×750], заполненные случайными числами. Сначала сравниваем между собой корректность реализации двух алгоритмов — произведения матриц должны совпадать. Затем выполняем каждый метод по 10 раз и подсчитываем среднее время выполнения.

// запускаем программу и выводим результат
public static void main(String[] args) {
    // входящие данные
    int l = 900, m = 1000, n = 750, steps = 10;
    int[][] a = randomMatrix(l, m), b = randomMatrix(m, n);
    // произведения матриц
    int[][] c1 = parallelMatrixMultiplication(l, m, n, a, b);
    int[][] c2 = sequentialMatrixMultiplication(l, m, n, a, b);
    // проверяем корректность результатов
    System.out.println("Результаты совпадают: " + Arrays.deepEquals(c1, c2));
    // замеряем время работы двух методов
    benchmark("Потоки", steps, () -> {
        int[][] c = parallelMatrixMultiplication(l, m, n, a, b);
        if (!Arrays.deepEquals(c, c1)) System.out.print("ошибка");
    });
    benchmark("Циклы", steps, () -> {
        int[][] c = sequentialMatrixMultiplication(l, m, n, a, b);
        if (!Arrays.deepEquals(c, c2)) System.out.print("ошибка");
    });
}

Вспомогательные методы

// вспомогательный метод, возвращает матрицу указанного размера
private static int[][] randomMatrix(int row, int col) {
    int[][] matrix = new int[row][col];
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            matrix[i][j] = (int) (Math.random() * row * col);
    return matrix;
}

// вспомогательный метод для замера времени работы переданного кода
private static void benchmark(String title, int steps, Runnable runnable) {
    long time, avg = 0;
    System.out.print(title);
    for (int i = 0; i < steps; i++) {
        time = System.currentTimeMillis();
        runnable.run();
        time = System.currentTimeMillis() - time;
        // время выполнения одного шага
        System.out.print(" | " + time);
        avg += time;
    }
    // среднее время выполнения
    System.out.println(" || " + (avg / steps));
}

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

Результаты совпадают: true
Потоки | 113 | 144 | 117 | 114 | 114 | 117 | 120 | 125 | 111 | 113 || 118
Циклы | 1357 | 530 | 551 | 569 | 535 | 538 | 525 | 517 | 518 | 514 || 615

Сравнение алгоритмов #

На восьмиядерном компьютере Linux x64 создаём для тестов виртуальную машину Windows x64. При прочих равных условиях в настройках меняем количество процессоров. Запускаем вышеописанный тест 100 раз вместо 10 — получаем сводную таблицу результатов. Время в миллисекундах.

   ЦПУ |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |
-------|-----|-----|-----|-----|-----|-----|-----|-----|
Потоки | 522 | 276 | 179 | 154 | 128 | 112 | 110 |  93 |
Циклы  | 519 | 603 | 583 | 571 | 545 | 571 | 559 | 467 |

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

Все описанные выше методы, включая свёрнутые блоки, можно поместить в одном классе.

Необходимые импорты

import java.util.Arrays;
import java.util.stream.IntStream;