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の実装を水から吹き飛ばすでしょうが、私はあなたが楽しく、部分的にエクササイズのためにこれをやっていると仮定しています。

編集：

あなたが分割して（しよう）タスクを並列化する方法がわからないように見えます。最も明白な分割戦略を征服おおよそそのよう、4つの象限に各マトリックスを分割し、n/2 -dimension行列の8回の乗算にn -dimension行列の1回の乗算を翻訳必要：

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 

Strassenののアルゴリズム7にこれを低減することができます非常に正確に選択された行列の操作を使用して、乗算を行うことができる。

また、慎重に選択した配列の繰り返し順序（複数のスレッドを使用することから得られるスピードアップを比較することもできます（Wayne and Sedgewick's illustration hereを参照）。