Explication de la mise en œuvre parallèle ou sérielle

Question

J'ai mis en œuvre un algorithme série et parallèle pour la résolution de systèmes linéaires utilisant la méthode jacobi. Les deux implémentations convergent et donnent des solutions correctes.

J'éprouve des difficultés avec la compréhension:

1. Comment la mise en œuvre parallèle après convergent si faible nombre d'itérations par rapport à série (même méthode est utilisée dans les deux). Est-ce que je suis confronté à des problèmes de concurrence que je ne connais pas?
2. Comment le nombre d'itérations peut-il varier d'une exécution à l'autre en implémentation parallèle (6,7)?

Merci!

sortie du programme:

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] 

code:

principal

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))); 


    } 

} 

données

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]; 


} 

parallèle

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; 

      } 

     } 

    } 

série

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

Je pense que une question de mise en œuvre et non parallélisation. Regardez ce qui se passe avec 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] 

Comme il se trouve - votre deuxième mise en œuvre ne fait pas exactement la même chose que votre premier. J'ai ajouté cela dans votre version parallèle et il a couru dans le même nombre d'itérations. Que se passe-t-il avec 1 travailleur?

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]; 
     } 
}