Страницы

Поиск по вопросам

среда, 12 декабря 2018 г.

Как правильно умножить матрицу на другую матрицу в нескольких потоках?

Моя задача такая. Мне нужно параллельно на 8 потоках умножить матрицу 200x248 на матрицу 248x333. В интернете я нашел простой пример умножения двух матриц 4x4 на 4 потоках, но я не совсем понимаю логику разделения этой задачи между потоками. Почему у каждого потока разные границы циклов и как они вообще образовываются? Почему в каждом потоке аж 3 цикла, а не 2? Можете мне объяснить алгоритм, чтобы я мог по его аналогии сделать умножение огромных матриц на 8 потоках?
Вот часть этого кода (там еще есть ввод данных с файла и вывод результата в другой файл, графический интерфейс и другое, но это не столь важно в этом вопросе).
Инициализация статических полей:
public static int[][] a; public static int[][] b; public static int[][] c;
Где-то в main создаются и запускаются потоки:
c = new int[a.length][b[0].length];
Thread1 thread1 = new Thread1(); Thread2 thread2 = new Thread2(); Thread3 thread3 = new Thread3(); Thread4 thread4 = new Thread4();
thread1.start(); thread2.start(); thread3.start(); thread4.start();
try { thread1.join(); } catch (InterruptedException e) { e.printStackTrace(); }
try { thread2.join(); } catch (InterruptedException e) { e.printStackTrace(); }
try { thread3.join(); } catch (InterruptedException e) { e.printStackTrace(); }
try { thread4.join(); } catch (InterruptedException e) { e.printStackTrace(); }
Код четырех потоков:
public static class Thread1 extends Thread {
@Override public void run() { int m = a.length; int n = b[0].length; int k = (a.length) / 4;
for (int i = 0; i <= k; i++) { for (int j = 0; j < n; j++) { for (int l = 0; l < b.length; l++) { c[i][j] = c[i][j] + a[i][l] * b[l][j]; } } } } }
public static class Thread2 extends Thread {
@Override public void run() { int m = a.length; int n = b[0].length; int k = (a.length) / 2 + 1; int s = ((a.length) / 4) + 1;
for (int i = s; i < k; i++) { for (int j = 0; j < n; j++) { for (int l = 0; l < b.length; l++) { c[i][j] = c[i][j] + a[i][l] * b[l][j]; } } } } }
public static class Thread3 extends Thread {
@Override public void run() { int m = a.length; int n = b[0].length; int k = ((3 * (a.length)) / 4) + 1; int s = (a.length) / 2 + 1;
for (int i = s; i < k; i++) { for (int j = 0; j < n; j++) { for (int l = 0; l < b.length; l++) { c[i][j] = c[i][j] + a[i][l] * b[l][j]; } } } } }
public static class Thread4 extends Thread {
@Override public void run() { int m = a.length; int n = b[0].length; int k = ((3 * (a.length)) / 4) + 1;
for (int i = k; i < m; i++) { for (int j = 0; j < n; j++) { for (int l = 0; l < b.length; l++) { c[i][j] = c[i][j] + a[i][l] * b[l][j]; } } } } }


Ответ

