Моя задача такая. Мне нужно параллельно на 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. Среди особенностей - форматированный вывод матриц в файл и автоматическое определение размера матриц в функциях-вычислителях. В качестве бонуса - однопоточное вычисление и контроль многопоточного результата с помощью однопоточного.
Комментариев нет:
Отправить комментарий