Hindernisse für die Parallelisierung

• Loop Carried Dependencies (LCD)
  • forward:

           DO I = 1, N-1
             A(I) = A(I) + A(I+1)
           ENDDO
    

  • backward:

           DO I = 3, N
             A(I) = A(I-1) + A(I-2)
           ENDDO
    

  • output:

           DO I = 1, N 
             A(J(I)) = B(I)
           ENDDO
    

    etwa: J(28) = J(42) = 17
    $\rightarrow$ A(17) hängt von Reihenfolge ab

• Aliasing

  void f(double a[], double b[], int n)
  {
     int i;
     for (i=0; i<n; i++)
     {
        a[i] = b[i];
     }
  }
  
  double a[100];
  f(a+1, a, 99);
  

• Calls (außer Intrinsics)
  mögliche Seiteneffekte!
• mehrfache entries/exits der Loop

     for (i=0; i<n; i++)
     {
        if (b[i] < 0.0) break;
        a[i] = b[i];
     }
  

Compiler parallelisiert automatisch:

• implizite Fortran90-Loop:

      X(1:M) = X(2:M+1)
  

  Fortran90: keine LCDs!

• LCD durch skalare Variable:

      DO I = 1, 1000
        S    = A(I) + B(I)
        C(I) = 2 * S
      ENDDO
  

• Reduktion:

      SUM = 0.0
      DO I = 1, 4711
        SUM = SUM + A(I)
      ENDDO