Умножение параллельной матрицы Java

Question

Может кто-нибудь помочь мне с этим, пожалуйста? Я пытаюсь сделать матричное умножение, используя параллельное программирование - Java. Это то, что я пытался до сих пор

public class MatrixParallel22 extends Thread{ 
final static int noThreads = 2 ; 
public static void main(String args[]) throws Exception{ 
    //get the start time 
    long startTime = System.currentTimeMillis(); 

    MatrixParallel [] threads = new MatrixParallel [noThreads] ; 
    for(int me = 0 ; me < noThreads ; me++) { 
     threads [me] = new MatrixParallel(me) ; 
     threads [me].start() ; 
    } 

    for(int me = 0 ; me < noThreads ; me++) { 
     threads [me].join() ; 
    } 

    long endTime = System.currentTimeMillis(); 

    System.out.println("Calculation completed in " + 
         (endTime - startTime) + " milliseconds"); 
} 
int me ; 
public MatrixParallel(int me) { 
     this.me = me ; 
    } 
public void run() { 

    //generate two matrices using random numbers 
    int matrix1 [][] = matrixGenerator(); 
    int matrix2 [][] = matrixGenerator(); 

    //get the number of rows from the first matrix 
    int m1rows = matrix1.length; 
    //get the number of columns from the first matrix 
    int m1cols = matrix1[0].length; 
    //get the number of columns from the second matrix 
    int m2cols = matrix2[0].length; 

    //multiply the matrices and put the result in an array 
    int[][] result = new int[m1rows][m2cols]; 
     for (int i=0; i< m1rows; i++){ 
      for (int j=0; j< m2cols; j++){ 
       for (int k=0; k< m1cols; k++){ 
       result[i][j] += matrix1[i][k] * matrix2[k][j]; 
      } 
     } 
    }   

} 
public static int[][] matrixGenerator(){ 
    //create an array 
    int matrix [][] = new int[550][550]; 
    //create a random generator 
    //and fill it with random numbers 
    Random r = new Random(); 
    for(int i=0; i < matrix.length; i++){ 
     for(int j=0; j < matrix[i].length; j++){ 
      matrix[i][j] = r.nextInt(10000); 
     } 
    } 
    return matrix; 
} 

}

В этом случае, я пытаюсь настроить количество потоков в переменной, а затем измерить и посмотреть, как быстро программа если я увеличиваю/уменьшаю количество потоков.

// update - Когда я выполняю код .. он отлично работает. Но дело в том, что если я увеличиваю количество потоков, время выполнения будет медленнее. Например, с 2 потоками я получаю 316 миллисекунд и с 8 потоками получаю 755 миллисекунд Я не знаю, какая часть не так. Так я выполняю потоки?

Answer 1

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

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

Что касается ускорения реализации простого матричного умножения в Java, есть много похожих вопросов с очень хорошими ответами (например, Peter Lawrey's answer here).

Если вы действительно используете матрицы, большие (n> 500), вы также можете попробовать Strassen's algorithm. Конечно, любой из специализированных инструментов для матричного умножения выведет простую реализацию Java из воды, но я предполагаю, что вы делаете это отчасти для удовольствия и отчасти в качестве упражнения.

Edit:

Похоже, что вы не знаете, как разделить и (попытаться) распараллелить задачу. Наиболее очевидным разделяй и властвуй стратегия требует разбиения каждой матрицы в 4 квадрантах и ​​перевод 1 умножение n -размерности матриц в 8 умножений n/2 -размерности матриц, примерно так:

A11 | A12  B11 | B12  A11*B11 | A11*B12  A12*B21 | A12*B22 
|----+----| x |----+----| = |--------+--------| + |---------+-------| 
A21 | A22  B21 | B21  A21*B11 | A21*B21  A22*B21 | A22*B22 

алгоритм Штрассена может уменьшить это до 7 умножения, используя очень точно выбранные манипуляции с A _ij и B _ij матрицы.

Вы также можете сравнить скорость, которую вы получаете, используя несколько потоков с ускорением из тщательно выбранного порядка итерации массива (см. Wayne and Sedgewick's illustration here).