4.1.1.1 Determining the inner product on a vector unit

• sequential :

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

  The sum above cannot be vectorized and so the whole algorithm cannot be vectorized.
• vektorized/sequential :

  
       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
  

  Here, the first loop but not the second loop is vectorized. The vectorization of that second loop can be done by means of cyclic reduction technique.
• vectorized/cyclic reduction : For simplicity assume $n=2^d$, otherwise the notation would be more complicated.

  
       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$
  

  The technique of cyclic reduction is also known as cascadic algorithm or as recursive doubling and is quite often used in parallelization. The vector length handled in the inner loop gets smaller with increasing index of the outer loop but it uses the vector unit at least partially. The coincidence between cyclic reduction and a REDUCE operation in a binary tree (Sect. 3.3.4) can be seen in Fig. 4.1.

Figure 4.1: Cyclic reduction $n=8$