Как я могу реализовать умножение 2D квадратной матрицы, используя многопоточность в Java?

Question

Я хочу умножить две квадратные 2D-матрицы, используя многопоточность в Java, чтобы сэкономить время.

Каков наилучший способ сделать это? Мой первый приоритет - сэкономить время.

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

Многопоточность должна экономить время, верно?

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Date;
import java.util.Scanner;
import java.util.concurrent.TimeUnit;

public class ExtraTaskOS {

    // Generatining Random Number Method
    static int generateRandomNumber() {

        int number = (int) (Math.random() * (9 - 1)) + 1;
        return number;
    }

    public static void main(String[] args) throws IOException {

        // Store current time
        long startTime = System.nanoTime();

        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of Eelement for both Square Matrix: ");
        int n = sc.nextInt();


        // Generaing First Matrix
        int[][] matrix01 = new int[n][n];

        for (int i = 0; i < matrix01.length; i++) {
            for (int j = 0; j < matrix01.length; j++) {
                matrix01[i][j] = generateRandomNumber();
            }
        }

        // Writing Matrix01 to Text File
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < matrix01.length; i++)//for each row
        {
            for (int j = 0; j < matrix01.length; j++)//for each column
            {
                builder.append(matrix01[i][j] + "");//append to the output string
                if (j < matrix01.length - 1)//if this is not the last row element
                {
                    builder.append(",");//then add comma (if you don't like commas you can use spaces)
                }
            }
            builder.append("\n");//append new line at the end of the row
        }
        BufferedWriter writer = new BufferedWriter(new FileWriter("matrix01.txt"));
        writer.write(builder.toString());//save the string representation of the board
        writer.close();

        // Generating Second Matix
        int[][] matrix02 = new int[n][n];

        for (int i = 0; i < matrix02.length; i++) {
            for (int j = 0; j < matrix02.length; j++) {
                matrix02[i][j] = generateRandomNumber();
            }
        }

        // Writing Matrix02 to Text File
        StringBuilder builder2 = new StringBuilder();

        for (int i = 0; i < matrix02.length; i++)//for each row
        {
            for (int j = 0; j < matrix02.length; j++)//for each column
            {
                builder2.append(matrix02[i][j] + "");//append to the output string
                if (j < matrix02.length - 1)//if this is not the last row element
                {
                    builder2.append(",");//then add comma (if you don't like commas you can use spaces)
                }
            }
            builder2.append("\n");//append new line at the end of the row
        }
        BufferedWriter writer2 = new BufferedWriter(new FileWriter("matrix02.txt"));
        writer2.write(builder2.toString());//save the string representation of the board
        writer2.close();

        // Printing both 2D Arrays
        for (int[] arr : matrix01) {
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("");
        for (int[] arr : matrix02) {
            System.out.println(Arrays.toString(arr));
        }

        // Multiplying both matrix
        int[][] productTwoMatrix = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

              for(int k=0; k<n; k++){
                productTwoMatrix[i][j] += matrix01[i][k] * matrix02[k][j];

              }  

            }
        }

        // Printing Result
        System.out.println("\nResult: ");
        for (int[] arr : productTwoMatrix) {
            System.out.println(Arrays.toString(arr));
        }

        // Calculate Execution time
        long endTime = System.nanoTime();
        long totalTime = endTime - startTime;
        long timeInMiliSecond = (totalTime / 1_000_000);
        System.out.println("Execution Time: "+ timeInMiliSecond + " miliseconds");


    }

}

Новый код, использующий многопоточность, должен сэкономить время.

Answer 1

Во-первых: научитесь правильно измерять свой код.Вы делаете

// Store current time
long startTime = System.nanoTime();

даже до и запрашиваете его ввод у пользователя.Затем вы делаете файл IO и распечатываете разные вещи в System.out.Подсказка: каждое из этих действий, вероятно, займет сотни миллисекунд, ожидание, пока человек введет число ... может занять несколько часов.Таким образом: только измеряет часть, которая действительно имеет значение для вас (это будет часть умножения).Избегайте всех видов операций ввода-вывода во время измерений!

Вы видите, сто миллисекунд, это не очень много звучит, но когда вы сделаете правильные измерения, вы обнаружите, что ваш процессор может сделать кучу вещей за 100 мс (если вы не мешаете всему этомувремя работы ввода-вывода).

Что касается нескольких потоков, вы также идете по неправильной кроличьей норе:

Я хочу умножить две квадратные 2D-матрицы, используя функции многопоточности вЯва, чтобы сэкономить время.

Это (почти) бессмысленно.Видите ли, интенсивная загрузка ЦП приносит , а не выгоду от использования нескольких потоков.В конце CPU должен обратиться к памяти, извлечь значения, сделать несколько вычислений и записать значения в память.Параллельное выполнение этого не обязательно ускоряет процесс.Наоборот, сначала вы должны «заплатить» различные штрафы:

• Создание потока не является дешевой операцией.Вы должны наверняка обработать тысячи элементов, прежде чем один будет оценен для new Thread().
• Когда мы говорим об огромных массивах (и как уже говорилось: маленькие массивы определенно приведут вас хуже результатов при использовании более чем одного потока) ... тогда очень важно, в каком порядке данные запрашиваются из памяти.Вы знаете, у процессоров есть кеши.Отсутствие кэша может быть очень дорогим.И угадайте, что происходит, когда у вас есть несколько потоков, обращающихся к различным частям ваших матриц?Точно: вы, скорее всего, будете причиной этого: кэш пропустит.

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

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

Приятная вещь: вы можете просто «нарезать» данные, которые необходимо обработать.Никакое значение результата не зависит от других результатов, поэтому нет необходимости в синхронизации вообще.Вы можете использовать 1 поток, 2, 4, n, почти столько, сколько вы хотите.

Что я бы посоветовал:

• не запрашивать у пользователя ввода.Просто сгенерируйте матрицы фиксированного размера, например, 100x100, 1000x1000, 10000x10000.
• , возможно, запустите генератор случайных чисел, чтобы все умножения работали с одними и теми же данными.- не печатать весь массив в конце (потому что, как сказано: используйте большие массивы).Массив, который помещается на вашем экране, слишком мал, чтобы дать вам какие-либо значимые измерения.Но, например, сумма до итоговой матрицы (чтобы избежать того, что JIT оптимизирует всю операцию: вам нужно убедиться, что некоторый результат вашей операции каким-либо образом используется)
• попробуйте написать код, который позволяет быстро изменять количество потоков, не меняя ничего другого.Так что вы можете многократно использовать потоки 1, 2, 4, 8, 16.

И когда вы закончите с использованием необработанных «голых металлических» потоков, скопируйте свой код, удалите все содержимое потокаи попробуйте реализовать матричное умножение, используя ExecutorService .Когда это сработает, сделайте еще один шаг и посмотрите на Futures и подумайте, как их можно использовать здесь.

Как уже говорилось: вы не должны делать это ради производительности.Единственная веская причина, по которой вы пишете такой код, - это научиться делать это (верно).