Рассмотрим алгоритм перемножения прямоугольных матриц с использованием потоков 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;
© Головин Г.Г., Код с комментариями, 2022