4.1.1.1 Berechnung des Skalarproduktes auf Vektorrechnern

• sequentiell :

  
       $s \;:=\; 0$
  
  
  DO $i \,=\, 1,\, n$
  
  		      $s \;:=\; s + \underbrace{x_i \ast y_i}_{vektorisierbar}$
  
  
  END DO
  

  Da obige Summation aber nicht vektorisierbar ist, ist auch der Gesamtalgorithmus nicht vektorisierbar.
• vektorisiert/sequentiell :

  
       DO $i \,=\, 1,\, n$
  
  		      $d_i \;:=\; x_i \ast y_i$
  
  
  END DO 
       $s \;:=\; 0$
  
  
  DO $i \,=\, 1,\, n$
  
  		      $s \;:=\; s +d_i$
  
  
  END DO
  

  Hier ist die erste Schleife Vektorisiert, jedoch die zweite noch nicht. Um auch die zweite Schleife zu vektorisieren, muß man mit der Technik des rekursiven Doppelns arbeiten.
• vektorisiert/ rekursives Doppeln : Sei $n=2^d$, ansonsten ist der folgende Algorithmus etwas schwerer aufzuschreiben.

  
       DO $i \,=\, 1,\, n$
  
  		      $d_i \;:=\; x_i \ast y_i$
  
  
  END DO 
  
  DO $\ell \,=\, 1,\,\log_2(n)$
  
  		      $is \;:=\; 2^\ell$
  
  
  DO $i \,=\, is,\, n,\,is$
  
  		 		       $d_i \;:=\; d_i +d_{i-is/2}$
  
  
  END DO  
  
  END DO  
       $s \,:=\, d_n$
  

  Das rekursive Doppeln in der zweiten Schleife, auch Kaskadenalgorithmus bzw. zyklische Reduktion genannt, arbeitet zwar mit immer kürzeren Vektoren, nutzt jedoch die Möglichkeiten des Vektorrechners zumindest teilweise aus. In Abbildung 4.1 ist deutlich die Äquivalenz zwischen dem rekursiven Doppeln und der REDUCE Operation im binären Baum (Abschnitt 3.3.4) erkennbar. Wir werden dieser zyklischen Reduktion auch bei der Parallelisierung immer wieder begegnen.

  

Abbildung 4.1: Illustration rekursives Doppeln $n=8$