Optimizing compiler. Vectorization

The presentation can be downloaded here.

Different kinds of parallel:

An optimizing compiler is a tool which translates source code into an executable module and optimize source code for better performance. Parallelization is a transformation of the sequential program into multi-threaded or vectorized (or both) to utilize multiple execution units simultaneously without breaking the correctness of the program.

A typical vector instruction is an operation on two vectors in memory or in fixed length registers. These vectors can be loaded from memory by a single or multiple operations.

Vectorization is a compiler optimization that inserts vector instructions instead of scalar. This optimization "wraps" the data into vector; scalar operations are replaced by operations with these vectors (packets).

Such optimization can be also performed manually by developer.

A (1: n: k) - section of the array in Fortran is very convenient for vector register representation.

MMX, SSE vector instruction sets

MMX is a single instruction, multiple data (SIMD) instruction set designed by Intel, introduced in 1996 for P5-based Pentium line of microprocessors, known as "Pentium with MMX Technology".

MMX (Multimedia Extensions) is a set of instructions perform specific actions for streaming audio/video encoding and decoding.

MMX is:

MMX provides only integer operations. Simultaneous operations with floats and packed integers are not possible.

Streaming SIMD Extensions (SSE) is a SIMD instruction set extension of the x86 architecture, designed by Intel and introduced with Pentium III series processors in 1999. SIMD instructions can greatly increase the performance when exactly the same operations are performed on the multiple data objects. Typical applications are digital signal processing and computer graphics.

SSE is:

SSE2, SSE3, SSEE3, SSE4 are further extensions of SSE.

SSE2 has packed data type with double precision floating point.

Advanced Vector Extensions (AVX) is an extension of the x86 instruction set architecture for Intel and AMD microprocessors proposed by Intel in March 2008. Firstly supported by Intel Westmere processor in Q1 2011 and by AMD Bulldozer processor in Q3 2011.

AVX provides new features, new instructions and a new coding scheme.

The size of vector registers is increased from 128 to 256 bits (YMM0-YMM15).

The existing 128-bit instructions use the lower half of YMM registers.

Different data types can be packed in vector registers as follows

Selecting the appropriate data type for calculations can significantly affect application performance.

Optimization with Switches

Instruction groups

An aligned data movement instruction cannot be applied to the memory location which is not aligned by 16 (bytes).

Comparison instructions :

<cc> defines comparison operation.

lt – less, gt – greater, eq - equal

State management instructions

These instructions are commonly used by operating system.

Three Sets of Switches to Enable Processor-specific Extensions

Simple estimation of vectorization profitability

A typical vector instruction is an operation on two vectors in memory or in registers of fixed length. These vectors can be loaded from memory in a single operation or in part.

Description of the foundations of SSE technology can be found in CHAPTER 10 PROGRAMMING WITH STREAMING SIMD EXTENSIONS (SSE) of the document "Intel 64 and IA-32 Intel Architecture Software Developer's Manual" (Volume 1)

Microsoft Visual Studio supports a set of SSE intrinsics that allows you to use SSE instructions directly from C/C++ code. You need to include xmmintrin.h, which defines the vector type __m128 and vector operations.

For example, we need to vectorize manually the following loop:

for(i=0;i<N;i++)
C[i]=A[i]*B[i];

To do this:

#include <stdio.h>
#include <xmmintrin.h>
#define N 40
int main() {
float a[N][N][N],b[N][N][N],c[N][N][N];
int i,j,k,rep; __m128 *xa,*xb,*xc;
for(i=0;i< N;i++)
 for(j=0;j< N;j++)
  for(k=0;k< N;k++) {
    a[i][j][k]=1.0;   b[i][j][k]=2.0; }
for(rep=0;rep<10000;rep++) {
#ifdef PERF
for(i=0;i<N;i++)
  for(j=0;j<N;j++)
    for(k=0;k<N;k+=4) {
      xa=(__m128*)(a[i][j][k]);  xb=(__m128*)(b[i][j][k]); xc=(__m128*)(c[i][j][k]);
      *xc=_mm_mul_ps(*xa,*xb);     }
#else
for(i=0;i< N;i++)
 for(j=0;j< N;j++)
  for(k=0;k<N;k++)
    c[i][j][k]=a[i][j][k]*b[i][j][k];
#endif
}
printf("%f\n",c[21][11][18])
}

