Vectorization

Vectorization, in computer science, is the process of converting a computer program from a scalar implementation, which does an operation on a pair of operands at a time, to a vectorized program where a single instruction can perform multiple operations on a pair of vector (series of adjacent values) operands. Vector processing is a major feature of both conventional and modern supercomputers.

One major research topic in computer science is the search for methods of automatic vectorization; seeking methods that would allow a compiler to convert scalar programs into vectorized programs without human assistance.

Background

In the beginning, computers generally had one logic unit executing one instruction at a time. Therefore, programs were designed to execute sequentially and so most programming languages do until today. However, since the first computers were created in the 60's, much effort was spend towards executing more than one instruction at the same time. But because programming languages still retained the procedural execution mode, a still greater effort was done, and still is being done, to transform sequential programs into parallel ones without changing the meaning and order of them.

A good part of parallelization on procedural languages is done via loop vectorization. Because most programs spend most of their execution times within loops and because the syntax of a loop body is generally simplified (because of its impact in runtime, programmers tend to minimize as much as possible), vectorizing loops can sometimes cause performance gains of orders of magnitude without a single effort from the programmer.

In the past decades, chip manufacturers created specialized processing units and registers to enable the same operations to run on a block of data rather than a single word. Intel's MMX and SSE and ARM's NEON instruction sets can run the same instruction on several bytes at the same time, reducing the number of iterations of the loop.

Of course, there are lots of conditions that hinders such vectorizations. Loop dependence analysis must define what can and what cannot be vectorized, relying on the data dependence of the instructions inside loops with others and themselves (in the next iterations). Some times, the execution time can actually be slower than plain loops because of pipeline synchronization, data movement timing and other issues.

Guarantees

Automatic vectorization must be done in a way to keep the program identical to what it was, but using vector instructions to speed up repetitive instructions. After the data dependence analysis, the compiler can infer if a specific statement can be vectorized or not, but it also must account for the changes in syntax (and semantics) of the change made.

Data Dependences

All dependences must be kept in order to assure the data will not be corrupted during the execution of the vectorized code, that would not happen on the sequential code. If that premise is not kept, both versions will yield different results, depending on the order of the inputs.

In general, loop invariant and lexically forward dependences can be easily vectorized, and lexically backward dependence can be transformed into lexically forward. But these transformations must be done safely, in order to assure the dependence between all statements remain true to the original.

Cyclic dependences cannot be vectorized and must be taken out of the vectorized loop, so even those dependences (after extraction) must be taken into account.

Data Precision

Integer precision (bit-size) must be kept during vector instruction execution. Especial care must be taken with sign extension (as multiple integers are packed inside the same register) and during shift operations, or operations with carry bits that would otherwise be taken into account.

The correct vector instruction must be chosen based on the size and behaviour of the internal integers. Also, with mixed integer types, extra care must be taken to promote/demote them correctly without loosing precision.

Floating-point precision must be kept as well, unless the IEEE-754 compliance is turned off, in which case the operations will be faster but the results may vary slightly. Big variations, even with the IEEE-754 turned off, usually means programmer error. The programmer can also force constants and loop variables to single precision (default is normally double) to execute twice as much operations per instruction.

Theory

To vectorize a program, the optimizer must first understand the dependences between each statement and re-align them, if necessary. Once the dependences are mapped, the optimizer must re-arrange the statements and change them to vectorial instructions.

Building the dependency graph

The first step is to build the dependency graph. For that, one needs to walk down the statements of a sequential program and identify every data access, mapping array access modifiers to functions and checking every access' dependency to all others in all statements. Alias analysis can be used to certify that the different variables access (or intersects) the same region in memory.

The dependency graph contains all local dependences with distance not greater than the vector size. So, if the vector register is 128 bits, and the array type is 32 bits, the vector size is 128/32 = 4. All other non-cyclic dependencies should not invalidate vectorization, since there won't be any concurrent access in the same vector instruction.

