Optimizing compiler. Auto parallelization

Multicore and multiprocessor is de facto standard

The presentation can be downloaded here.

Intel® Pentium® Processor Extreme Edition (2005-2007)

Dual core introduced

Intel® Xeon® Processor 5100, 5300 Series

Intel® Core™2 Processor Family (2006-)

Dual-processor and quad-core

Intel® Xeon® Processor 5200, 5400, 7400 Series

Intel® Core™2 Processor Family (2007-)

2-4 processors, up to 6 cores

Intel® Atom™ Processor Family (2008-)

Energy Efficiency has high priority

Intel® Core™i7 Processor Family (2008-)

Hyperthreading technology. System with non-uniform memory access.

CPU core is a complete computer system that shares some of the processing resources with other cores

Multiprocessor systems are

Instability of the application performance on multiprocessor machines with non-uniform memory access.

OS periodically moves application from one core to another with different access speed to the memory used.

Pros and cons of the multi-threaded applications

Auto parallelization is a compiler optimization which automatically converts sequential code into multi-threaded in order to utilize multiple cores simultaneously. The purpose of the automatic parallelization is to free programmer from the difficult and tedious manual parallelization.

/Qparallel

enable the auto-parallelization to generate multi-threaded code for loops that can be safely executed in parallel

Profitability of auto parallelization

Let’s consider simple fortran test:

REAL :: a(1000,1000),b(1000,1000),
        c(1000,1000)
integer   i,j,rep_factor 
DO I=1,1000
  DO J=1,1000
    A(J,I) = I
    B(J,I) = I+J
    C(J,I) = 0
  END DO
END DO
DO rep_factor=1,1000
  C=B/A+rep_factor 
END DO
END 

This slide demonstrates auto parallelization speedup. We have improvement on real time from 2.29 s. to 1.67 s. User time has been changed from 2.23 s. to 6.02 s. It means that amount of work was increased.

void matrix_mul_matrix(int n, 
float C[n][n], float A[n][n], 
float B[n][n]) {
 int i,j,k;
 for (i=0; i<n; i++) 
  for (j=0; j<n; j++) {
   C[i][j]=0;
       for(k=0;k<n;k++)
         C[i][j]+=A[i][k]*B[k][j];
    }
}

CPU cores may compete for some processor resources, for example for cash subsystem and for system bus. Bus bandwidth can be bottleneck for some algorithms. The right picture demonstrates the relation between time and number of threads for matrix multiplication loop. It is an example of highly scalable algorithm.