An example illustrating the vectorization with SSE intrinsics

icl -Od test.c -Fetest1.exe
icl -Od test.c -DPERF -Fetest_opt.exe
time test1.exe
2.000000

CPU time for command: 'test1.exe'

real    3.406 sec
user    3.391 sec
system  0.000 sec
time test_opt.exe
2.000000

CPU time for command: 'test_opt.exe'

real    1.281 sec
user    1.250 sec
system  0.000 sec

Intel compiler 12.0 was used for this experiment

The resulting speedup is 2.7x.

We used aligned by 16 memory access instructions in this example. Alignment was matched accidently, in the real case, you need to worry about it.

Test-optimized compiler shows the following result:

icl test.c-Qvec_report3-Fetest_intel_opt.exe
 time test_intel_opt.exe
 2.000000

CPU time for command: 'test_intel_opt.exe'

real 0.328 sec
user 0.313 sec
system 0.000 sec

Admissibility of vectorization

Vectorization is a permutation optimization. Initial execution order is changed during vectorization.

Permutation optimization is acceptable, if it preserves the order of dependencies. Thus we have a criterion for the admissibility of vectorization in terms of dependencies.

The simplest case when there are no dependencies inside the processed loop.

In more complicated case there are dependences inside the vectorized loop but its order is the same as inside the initial scalar loop.

Let’s recall the description of the dependency in a loop:

There is a loop dependency between the statements S1 and S2 in the set of nested loops, if and only if

Option for vectorization control

/Qvec-report[n]

control amount of vectorizer diagnostic information

Usage: icl -c -Qvec_report3 loop.c

Diagnostic examples:

Simple criteria of vectorization admissibility

Let’s write vectorization of loop with usage of fortran array sections.

A good criterion for vectorization is the fact that the introduction section of the array does not create dependency.

There is dependency because A(I+1:I+1+VL) on iteration I and A(I+VL:I+2*VL) for I+1 are intersected.

There is no dependency because A(I-1:I-1+VL) on iteration I and A(I+VL:I+2*VL) for I+1 aren’t intersected.

PROGRAM TEST_VEC
INTEGER,PARAMETER :: N=1000
#ifdef PERF
INTEGER,PARAMETER :: P=4
#else
INTEGER,PARAMETER :: P=3
#endif
INTEGER A(N)
DO I=1,N-P
 A(I+P)=A(I)
END DO
PRINT *,A(50)
END

Let’s check an assumption:

Loop can be vectorized, if the dependence distance greater or equal to number of array elements within the vector register.

Check this with compiler:

ifort test.F90 -o a.out –vec_report3
echo -------------------------------------
ifort test.F90 -DPERF -o b.out –vec_report3
./build.sh
test.F90(11): (col. 1) remark: loop was not vectorized: existence of vector dependence.
-------------------------------------
test.F90(11): (col. 1) remark: LOOP WAS VECTORIZED.

Dependency analysis and directives

There are two tasks which compiler should perform for dependency evaluation:

Compiler should prove that there are not aliased objects and precisely calculate the dependencies. It is hard task and sometimes compiler isn’t able to solve it.

There are methods of providing additional information to the compiler:

Some performance issues for the vectorized code

INTEGER :: A(1000),B(1000)
INTEGER I,K
INTEGER, PARAMETER :: REP = 500000
A = 2
DO K=1,REP
  CALL ADD(A,B)
END DO
PRINT *,SHIFT,B(101)
CONTAINS
  SUBROUTINE ADD(A,B)
  INTEGER A(1000),B(1000)
  INTEGER I
!DEC$ UNROLL(0)
  DO I=1,1000-SHIFT
   B(I) = A(I+SHIFT)+1
  END DO
  END SUBROUTINE
END

