Using Automatic Vectorization

Vectorization Speed-up

Where does the vectorization speedup come from? Consider the following sample code fragment, where a, b and c are integer arrays:

for (I=0;i<=MAX;i++)
   c[i]=a[i]+b[i];

If vectorization is not enabled (that is, you compile using O1 or [Q]vec- options), for each iteration, the compiler processes the code such that there is a lot of unused space in the SIMD registers, even though each of the registers could hold three additional integers. If vectorization is enabled (compiled using O2 or higher options), the compiler may use the additional registers to perform four additions in a single instruction. The compiler looks for vectorization opportunities whenever you compile at default optimization (O2) or higher.

To get information on whether a loop was vectorized or not, enable generation of the vectorization report using the [Q]vec-report[:]1 or [Q]opt-report-phase hpo options. You will get a one line message for every loop that is vectorized, as follows:

> icl /Qvec-report1 Multiply.c 
Multiply.c(92): (col. 5) remark: LOOP WAS VECTORIZED.

The source line number (92 in the above example) refers to either the beginning or the end of the loop.

To get details about the type of loop transformations and optimizations that took place, use the [Q]opt-report-phase hpo option by itself or along with the [Q]opt-report option.

How significant is the performance enhancement? To evaluate performance enhancement yourself, run vec_samples:

1. Open an Intel® Fortran Compiler command line window.

   • On Windows*: Go to Start > All Programs > Intel Parallel Studio > Intel C++ Compiler Professions > C++ build environment for applications running on …

   • On Linux* and OS X*: Source an environment script such as iccvars_intel64.sh in the compiler /bin/intel64 directory, or iccvars_ia32.sh in the /bin/ia32 directory, as appropriate.

2. Navigate to the <install-dir>\Samples\<locale>\C++\ directory. Open the sample project vec_samples.zip. The small application multiplies a vector by a matrix using the following loop:

3. for (j = 0;j < size2; j++) { b[i] += a[i][j] * x[j]; }

   Build and run the application, first without enabling auto-vectorization. Note the time taken for the application to run.

   // (Linux* and OS X*)
   icc -O2 -no-vec  Multiply.c -o NoVectMult 
   ./NoVectMult

   // (Windows*)
   icl /O2 /Qvec- Multiply.c /FeNoVectMult 
   NoVectMult

4. Now build and run the application, this time enabling auto-vectorization. Note the time taken for the application to run.

   // (Linux* and OS X*)
   icc -O2 -vec-report1 Multiply.c -o VectMult 
   ./VectMult

   // (Windows*)
   icl /O2 /Qvec-report1 Multiply.c /FeVectMult 
   VectMult

When you compare the timing of the two runs, you may see that the vectorized version runs faster. The time for the non-vectorized version is only slightly faster than would be obtained by compiling with the O1 option.

Obstacles to Vectorization

The following do not always prevent vectorization, but frequently either prevent it or cause the compiler to decide that vectorization would not be worthwhile.

• Non-contiguous memory access: Four consecutive integers or floating-point values, or two consecutive doubles, may be loaded directly from memory in a single SSE instruction. But if the four integers are not adjacent, they must be loaded separately using multiple instructions, which is considerably less efficient. The most common examples of non-contiguous memory access are loops with non-unit stride or with indirect addressing, as in the examples below. The compiler rarely vectorizes such loops, unless the amount of computational work is large compared to the overhead from non-contiguous memory access.

  // arrays accessed with stride 2 
  for (int I=0; i<SIZE; I+=2)  b[i] += a[i] * x[i]; 
  // inner loop accesses a with stride SIZE 
  for (int j=0; j<SIZE; j++)  {
    for (int I=0; i<SIZE; I++)   b[i] += a[i][j] * x[j]; 
  } 
  
  // indirect addressing of x using index array
    for (int I=0; i<SIZE; I+=2)  b[i] += a[i] * x[index[i]];

  The typical message from the vectorization report is: vectorization possible but seems inefficient, although indirect addressing may also result in the following report: Existence of vector dependence.

• Data dependencies: Vectorization entails changes in the order of operations within a loop, since each SIMD instruction operates on several data elements at once. Vectorization is only possible if this change of order does not change the results of the calculation.
  • The simplest case is when data elements that are written (stored to) do not appear in any other iteration of the individual loop. In this case, all the iterations of the original loop are independent of each other, and can be executed in any order, without changing the result. The loop may be safely executed using any parallel method, including vectorization. All the examples considered so far fall into this category.
  • When a variable is written in one iteration and read in a subsequent iteration, there is a “read-after-write” dependency, also known as a flow dependency, as in this example:

    A[0]=0; 
    for (j=1; j<MAX; j++)  A[j]=A[j-1]+1; 
              // this is equivalent to: 
       A[1]=A[0]+1;   
       A[2]=A[1]+1;   
       A[3]=A[2]+1; 
       A[4]=A[3]+1;

    So the value of j gets propagated to all A[j]. This cannot safely be vectorized: if the first two iterations are executed simultaneously by a SIMD instruction, the value of A[1] is used by the second iteration before it has been calculated by the first iteration.

  • When a variable is read in one iteration and written in a subsequent iteration, this is a write-after-read dependency, (sometimes also known as an anti-dependency), as in the following example:

    for (j=1; j<MAX; j++)  A[j-1]=A[j]+1; 
              // this is equivalent to: 
       A[0]=A[1]+1;
       A[1]=A[2]+1;
       A[2]=A[3]+1;
       A[3]=A[4]+1;

    This is not safe for general parallel execution, since the iteration with the write may execute before the iteration with the read. However, for vectorization, no iteration with a higher value of j can complete before an iteration with a lower value of j, and so vectorization is safe (i.e., gives the same result as non-vectorized code) in this case. The following example, however, may not be safe, since vectorization might cause some elements of A to be overwritten by the first SIMD instruction before being used for the second SIMD instruction.

    for (j=1; j<MAX; j++)  {
      A[j-1]=A[j]+1;
      B[j]=A[j]*2; 
    } 
    
              // this is equivalent to: 
       A[0]=A[1]+1;   
       A[1]=A[2]+1;   
       A[2]=A[3]+1;
       A[3]=A[4]+1;

  • Read-after-read situations aren’t really dependencies, and do not prevent vectorization or parallel execution. If a variable is not written, it does not matter how often it is read.
  • Write-after-write, or ‘output’, dependencies, where the same variable is written to in more than one iteration, are in general unsafe for parallel execution, including vectorization.
  • However, there is a very important exception, that apparently contains all of the above types of dependency:

    sum=0; 
    for (j=1; j<MAX; j++)  sum = sum + A[j]*B[j]

    Although sum is both read and written in every iteration, the compiler recognizes such reduction idioms, and is able to vectorize them safely. The loop in example 1 was another example of a reduction, with a loop-invariant array element in place of a scalar.

    These types of dependencies between loop iterations are sometimes known as loop-carried dependencies.

    The above examples are of proven dependencies. However, the compiler cannot safely vectorize a loop if there is even a potential dependency. Consider the following example:

    for (I = 0; I < size; I++) { c[i] = a[i] * b[i]; }

    In the above example, the compiler needs to determine whether, for some iteration I, c[i] might refer to the same memory location as a[i] or b[i] for a different iteration. (Such memory locations are sometimes said to be “aliased”). For example, if a[i] pointed to the same memory location as c[i-1], there would be a read-after-write dependency as in the earlier example. If the compiler cannot exclude this possibility, it will not vectorize the loop unless you provide the compiler with hints.