계산 행렬 결정자

Question

자기 코딩/인터뷰 연습을 위해 (모든 크기의) 행렬의 행렬식을 계산하려고합니다. 내 첫 번째 시도는 재귀를 사용하고 그 다음 구현 날 리드 :

import java.util.Scanner.*; 
public class Determinant { 

    double A[][]; 
    double m[][]; 
    int N; 
     int start; 
     int last; 

     public Determinant (double A[][], int N, int start, int last){ 
      this.A = A; 
      this.N = N; 
      this.start = start; 
      this.last = last; 
     } 

     public double[][] generateSubArray (double A[][], int N, int j1){ 
      m = new double[N-1][]; 
      for (int k=0; k<(N-1); k++) 
        m[k] = new double[N-1]; 

      for (int i=1; i<N; i++) 
      { 
        int j2=0; 
        for (int j=0; j<N; j++) 
        { 
         if(j == j1) 
           continue; 
         m[i-1][j2] = A[i][j]; 
         j2++; 
        } 
      } 
      return m; 
     } 
    /* 
    * Calculate determinant recursively 
    */ 
    public double determinant(double A[][], int N) 
    { 
     double res; 

     // Trivial 1x1 matrix 
     if (N == 1) 
      res = A[0][0]; 
     // Trivial 2x2 matrix 
     else if (N == 2) 
      res = A[0][0]*A[1][1] - A[1][0]*A[0][1]; 
     // NxN matrix 
     else 
     { 
      res=0; 
      for (int j1=0; j1<N; j1++) 
      { 
          m = generateSubArray (A, N, j1); 
          res += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * determinant(m, N-1); 
      } 
     } 
     return res; 
    } 
} 

것은 지금까지 모두 좋은 그것은 나에게 정확한 결과를 제공합니다. 이제이 결정 변수 값을 계산하기 위해 여러 스레드를 사용하여 코드를 최적화하고 싶습니다. Java Fork/Join 모델을 사용하여 병렬 처리하려고했습니다.

이

@Override 
     protected Double compute() { 
      if (N < THRESHOLD) { 
       result = computeDeterminant(A, N); 
       return result; 
      } 

      for (int j1 = 0; j1 < N; j1++){ 
       m = generateSubArray (A, N, j1); 
       ParallelDeterminants d = new ParallelDeterminants (m, N-1); 
       d.fork(); 
       result += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * d.join(); 
      } 

      return result; 
     } 

    public double computeDeterminant(double A[][], int N) 
    { 
     double res; 

     // Trivial 1x1 matrix 
     if (N == 1) 
      res = A[0][0]; 
     // Trivial 2x2 matrix 
     else if (N == 2) 
      res = A[0][0]*A[1][1] - A[1][0]*A[0][1]; 
     // NxN matrix 
     else 
     { 
      res=0; 
      for (int j1=0; j1<N; j1++) 
      { 
          m = generateSubArray (A, N, j1); 
          res += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * computeDeterminant(m, N-1); 
      } 
     } 
     return res; 
    } 

/* 
* Main function 
*/ 
public static void main(String args[]) 
{ 
    double res; 
      ForkJoinPool pool = new ForkJoinPool(); 
      ParallelDeterminants d = new ParallelDeterminants(); 
      d.inputData(); 
    long starttime=System.nanoTime(); 
      res = pool.invoke (d); 
    long EndTime=System.nanoTime(); 

    System.out.println("Seq Run = "+ (EndTime-starttime)/100000); 
    System.out.println("the determinant valaue is " + res); 
} 

그러나 성능을 비교 한 후, 내가 처음에 비해 (포크의 성능/접근에 참여하는 것은 아주 나쁜, 그리고 매트릭스 차원 높은이 느린가 될 것을 발견 : 이것은 나의 접근 방식이다 접근). 오버 헤드는 어디에 있습니까? 누구든지 이것을 향상시킬 수있는 방법을 밝힐 수 있습니까?

Answer 1

ForkJoin 코드의 속도가 느린 주된 이유는 실제로 스레드 오버 헤드가 발생하여 직렬화되기 때문입니다. fork/join의 이점을 원하면 모든 인스턴스를 먼저 fork 한 다음 결과를 기다려야합니다. "계산"에서 루프를 두 개의 루프로 분할합니다. 하나는 포크 (예 : 배열에 ParallelDeterminants의 인스턴스를 저장함)이고 다른 하나는 결과를 수집하는 루프입니다.

또한 가장 바깥 쪽 수준에서만 포크를 사용하고 내부 수준에서는 포크를 사용하지 않는 것이 좋습니다. O (N^2) 개의 쓰레드를 생성하고 싶지는 않습니다.