Полная тестовая программа, вычисляющая произведение матриц в несколько потоков. В отличие от предложенного в другом ответе варианта, распределяет вычисления между потоками более "справедливо". Поток не обязательно вычисляет строку новой матрицы целиком, вычисления могут начинаться и заканчиваться на любой ячейке матрицы.
import java.io.FileWriter; import java.io.IOException; import java.util.Random;
/** Поток-вычислитель группы ячеек матрицы. */ class MultiplierThread extends Thread { /** Первая (левая) матрица. */ private final int[][] firstMatrix; /** Вторая (правая) матрица. */ private final int[][] secondMatrix; /** Результирующая матрица. */ private final int[][] resultMatrix; /** Начальный индекс. */ private final int firstIndex; /** Конечный индекс. */ private final int lastIndex; /** Число членов суммы при вычислении значения ячейки. */ private final int sumLength;
/** * @param firstMatrix Первая (левая) матрица. * @param secondMatrix Вторая (правая) матрица. * @param resultMatrix Результирующая матрица. * @param firstIndex Начальный индекс (ячейка с этим индексом вычисляется). * @param lastIndex Конечный индекс (ячейка с этим индексом не вычисляется). */ public MultiplierThread(final int[][] firstMatrix, final int[][] secondMatrix, final int[][] resultMatrix, final int firstIndex, final int lastIndex) { this.firstMatrix = firstMatrix; this.secondMatrix = secondMatrix; this.resultMatrix = resultMatrix; this.firstIndex = firstIndex; this.lastIndex = lastIndex;
sumLength = secondMatrix.length; }
/**Вычисление значения в одной ячейке. * * @param row Номер строки ячейки. * @param col Номер столбца ячейки. */ private void calcValue(final int row, final int col) { int sum = 0; for (int i = 0; i < sumLength; ++i) sum += firstMatrix[row][i] * secondMatrix[i][col]; resultMatrix[row][col] = sum; }
/** Рабочая функция потока. */ @Override public void run() { System.out.println("Thread " + getName() + " started. Calculating cells from " + firstIndex + " to " + lastIndex + "...");
final int colCount = secondMatrix[0].length; // Число столбцов результирующей матрицы. for (int index = firstIndex; index < lastIndex; ++index) calcValue(index / colCount, index % colCount);
System.out.println("Thread " + getName() + " finished."); } }
class Main { /** Заполнение матрицы случайными числами. * * @param matrix Заполняемая матрица. */ private static void randomMatrix(final int[][] matrix) { final Random random = new Random(); // Генератор случайных чисел.
for (int row = 0; row < matrix.length; ++row) // Цикл по строкам матрицы. for (int col = 0; col < matrix[row].length; ++col) // Цикл по столбцам матрицы. matrix[row][col] = random.nextInt(100); // Случайное число от 0 до 100. }
//
/** Вывод матрицы в файл. * Производится выравнивание значений для лучшего восприятия. * * @param fileWriter Объект, представляющий собой файл для записи. * @param matrix Выводимая матрица. * @throws IOException */ private static void printMatrix(final FileWriter fileWriter, final int[][] matrix) throws IOException { boolean hasNegative = false; // Признак наличия в матрице отрицательных чисел. int maxValue = 0; // Максимальное по модулю число в матрице.
// Вычисляем максимальное по модулю число в матрице и проверяем на наличие отрицательных чисел. for (final int[] row : matrix) { // Цикл по строкам матрицы. for (final int element : row) { // Цикл по столбцам матрицы. int temp = element; if (element < 0) { hasNegative = true; temp = -temp; } if (temp > maxValue) maxValue = temp; } }
// Вычисление длины позиции под число. int len = Integer.toString(maxValue).length() + 1; // Одно знакоместо под разделитель (пробел). if (hasNegative) ++len; // Если есть отрицательные, добавляем знакоместо под минус.
// Построение строки формата. final String formatString = "%" + len + "d";
// Вывод элементов матрицы в файл. for (final int[] row : matrix) { // Цикл по строкам матрицы. for (final int element : row) // Цикл по столбцам матрицы. fileWriter.write(String.format(formatString, element));
fileWriter.write("
"); // Разделяем строки матрицы переводом строки. } }
/** * Вывод трёх матриц в файл. Файл будет перезаписан. * * @param fileName Имя файла для вывода. * @param firstMatrix Первая матрица. * @param secondMatrix Вторая матрица. * @param resultMatrix Результирующая матрица. */ private static void printAllMatrix(final String fileName, final int[][] firstMatrix, final int[][] secondMatrix, final int[][] resultMatrix) { try (final FileWriter fileWriter = new FileWriter(fileName, false)) { fileWriter.write("First matrix:
"); printMatrix(fileWriter, firstMatrix);
fileWriter.write("
Second matrix:
"); printMatrix(fileWriter, secondMatrix);
fileWriter.write("
Result matrix:
"); printMatrix(fileWriter, resultMatrix); } catch (IOException e) { e.printStackTrace(); } }
/** Однопоточное умножение матриц. * * @param firstMatrix Первая матрица. * @param secondMatrix Вторая матрица. * @return Результирующая матрица. */ private static int[][] multiplyMatrix(final int[][] firstMatrix, final int[][] secondMatrix) { final int rowCount = firstMatrix.length; // Число строк результирующей матрицы. final int colCount = secondMatrix[0].length; // Число столбцов результирующей матрицы. final int sumLength = secondMatrix.length; // Число членов суммы при вычислении значения ячейки. final int[][] result = new int[rowCount][colCount]; // Результирующая матрица.
for (int row = 0; row < rowCount; ++row) { // Цикл по строкам матрицы. for (int col = 0; col < colCount; ++col) { // Цикл по столбцам матрицы. int sum = 0; for (int i = 0; i < sumLength; ++i) sum += firstMatrix[row][i] * secondMatrix[i][col]; result[row][col] = sum; } }
return result; }
/** Многопоточное умножение матриц. * * @param firstMatrix Первая (левая) матрица. * @param secondMatrix Вторая (правая) матрица. * @param threadCount Число потоков. * @return Результирующая матрица. */ private static int[][] multiplyMatrixMT(final int[][] firstMatrix, final int[][] secondMatrix, int threadCount) { assert threadCount > 0;
final int rowCount = firstMatrix.length; // Число строк результирующей матрицы. final int colCount = secondMatrix[0].length; // Число столбцов результирующей матрицы. final int[][] result = new int[rowCount][colCount]; // Результирующая матрица.
final int cellsForThread = (rowCount * colCount) / threadCount; // Число вычисляемых ячеек на поток. int firstIndex = 0; // Индекс первой вычисляемой ячейки. final MultiplierThread[] multiplierThreads = new MultiplierThread[threadCount]; // Массив потоков.
// Создание и запуск потоков. for (int threadIndex = threadCount - 1; threadIndex >= 0; --threadIndex) { int lastIndex = firstIndex + cellsForThread; // Индекс последней вычисляемой ячейки. if (threadIndex == 0) { /* Один из потоков должен будет вычислить не только свой блок ячеек, но и остаток, если число ячеек не делится нацело на число потоков. */ lastIndex = rowCount * colCount; } multiplierThreads[threadIndex] = new MultiplierThread(firstMatrix, secondMatrix, result, firstIndex, lastIndex); multiplierThreads[threadIndex].start(); firstIndex = lastIndex; }
// Ожидание завершения потоков. try { for (final MultiplierThread multiplierThread : multiplierThreads) multiplierThread.join(); } catch (InterruptedException e) { e.printStackTrace(); }
return result; }
/** Число строк первой матрицы. */ final static int FIRST_MATRIX_ROWS = 1000; /** Число столбцов первой матрицы. */ final static int FIRST_MATRIX_COLS = 1000; /** Число строк второй матрицы (должно совпадать с числом столбцов первой матрицы). */ final static int SECOND_MATRIX_ROWS = FIRST_MATRIX_COLS; /** Число столбцов второй матрицы. */ final static int SECOND_MATRIX_COLS = 1000;
public static void main(String[] args) { final int[][] firstMatrix = new int[FIRST_MATRIX_ROWS][FIRST_MATRIX_COLS]; // Первая (левая) матрица. final int[][] secondMatrix = new int[SECOND_MATRIX_ROWS][SECOND_MATRIX_COLS]; // Вторая (правая) матрица.
randomMatrix(firstMatrix); randomMatrix(secondMatrix);
final int[][] resultMatrixMT = multiplyMatrixMT(firstMatrix, secondMatrix, Runtime.getRuntime().availableProcessors());
// Проверка многопоточных вычислений с помощью однопоточных. final int[][] resultMatrix = multiplyMatrix(firstMatrix, secondMatrix);
for (int row = 0; row < FIRST_MATRIX_ROWS; ++row) { for (int col = 0; col < SECOND_MATRIX_COLS; ++col) { if (resultMatrixMT[row][col] != resultMatrix[row][col]) { System.out.println("Error in multithreaded calculation!"); return; } } }
printAllMatrix("Matrix.txt", firstMatrix, secondMatrix, resultMatrixMT); } }
P.S. Среди особенностей - форматированный вывод матриц в файл и автоматическое определение размера матриц в функциях-вычислителях. В качестве бонуса - однопоточное вычисление и контроль многопоточного результата с помощью однопоточного.

Комментариев нет:

Отправить комментарий