Suppose the vector size is the same as 4 ints:

for (i = 0; i < 128; i)) {
  a[i] = a[i+16]; // 16 > 4, safe to ignore
  a[i] = a[i+1]; // 1 < 4, stay on dep. graph
}

Clustering

After the graph is built, the optimizer can then cluster the strongly connected components (SCC) and separate what can be optimized and what has to be left alone.

For example, suppose a program fragment containing three groups inside a loop: (SSC1+SSC2), SSC3 and SSC4. Now, imagine that only the second group (SCC3) can be vectorized. The final program will then contain three loops, one for which group, where only the middle one is vectorized. The optimizer cannot join the first with the last, or it'd change the order in which the statements are executed, thus breaking the necessary guarantees.

Detecting idioms

Some non-obvious dependences can be further optimized based on specific idioms.

For instance, the following self-data-dependences can be vectorized because the value of the right-hand values (RHS) are fetched and then stored on the left-hand value, so there is no way the data will change within the assignment.

a[i] = a[i] + a[i+1];

Self-dependence by scalars can be vectorized by variable elimination.

General Framework

The general framework for loop vectorization is split into four stages:

• Prelude: Where the loop-independent variables are prepared to be used inside the loop. This normally involves moving them to vector registers with specific patterns that will be used in vector instructions. For run-time dependence check, this is also the place to do it. If the check thinks it's impossible to vectorize it branches directly to the Cleanup stage.
• Loop(s): All vectorizes (or not) loops, separated by SSCs clusters in order of appearance in the original code.
• Postlude: Move back all loop-independent variables, inductions and reductions.
• Cleanup: Non-vectorize plain loop, for the remaining iterations (if the number of iterations is not a multiple of the vector size) or for when run-time checks detect impossibility of vectorization.

Run-time vs. Compile-time vectorization

Some vectorizations cannot be checked during compile time. Either because there is no explicit array indexes or because there is no way to know who could call the function (libraries). On those cases, a run-time check can still vectorize loops on-the-fly.

This check is made on the prelude stage and redirects the flow to the vectorized or not, depending on the variables that are being passed on the registers or scalar variables.

The following code can easily be vectorized on compile time, as it doesn't have any dependence on external parameters. Also, the language guarantees that neither will occupy the same region in memory as any other variable, as they are local variable and live in the stack.

int a[128];
int b[128];
// initialize b
 
for (i = 0; i<128; i++)
  a[i] = b[i] + 5;

On the other hand, the code below has no information on the positions in memory, as they are pointers and the memory they point to lives in the heap.

int *a = (int*) malloc(128*sizeof(int));
int *b = (int*) malloc(128*sizeof(int));
// initialize b
 
for (i = 0; i<128; i++, a++, b++)
  *a = *b + 5;

A quick run-time check on the address of both a and b, plus the loop iteration space (128) is enough to tell if the arrays overlap or not, thus knowing the dependence between them.

Techniques

Automatic vectorization, in the context of a computer program, refers to the automatic transformation of a series of operations performed sequentially, one operation at a time, to operations performed in parallel, several at once, in a manner suitable for processing by a vector processor.

An example would be a program to multiply two vectors of numeric data. A scalar approach would be something like:

 for (i = 0; i < 1024; i++)
 {
    C[i] = A[i]*B[i];
 }

This could be transformed to vectorized code something like:

 for (i = 0; i < 1024; i+=4)
 {
    C[i:i+3] = A[i:i+3]*B[i:i+3];
 }

Here, C[i:i+3] represents the four array elements from C[i] to C[i+3] and we assume that the vector processor can perform four operations for a single vector instruction. Since four operations are performed for an execution time roughly similar to time taken for one scalar instruction, the vector code can run up to four times faster than the original code.

There are two distinct compiler approaches: one based on the conventional vectorization technique and the other based on loop unrolling.

Loop-level automatic vectorization

This technique, used for conventional vector machines, tries to find and exploit SIMD parallelism from the loop level. It consists of two major steps as follows.