Let’s consider some simple test with a assignment which is appropriate for vectorization. Let us obtain vectorized code with usage of Intel Fortran compiler for different values of SHIFT macro.

/fpp – option for preprocessor Intel compiler makes vectorization if level of optimization is 2 or 3. (-O2 or -O3)

Option –Ob0 is used to forbid inlining.

Experiment results

ifort test1.F90 -O2  -Ob0 /fpp /DSHIFT=0 -Fea.exe -Qvec_report >a.out 2>1
ifort test1.F90 -O2  -Ob0 /fpp /DSHIFT=1 -Feb.exe -Qvec_report >b.out 2>1

time.exe a.exe
 0           3
 CPU time for command: 'a.exe'
 real    0.125 sec
 user    0.094 sec
 system  0.000 sec
 time.exe  b.exe
 1           3
 CPU time for command: 'b.exe'
 real    0.297 sec
 user    0.281 sec
 system  0.000 sec

ifort test1.F90 -O2  -Ob0 /fpp /DSHIFT=0 /Fas -Ob0 -S –Fafast.s
fast.s
.B2.5:                          ; Preds .B2.5 .B2.4
$LN83:
;;;    B(I) = A(I+SHIFT)+1
        movdqa    xmm1, XMMWORD PTR [eax+ecx*4]                 ;17.11
$LN84:
        paddd     xmm1, xmm0                                    ;17.4
$LN85:
        movdqa    XMMWORD PTR [edx+ecx*4], xmm1                 ;17.4
$LN86:
        add       ecx, 4                                        ;16.3
$LN87:
        cmp       ecx, 1000                                     ;16.3
$LN88:
        jb        .B2.5         ; Prob 99%                      ;16.3

ifort test1.F90 -O2  -Ob0 /fpp /DSHIFT=1  /Fas -Ob0  -S  –Faslow.s

slow.s

.B2.5:                          ; Preds .B2.5 .B2.4
$LN81:
;;;    B(I) = A(I+SHIFT)+1
        movdqu    xmm1, XMMWORD PTR [4+eax+ecx*4]               ;17.11
$LN82:
        paddd     xmm1, xmm0                                    ;17.4
$LN83:
        movdqa    XMMWORD PTR [edx+ecx*4], xmm1                 ;17.4
$LN84:
        add       ecx, 4                                        ;16.3
$LN85:
        cmp       ecx, 996                                      ;16.3
$LN86:
        jb        .B2.5         ; Prob 99%                      ;16.3

CONCLUSION:

MOVDQA—Move Aligned Double Quadword

MOVDQU—Move Unaligned Double Quadword

In fast version aligned instructions are used and vector registers are filled faster.

Unaligned instructions are slower. For latest architectures they shows the same performance as aligned instructions if applied to the aligned data.

Performance of vectorized loop depends on the memory location of the objects used. The important aspect of program performance is the memory alignment of the data

Data Structure Alignment is computer memory data placement. This concept includes two distinct but related issues: alignment of the data (Data alignment) and data structure filling (Data structure padding).

Data alignment specifies how certain data is located relative to the boundaries of memory. This property is usually associated with a data type.

Filling data structures involves insertion of unnamed fields into the data structure in order to preserve the relative alignment of structure fields.

Data alignment

Information about the alignment can be obtained with intrinsic __alignof__. The size and the default alignment of the variable of a type may depend on the compiler. (ia32 or intel64)

 printf("int:  sizeof=%d align=%d\n",sizeof(a),__alignof__(a));

Alignment for ia32 Intel C++ compiler:

bool           sizeof = 1 alignof = 1
wchar_t        sizeof = 2 alignof = 2
short int      sizeof = 2 alignof = 2
int            sizeof = 4 alignof = 4
long int       sizeof = 4 alignof = 4
long long int  sizeof = 8 alignof = 8
float          sizeof = 4 alignof = 4
double         sizeof = 8 alignof = 8
long double    sizeof = 8 alignof = 8
void*          sizeof = 4 alignof = 4

The same rules are used for array alignment.

There is the possibility to force the compiler to align object in a certain way:

