並行與串行實現的解釋

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

我認爲它的實現，而不是並行的問題。再看一下與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]; 
     } 
}