1. Find an innermost loop that can be vectorized
2. Transform the loop and generate vector codes

In the first step, the vectorizing compiler looks for obstacles that can prevent vectorization. A major obstacle for vectorization is true data dependency shorter than the vector length. Other obstacles include function calls and short iteration counts.

Once the loop is determined to be vectorizable, the loop is stripmined by the vector length and each scalar instructions within the loop body are replaced with the corresponding vector instructions. Below, the component transformations for this step are shown using the above example.

• After stripmining

 for (i = 0; i < 1024; i+=4)
 {
   for (ii = 0; ii < 4; ii++)
   {
      C[i+ii] = A[i+ii]*B[i+ii];
   }
 }

• After loop distribution using temporary arrays

 for (i = 0; i < 1024; i+=4)
 {
   for (ii = 0; ii < 4; ii++) tA[ii] = A[i+ii];
   for (ii = 0; ii < 4; ii++) tB[ii] = B[i+ii];
   for (ii = 0; ii < 4; ii++) tC[ii] = tA[ii]*tB[ii];
   for (ii = 0; ii < 4; ii++) C[i+ii] = tC[ii];
 }

• After replacing with vector codes

 for (i = 0; i < 1024; i+=4)
 {
   vA = vec_ld( &A[i] );
   vB = vec_ld( &B[i] );
   vC = vec_mul( vA, vB );
   vec_st( vC, &C[i] );
 }

Basic block level automatic vectorization

This relatively new technique specifically targets modern SIMD architectures with short vector lengths. Although loops can be unrolled to increase the amount of SIMD parallelism in basic blocks, this technique targets to exploit SIMD parallelism within basic blocks rather than from loops. Because of this, SIMD codes can be generated from basic blocks outside loop nests. The two major steps are as follows.

1. The innermost loop is unrolled by a factor of the vector length to form a large loop body.
2. Isomorphic scalar instructions (that perform the same operation) are packed into a vector instruction if dependencies do not prevent doing so.

To show step-by-step transformations for this approach, the same example is used again.

• After loop unrolling (by the vector length, assumed to be 4 in this case)

 for (i = 0; i < 1024; i+=4)
 {
    sA0 = ld( &A[i+0] );
    sB0 = ld( &B[i+0] );
    sC0 = sA0 * sB0;
    st( sC0, &C[i+0] );
          ...
    sA3 = ld( &A[i+3] );
    sB3 = ld( &B[i+3] );
    sC3 = sA3 * sB3;
    st( sC3, &C[i+3] );
 }

• After packing

 for (i = 0; i < 1024; i+=4)
 {
    (sA0,sA1,sA2,sA3) = ld( &A[i+0:i+3] );
    (sB0,sB1,sB2,sB3) = ld( &B[i+0:i+3] );
    (sC0,sC1,sC2,sC3) = (sA0,sA1,sA2,sA3) * (sB0,sB1,sB2,sB3);
    st( (sC0,sC1,sC2,sC3), &C[i+0:i+3] );
 }

• After code generation

 for (i = 0; i < 1024; i+=4)
 {
   vA = vec_ld( &A[i] );
   vB = vec_ld( &B[i] );
   vC = vec_mul( vA, vB );
   vec_st( vC, &C[i] );
 }

Here, sA1, sB1, ... represent scalar variables and vA, vB, and vC represent vector variables.

Most automatically vectorizing commercial compilers use the conventional loop-level approach except the IBM XL Compiler that uses both.

Vectorization in the presence of control flow

When there are if-statements in the loopbody, the instructions in all control paths have to be executed to merge the multiple values of a variable. One general approach is to go through a sequence of code transformations: predication → vectorization(using one of the above methods) → remove vector predicates → remove scalar predicates. If the following code is used as an example to show these transformations;

 for (i = 0; i < 1024; i++)
 {
    if (A[i] > 0)
      C[i] = B[i];
    else
      D[i] = D[i-1];
 }