void matrix_add(int n, float Res[n][n],float A1[n][n], float A2[n][n],
float A3[n][n],float A4[n][n], float A5[n][n], float A6[n][n],
float A7[n][n], float A8[n][n]) {
  int i,j;
  for (i=0; i<n; i++) 
    for (j=1; j<n-1; j++) 
    Res[i][j]=A1[i][j]+A2[i][j]+A3[i][j]+A4[i][j]+
      A5[i][j]+A6[i][j]+A7[i][j]+A8[i][j]+
      A1[i][j+1]+A2[i][j+1]+A3[i][j+1]+A4[i][j+1]+
      A5[i][j+1]+A6[i][j+1]+A7[i][j+1]+A8[i][j+1];

Admissibility of auto parallelization

Auto parallelization is a loop permutation optimization.

Initial order of instruction execution becomes unspecified.

A necessary conditions for its applicability are:

/Qpar-report{0|1|2|3} control the auto-parallelizer diagnostic level

/Qpar-report3 option informs if the compiler parallelizes or doesn’t parallelize a loop, including reports which problem prevents auto parallelization. For example:

   int sub (int *a, float *b, int n) =>
   int sub (int *restrict a, float *restrict b, int n)

# pragma parallel, # pragma parallel always, # pragma noparallel

Automatic parallelization is done using the OpenMP interface. OpenMP (Open Multi-Processing) is a software interface that supports multi-platform programming for multiprocessor computation systems with shared memory on C/C++ and Fortran.

The number of used threads is defined by the environment variable OMP_NUM_THREADS and can be modified before application launch (by default application will use all available cores)

Loop parallelization looks like creating a function taking all used objects and loop iteration space part as arguments.

The multiple instances of loop thread function are executed in different streams with different values of the boundaries. Iterative loop space is divided into several parts and each is given to the separate thread.

Optimizing compiler is able to create several versions of code by adding some run-time checks to resolve dependences issues, to make estimation of loop iterations, etc.

/Qpar-runtime-control[n]

Control parallelizer to generate runtime check code for effective automatic parallelization.

Interaction with other loop optimizations

An optimizing compiler makes loop parallelization together with other optimizations. Because thread creation has its price it is more profitable to has large loops for processing. So order of optimizations canbe:

These considerations can be used during creating a program design to simplify following threadization with usage of compiler autoparallelization or OPENMP directives.

Software prefetching

Prefetching is loading data from relatively slow memory into the cache before the memory is required by processor. Software prefetching is insertion of the special prefetch instructions to the code.

There are several methods of prefetch usage:

Prefetch intrinsic functions are defined in xmmintrin.h and has the form

# include <xmmintrin.h>
enum _mm_hint {_MM_HINT_T0 = 3, (L1)
   _MM_HINT_T1 = 2, (L2)
   _MM_HINT_T2 = 1, (L3)
   _MM_HINT_NTA = 0};
void _mm_prefetch (void * p, enum _mm_hint h);

It loads a cache line from the address specified (size of the cache line is 64 bytes)

Use CALL mm_prefetch (P, HINT) inside the fortran programs

Why software prefetching can be useful

There is hardware prefetch mechanism which tries to identify the memory access pattern to choose the appropriate preloading scheme. It works fine when the memory is accessed with constant stride and this stride is relatively small.

Software prefetch instructions have its price. Computing system can ignore software prefetching instructions when the system bus is busy.

Don’t use software prefetching instructions

There are many cases when programmer could help to preload the memory required:

The VTUNE usage can help to identify slowdowns, caused by the inefficient memory access.

SUBROUTINE CALC(A,B,C,N,K,SEC)
INTEGER N,K,SEC,I,J
REAL A(K,N),B(K,N),C(K,N)
DO I=1,K
  DO J=1,N
    A(I,J)=A(I,J)/(A(I,J)+ B(I,J)*C(I,J))
#ifdef PERF
      CALL mm_prefetch(A(I,J+SEC),3)
      CALL mm_prefetch(B(I,J+SEC),3)
      CALL mm_prefetch(C(I,J+SEC),3)
#endif
  END DO
END DO
END SUBROUTINE CALC

Idea of this example:

Memory is accessed with large constant stride.

Can we obtain performance gain?

Would it be different for different SEC values?

INTEGER N,K
REAL, ALLOCATABLE :: A(:,:),B(:,:),C(:,:),D(:,:)
REAL T1,T2
INTEGER REP,SEC
READ *,N,SEC
READ *,K
ALLOCATE(A(K,N),B(K,N),C(K,N))
ALLOCATE(D(10000,10000))
A=1
B=1
C=1
D=0
CALL CPU_TIME(T1)
CALL CALC(A,B,C,N,K,SEC)
CALL CPU_TIME(T2)
PRINT *,T2-T1 
END

Execution results

 ifort /fpp  -DPERF -Od pref.f90 -Feperf_pref.exe 
 ifort /fpp         -Od pref.f90 -Feperf.exe  

Data for input:

 4000 SEC
 4000

without SP: 0.48s.

  SEC == 1 with SP:   0.56s.
  SEC == 4 with SP:   0.48s    

?? Price of prefetch instructions exceed gain from prefetch.

Let’s enlarge calculations inside loop

A(I,J)=A(I,J)/(A(I,J)+ B(I,J)*C(I,J)) => 
A(I,J) = (EXPONENT(A(I,J))+EXPONENT(B(I,J))+EXPONENT(C(I,J)))/(A(I,J)*B(I,J)*C(I,J))

without SP: 1.45s.

  SEC == 1 with SP:   1.07s.
  SEC == 4 with SP:   0.98s 

Conclusion

It is hard to determine if the prefetch instruction can be helpful for all computing systems. The performance of the memory subsystems depend on many different factors such as, amount of cash memory, memory latency, bandwidth, etc. Prefetch instruction call has its price and increases amount of data which should be passed through the system bus. Therefore result of software prefetch can be different for the different computing systems.

Auto software prefetching options

/Qopt-prefetch[:n]

C/C++ extended array notation

C/C++ language extension for array notations is an Intel-specific language extension that is a part of Intel® Cilk™ Plus feature supported by the Intel® compiler.

The C/C++ extension provides data parallel array notations with the following major benefits:

When you use the array notations, the Intel® compiler implements them using vector code.

Usage Recommendations

Use the array notations when your algorithm requires operations on arrays and where it does not require a specific order of operations among the elements of the array(s).

To use the array notations in your application, keep the following sequence of steps in mind:

Insert the array notations language extensions into your application source code.

Compile the application at optimization level –O1 and above to enable vectorization. By default, the compiler generates SIMD vector instructions in the SSE2 instruction set. To generate SIMD vector instructions beyond SSE2, you can add target/architecture-specific compiler options to the compile command.

By default, the Intel® compiler accepts the array notations language extensions to generate vector and multi-threaded code based on the data parallel constructs in the program.

CEAN (C/C++ Extensions for Array Notations Programming Model)

Declaration of the array sections

  section_operator :: = [<lower bound>:<length>:<stride>]
  a[0:3][0:4]
  b[0:2:3]

You must use –std=c99 (Linux и MAC OS) or /Qstd=c99 compiler options

Example:

typedef int (*p2d)[128];
  p2d p = (p2d) malloc (sizeof(int)*rows*128);
  p[0:rows][:]

Most of C/C++ operators are available for array sections.

a[:]*b[:]                  // element-wise multiplication
a[3:2][2:2] + b[5:2][5:2]  // matrix addition
a[0:4]+c                   // adds scalar to an array section
a[:][:] = b[:][1][:] + c   // array assignment

#include <stdio.h>
#include <stdlib.h>
#define N 2000
typedef double (*p2d)[];
void matrix_mul(int n, double a[n][n], 
        double b[n][n],double c[n][n]) {
 int i,j;
 a[:][:] =1;
 b[:][:] =-1;
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
      c[i][j]=c[i][j]+ 
__sec_reduce_add(a[i][:]*b[:][j]);
 return;
}

int main() {
 p2d a= (p2d)malloc(N*N*sizeof(double)) ;
 p2d b= (p2d)malloc(N*N*sizeof(double)) ;
 p2d c= (p2d)malloc(N*N*sizeof(double));
 matrix_mul(N,a,a,a);
 matrix_mul(N,a,b,c);
 free(a);
 free(b);
 free(c);
}