__declspec(align(16)) float x[N];

The order of fields in the structure affects the size of the object of a derived type. To reduce the size of the object structure fields should be sorted by descending of its size. You can use __declspec to align structure fields.

typedef struct aStuct{
 __declspec(align(16)) float x[N];
 __declspec(align(16)) float y[N];
 __declspec(align(16)) float z[N];
};

Loop vectorization usually produces three loops: loop for non-aligned staring elements, vectorized loop and tail. Vectorization of loop with small number of iterations can be unprofitable.

Additional vectorization example

Vector.c

void Calculate(float * a,float * b,
                           float * c , int n) {
int i;
  for(i=0;i<n;i++) {
    a[i] = a[i]+b[i]+c[i];
  }
  return;
}

First argument alignment differs

Main.c

#include <stdio.h>
#define N 1000
extern void Calculate(float *,float *, float *,int);
int main() {
float x[N],y[N],z[N];
int i,rep;
for(i=0;i<N;i++) {
  x[i] = 1;y[i] = 0; z[i] = 1;
}
for(rep=0;rep<10000000;rep++) {
 Calculate(x[1],y[0],z[0],N-1);
}
printf("x[1]=%f\n",x[1]);
}

icl  main.c vec.c -O1 –FeA
time a.exe 12.6 s.     

Option -Qvec_report informs about vectorized loops.  
icl  main.c vec.c –O2 –Qvec_report –Feb
vec.c(3): (col. 3) remark: LOOP WAS VECTORIZED.
time b.exe         3.67 s.

void Calculate(float * resrtict a,float * restrict b, float * restrict c , int n) {

icl  main.c vec.c –Qstd=c99 –O2 –Qvec_report –Fec
vec.c(3): (col. 3) remark: LOOP WAS VECTORIZED.
time c.exe         3.55 s.

int main() {
 __declspec(align(16)) float x[N];
 __declspec(align(16)) float y[N];
 __declspec(align(16)) float z[N];

Calculate(x[0],y[0],z[0],N-1);

void Calculate (float * resrtict a,float * restrict b, float * restrict c , int n) {
Int n;
__assume_aligned(a,16);
__assume_aligned(b,16);
__assume_aligned(c,16);

icl  main.c vec.c –Qstd=c99 –O2 –Qvec_report –Fed
vec.c(3): (col. 3) remark: LOOP WAS VECTORIZED.
time d.exe         3.20 s.

Data alignment

Good array data alignment for SSE: 16B for AVX: 32B

Non-unit stride and unit stride access

Well aligned data is better for vectorization because in this case vector register is filled by the single operation. In case with non-unit stride access to array, register filling is more complicated task and vectorization is less profitable.

Auto vectorizer cooperates with loop optimizations for improving access to objects.

There are compiler directives which recommend to make vectorization in case when compiler doesn’t make it because it looks unprofitable.

C/C++

#pragma vector{aligned|unaligned|always} 
#pragma novector

Fortran

!DEC$ VECTOR ALWAYS
!DEC$ NOVECTOR

Vectorization of outer loop

Usually auto vectorizer processes the nested loop. Vectorization of the outer loop can be done using "simd" directive.

#define  N 200
#include<stdio.h>

int main() {
int A[N][N],B[N][N],C[N][N];
int i,j,rep;

for(i=0;i<N;i++)
  for(j=0;j<N;j++) {
     A[i][j]=i+j;
     B[i][j]=2*j-i;
     C[i][j]=0;
  }

for(rep=0;rep<10000000;rep++) {
#pragma simd 
  for(i=0;i<N;i++) {
    j=0;
    while(A[i][j]<=B[i][j]  j<N) {
      C[i][j]=C[i][j]+B[j][i]-A[j][i];     
      j++;
    }
  }
}
printf("%d\n"C[0][2]);
}

icl   vec.c -O3 -Qvec- -Fea    (Qvec- disable vectorization)    20.7 s
icl   vec.c -O3 -Qvec_report -Feb                                 17.s
vec.c(17): (col. 3) remark: SIMD LOOP WAS VECTORIZED.