• After predication

 for (i = 0; i < 1024; i++)
 {
    P = A[i] > 0;
    NP = !P;
    C[i] = B[i];     (P)
    D[i] = D[i-1];   (NP)
 }

where (P) denotes a predicate guarding the statement.

• After vectorization

 for (i = 0; i < 1024; i+=4)
 {
    vP  = A[i:i+3] > (0,0,0,0);
    vNP = vec_not(vP);
    C[i:i+3] = B[i:i+3];     (vP)
    (NP1,NP2,NP3,NP4) = vNP;
    D[i]   = D[i-1];         (NP1)
    D[i+1] = D[i];           (NP2)
    D[i+2] = D[i+1];         (NP3)
    D[i+3] = D[i+2];         (NP4)
 }

• After removing vector predicates

 for (i = 0; i < 1024; i+=4)
 {
    vP  = A[i:i+3] > (0,0,0,0);
    vNP = vec_not(vP);
    C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vP);
    (NP1,NP2,NP3,NP4) = vNP;
    D[i]   = D[i-1];         (NP1)
    D[i+1] = D[i];           (NP2)
    D[i+2] = D[i+1];         (NP3)
    D[i+3] = D[i+2];         (NP4)
 }

• After removing scalar predicates

 for (i = 0; i < 1024; i+=4)
 {
    vP  = A[i:i+3] > (0,0,0,0);
    vNP = vec_not(vP);
    C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vP);
    (NP1,NP2,NP3,NP4) = vNP;
    if (NP1) D[i]   = D[i-1];
    if (NP2) D[i+1] = D[i];
    if (NP3) D[i+2] = D[i+1];
    if (NP4) D[i+3] = D[i+2];
 }

Reducing vectorization overhead in the presence of control flow

Having to execute the instructions in all control paths in vector code has been one of the major factors that slow down the vector code with respect to the scalar baseline. The more complex the control flow becomes and the more instructions are bypassed in the scalar code the larger the vectorization overhead grows. To reduce this vectorization overhead, vector branches can be inserted to bypass vector instructions similar to the way scalar branches bypass scalar instructions. Below, AltiVec predicates are used to show how this can be achieved.

• Scalar baseline (original code)

 for (i = 0; i < 1024; i++)
 {
    if (A[i] > 0)
    {
      C[i] = B[i];
      if (B[i] < 0)
        D[i] = E[i];
    }
 }

• After vectorization in the presence of control flow

 for (i = 0; i < 1024; i+=4)
 {
    vPA = A[i:i+3] > (0,0,0,0);
    C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vPA);
    vT = B[i:i+3] < (0,0,0,0);
    vPB = vec_sel((0,0,0,0), vT, vPA);
    D[i:i+3] = vec_sel(D[i:i+3],E[i:i+3],vPB);
 }

• After inserting vector branches

 for (i = 0; i < 1024; i+=4)
 {
    if (vec_any_gt(A[i:i+3],(0,0,0,0)))
    {
       vPA = A[i:i+3] > (0,0,0,0);
       C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vPA);
       vT = B[i:i+3] < (0,0,0,0);
       vPB = vec_sel((0,0,0,0), vT, vPA);
       if (vec_any_ne(vPB,(0,0,0,0)))
       {
          D[i:i+3] = vec_sel(D[i:i+3],E[i:i+3],vPB);
       }
    }
 }

There are two things to note in the final code with vector branches; First, the predicate defining instruction for vPA is also included within the body of the outer vector branch by using vec_any_gt. Second, the profitability of the inner vector branch for vPB depends on the conditional probability of vPB having false values in all fields given vPA has false values in all fields.

Let's think about an example where the outer branch in the scalar baseline is always taken bypassing most instructions in the loopbody. Without vector branches, the vector code, shown in the second loop above, should execute all vector instructions. When vector branches are used as in the final code, both the comparison and the branch are performed in vector mode potentially gaining performance over the scalar baseline.