並列対直列実装の説明

Question

jacobiメソッドを使用して線形システムを解くための直列アルゴリズムと並列アルゴリズムを実装しました。両方の実装が収束し、正しい解決策を提供します。

は、私が理解した上でトラブルを抱えています：

実装を平行するにはどうすればよい

1. が（両方で使用されているのと同じ方法で）シリアルに比べ、反復の非常に低い番号の後に収束します。私が気づいていないいくつかの並行性の問題に直面していますか？
2. 並列実装（6,7）では、繰り返し実行回数はどのように変化しますか？

ありがとう！

プログラムの出力：

Mathematica solution: {{-1.12756}, {4.70371}, {-1.89272}, {1.56218}} 
Serial: iterations=7194 , error=false, solution=[-1.1270591, 4.7042074, -1.8922218, 1.5626835] 
Parallel: iterations=6 , error=false, solution=[-1.1274619, 4.7035804, -1.8927546, 1.5621948] 

コード：

メイン

import java.util.Arrays; 

public class Main { 

    public static void main(String[] args) { 

     Serial s = new Serial(); 
     Parallel p = new Parallel(2); 

     s.solve(); 
     p.solve(); 

     System.out.println("Mathematica solution: {{-1.12756}, {4.70371}, {-1.89272}, {1.56218}}"); 
     System.out.println(String.format("Serial: iterations=%d , error=%s, solution=%s", s.iter, s.errorFlag, Arrays.toString(s.data.solution))); 
     System.out.println(String.format("Parallel: iterations=%d , error=%s, solution=%s", p.iter, p.errorFlag, Arrays.toString(p.data.solution))); 


    } 

} 

データ

public class Data { 

    public float A[][] = {{2.886139567217389f, 0.9778259187352214f, 0.9432146432722157f, 0.9622157488990459f} 
         ,{0.3023479007910952f,0.7503803506938734f,0.06163831478699766f,0.3856445043958068f} 
         ,{0.4298384105199724f, 0.7787439716945019f, 1.838686110345417f, 0.6282668788698587f} 
         ,{0.27798718418255075f, 0.09021764079496353f, 0.8765867330141233f, 1.246036349549629f}}; 

    public float b[] = {1.0630309381779384f,3.674438173599066f,0.6796639099285651f,0.39831385324794155f}; 
    public int size = A.length; 
    public float x[] = new float[size]; 
    public float solution[] = new float[size]; 


} 

パラレル

import java.util.Arrays; 

    public class Parallel { 


     private final int workers; 
     private float[] globalNorm; 

     public int iter; 
     public int maxIter = 1000000; 
     public double epsilon = 1.0e-3; 
     public boolean errorFlag = false; 

     public Data data = new Data(); 

     public Parallel(int workers) { 
      this.workers = workers; 
      this.globalNorm = new float[workers]; 
      Arrays.fill(globalNorm, 0); 
     } 

     public void solve() { 

      JacobiWorker[] threads = new JacobiWorker[workers]; 
      int batchSize = data.size/workers; 

      float norm; 

      do { 


       for(int i=0;i<workers;i++) { 
        threads[i] = new JacobiWorker(i,batchSize); 
        threads[i].start(); 
       } 

       for(int i=0;i<workers;i++) 
        try { 

         threads[i].join(); 

        } catch (InterruptedException e) { 

         e.printStackTrace(); 
        } 

       // At this point all worker calculations are done! 

       norm = 0; 

       for (float d : globalNorm) if (d > norm) norm = d; 

       if (norm < epsilon) 
        errorFlag = false; // Converged 
       else 
        errorFlag = true; // No desired convergence 

      } while (norm >= epsilon && ++iter <= maxIter); 

     } 

     class JacobiWorker extends Thread { 

      private final int idx; 
      private final int batchSize; 

      JacobiWorker(int idx, int batchSize) { 
       this.idx = idx; 
       this.batchSize = batchSize; 
      } 

      @Override 
      public void run() { 

       int upper = idx == workers - 1 ? data.size : (idx + 1) * batchSize; 

       float localNorm = 0, diff = 0; 

       for (int j = idx * batchSize; j < upper; j++) { // For every 
                   // equation in batch 

        float s = 0; 
        for (int i = 0; i < data.size; i++) { // For every variable in 
                  // equation 

         if (i != j) 
          s += data.A[j][i] * data.x[i]; 

         data.solution[j] = (data.b[j] - s)/data.A[j][j]; 

        } 


        diff = Math.abs(data.solution[j] - data.x[j]); 
        if (diff > localNorm) localNorm = diff; 
        data.x[j] = data.solution[j]; 


       } 


       globalNorm[idx] = localNorm; 

      } 

     } 

    } 

シリアル

public class Serial { 

    public int iter; 
    public int maxIter = 1000000; 
    public double epsilon = 1.0e-3; 
    public boolean errorFlag = false; 

    public Data data = new Data(); 

    public void solve() { 

     float norm,diff=0; 

     do { 


      for(int i=0;i<data.size;i++) { 

       float s=0; 
       for (int j = 0; j < data.size; j++) { 
        if (i != j) 
         s += data.A[i][j] * data.x[j]; 
        data.solution[i] = (data.b[i] - s)/data.A[i][i]; 
       } 
      } 


      norm = 0; 

      for (int i=0;i<data.size;i++) { 
       diff = Math.abs(data.solution[i]-data.x[i]); // Calculate convergence 
       if (diff > norm) norm = diff; 
       data.x[i] = data.solution[i]; 
      } 


      if (norm < epsilon) 
       errorFlag = false; // Converged 
      else 
       errorFlag = true; // No desired convergence 


     } while (norm >= epsilon && ++iter <= maxIter); 

    } 
} 

Answer 1

私は実装していない並列化のその問題を考えます。 2番目の実装は、あなたの最初のものとまったく同じことをやっていません - それは結局のところParallel p = new Parallel(1);

Mathematica solution: {{-1.12756}, {4.70371}, {-1.89272}, {1.56218}} 
Serial: iterations=7194 , error=false, solution=[-1.1270591, 4.7042074, -1.8922218, 1.5626835] 
Parallel: iterations=6 , error=false, solution=[-1.1274619, 4.7035804, -1.8927546, 1.5621948] 

で何が起こるかを見てください。

これを並列バージョンに追加しましたが、同じ繰り返し回数で実行されました。

for (int i = idx * batchSize; i < upper; i++) { 
    diff = Math.abs(data.solution[i] - data.x[i]); // Calculate 
     // convergence 
     if (diff > localNorm) 
      localNorm = diff; 
      data.x[i] = data.solution[i]; 
     } 
}