Optimización CPU

Presenter Notes

Resumen:

  • Tour por un compilador optimizante.
  • Que cosas no vale la pena hacer.
  • Que cosas SI vale la pena hacer.

Nicolás Wolovick 20160329

Presenter Notes

Proebsting’s Law

Compiler technology doubles CPU power every 18 years

This means that while hardware computing horsepower increases at roughly 60%/year, compiler optimizations contribute only 4%. Basically, compiler optimization work makes only marginal contributions.

Perhaps this means Programming Language Research should be concentrating on something other than optimizations. Perhaps programmer productivity is a more fruitful arena.

Presenter Notes

Tour por un compilador optimizante

Presenter Notes

Proceso básico de compilación

Basic Compiler Process

Presenter Notes

Lenguaje de representación intermedio

1 int j,k,m,n;
2 while (j<n) {
3     k = k + j*2;
4     m = j*2;
5     j++;
6 }

Luego de gcc -c -fdump-tree-gimple HPC_p52.c:

 1 int D.1715;
 2 int j;
 3 int k;
 4 int m;
 5 int n;
 6 goto <D.1712>;
 7 <D.1711>:
 8 D.1715 = j * 2;
 9 k = D.1715 + k;
10 m = j * 2;
11 j = j + 1;
12 <D.1712>:
13 if (j < n) goto <D.1711>; else goto <D.1713>;
14 <D.1713>:

Presenter Notes

Bloques básicos

Grafo de flujo, donde cada bloque es un straight-line program.

Intermediate languaje divided into basic blocks

Es fácil sacar informacion de definición-uso, propagación de constantes, bloques no-alcanzables, etc.

Presenter Notes

Tipos de optimización

  • Sin optimizar
    Ideal para debuggers, hay una relación 1-a-1 entre código fuente y código de máquina.
  • Optimizaciones básicas
    Es lo que veremos hoy: constant propagation, common expressions, ...
  • Analisis interprocedural
    Extiende las optimizaciones básicas más allá de las fronteras de una función (propagación de constantes, function inlining).
  • Optimizaciones de punto flotante
    Transformaciones algebraicas no-conservativas que incrementan la velocidad.
    Menos manejo de errores.
    Operaciones aproximadas.
  • Análisis de flujo de datos
    Identifica paralelismo en instrucciones, bloques o iteraciones sucesivas de ciclos.
  • Analisis de perfil en tiempo de ejecución Se arma una corrida para juntar información que servirá para que en una segunda fase de compilación se optimize según el perfil encontrado.
  • Optimizaciones Avanzadas

Presenter Notes

Que cosas NO hay que hacer

Presenter Notes

Optimizaciones Clásicas

Constant folding

Fácil, propagación en un término ...

1 PROGRAM MAIN
2 INTEGER I,K
3 PARAMETER (I = 100)
4 K = 200
5 J = I+K
6 PRINT *,J
7 END

Difícil, propagación en 1024 términos ...

1 int main(void){
2     const int C = 1024;
3     int s = 0;
4     for (unsigned int i=0; i<C; ++i) {
5         s += i;
6     }
7     return s;
8 }

¿Podemos hacer que el compilador entre en un lazo infinito? ☺

Si saco const lo sigue optimizando: constant discovery.

Presenter Notes

Eliminación de código muerto

Trivial: HPC_p56.f.

1 INTEGER I,K
2 I = 257
3 WRITE (*,*) I
4 STOP
5 I = 263
6 WRITE (*,*) I
7 END

Un poquito más difícil: HPC_p57.c.

1 #include <stdio.h>
2 
3 int main(void) {
4     int i,k;
5     i = k = 1;
6     i += 257;
7     k += 263; // no existe en el assembler
8     return i;
9 }

Ojo, ojito, el deadcode removal es una fuente infinta de amazing benchmarks ʘ_ʘ

Presenter Notes

Strength reduction

Reemplazar operaciones caras por equivalentes baratas (HPC_p57.f)

1 REAL FUNCTION COMPUTE(X,J)
2 REAL X,Y
3 INTEGER J,K
4 Y = X**3
5 K = J*3
6 COMPUTE = Y+K
7 END

Grandes trucos de manejo bitwise (strength_reduction.c)

1 unsigned int divido_32(unsigned int x) {
2     return x/32;
3 }

clap, clap, clap, ...

Ejemplo clásico

1 for(i=0; i<N; ++i)

El idioma xorl %eax, %eax para setear variables a 0 es otro caso típico.

Presenter Notes

Renombre de Variables

renaming.c

1 void reuso(float x, float y, float z, float *u, float *v, float *w) {
2     float a;
3     a = x + y + z;
4     *u = a;
5     a = y * z;
6     *v = a;
7     a = x * z;
8     *w = a;
9 }

Impide el paralelismo ...

Si compilamos utiliza diferentes registros para la misma variable.
(¿Para qué si hay register renaming por hardware?)

Es interesante ver la diferencia entre -O1 y -O2: planificación para evitar pipeline stalls.

Presenter Notes

Eliminación de subexpresiones comunes

HPC_p58.f

1 REAL FUNCTION COMPUTE(A,B,C,D,E)
2 REAL A,B,C,D,E
3 D = C*(A+B)
4 E = (A+B)/2
5 COMPUTE = D-E
6 END

Calcula una sola vez A+B.

El acceso a índices es una forma muy común de common subexpression elimination.

1 A(I,J) = A(I,J)*2 + A(I+1,J)

Presenter Notes

Sacar expresiones invariantes fuera de lazo

HPC_p59.f

1 SUBROUTINE COMPUTE(A,B,C,D,E,G,K,N)
2 REAL A(*),B(*),C,D,E,G(*)
3 INTEGER K,N
4 DO I=1,N
5     A(I) = B(I) + C*D
6     E = G(K)
7 ENDDO
8 END

clap, clap, clap ...

Es interesante ver las diferencias entre -O1 , -O2 y -O3.

¡Vectorización para -O3!

1 addps  %xmm2, %xmm0

Suma 4 flotantes en una sola operación. Lo importante es la p en addps, significa packed.

Presenter Notes

Simplificación por variables inductivas

HPC_p60.f

1 SUBROUTINE FILL(A,N)
2 REAL A(*)
3 INTEGER N
4 DO I=1,N
5     A(I) = 4*I + N
6 ENDDO
7 END

Caso típico de acceso a arreglos bidimensionales en C y FORTRAN

La dirección de memoria de A(I,J) es

membase + J*rowsize + I

La dirección de memoria de A[I,J] es

membase + I*rowsize + J

Presenter Notes

Un ejemplo más complejo

mixed.c

 1 #define N 128
 2 int a[N];
 3 
 4 int main(void){
 5     for (unsigned int i=0; i<N/2; ++i) {
 6         int four = a[i]*4;
 7         int six = a[i]*6;
 8         a[i] = four;
 9         a[N-i] = six;
10     }
11 }

Notar:

  • No importa que declaremos una variable "nueva" en cada iteración.
  • Usó
    • Induction variable simplification.
    • Common subexpression elimination.
    • Register allocation.

Presenter Notes

Procedure inlining

inlining.c

 1 static int square(int i) {
 2     int result = 0;
 3     result =  i*i;
 4     return result;
 5 }
 6 
 7 int main(void){
 8     const int C = 131072;
 9     int s = 0;
10     for (unsigned int i=0; i<C; ++i) {
11         s += square(i);
12     }
13     return s;
14 }

No tiene sentido usar #define SQUARE(I) ((I)*(I)), esto es igual de eficiente y utiliza el sistema de tipos!

Presenter Notes

Loop unswitching

Arregla este tipo de códigos mal escritos.

loop_unswitch.c

1 void compute0(float a[], const unsigned int N, const int first) {
2     for (unsigned int i=0; i<N; ++i) {
3         if (first==1) {
4             a[i] = 0;
5         } else {
6             a[i] = a[i]/2;
7         }
8     }
9 }

Saca el condicional afuera, armando dos lazo uno por rama.

Presenter Notes

Conversiones de tipos constantes

type_conversions.c

 1 float conv1(float x) {
 2     return 3*x;
 3 }
 4 
 5 float conv2(float x) {
 6     return 3.0*x;
 7 }
 8 
 9 float conv3(float x) {
10     return 3.0f*x;
11 }

Da lo mismo, aunque:

  • La primera es un entero.
  • La segunda un doble.
  • La tercera un flotante.

Ojo! Para ciertos compiladores (nvcc) esto produce 3 versiones distintas.

Presenter Notes

Una tabla

Comparación de optimizaciones de compiladores

(Agner Fog, Optimizing software in C++ ...)

Presenter Notes

Una tabla

Comparación de optimizaciones de compiladores, 2nd

(Agner Fog, Optimizing software in C++ ...)

Presenter Notes

Que es lo que VALE LA PENA hacer

Presenter Notes

Condiciones dependientes del índice

Esto no lo simplifica en loop_branch.c

1 void compute0(float a[], const unsigned int N) {
2     for (unsigned int i=0; i<N; ++i) {
3         if (i==0) {
4             a[i] = a[i]/2;
5         } else {
6             a[i] = a[i-1]/2;
7         }
8     }
9 }

Presenter Notes

Condiciones dependientes índice

Ejemplo: condiciones de borde no-periódicas en loop_branch.c.

 1 void compute1(float a[], const unsigned int N) {
 2     for (unsigned int i=0; i<N; ++i) {
 3         if (i==0) {
 4             a[i] = a[i+1]/2;
 5         } else if (i==N-1) {
 6             a[i] = a[i-1]/2;
 7         } else { // 0<i<N-1
 8             a[i] = (a[i-1]+a[i+1])/2;
 9         }
10     }
11 }

Conviene reescribirlo asi

1 void compute2(float a[], const unsigned int N) {
2     a[0]=a[1]/2;
3     for (unsigned int i=1; i<N-1; ++i) {
4         a[i] = (a[i-1]+a[i+1])/2;
5     }
6     a[N-1]=a[N-2]/2;
7 }

Presenter Notes

Condiciones dependientes índice

Algo se debería poder hacer.

Mirar Graphite y
-floop-interchange -ftree-loop-distribution
-floop-strip-mine -floop-block

Mirar todas las opciones -ftree-loop-* en GCC Optimize Options

La/el que encuentre algo -> Polvoritas™

Presenter Notes

Condiciones dependientes de la iteración

1 DO I=1,N
2     IF (X .LT. A(I)) X = X + B(I)*2
3 ENDDO

No hay mucho para hacer salvo desenrollar el lazo un poquito a mano.

Presenter Notes

Condiciones que transfieren el control

No hagan estas cosas.

1 DO I=1,N
2     DO J=1,N
3         IF (B(J,I) .EQ. 0) THEN
4             PRINT *,I,J
5             STOP
6         ENDIF
7         A(J,I) = A(J,I)/B(J,I)
8     ENDDO
9 ENDDO

Presenter Notes

Bibliografía

Presenter Notes

Bibliografía

Lectura adicional

Presenter Notes

La clase que viene

  • Optimizaciones de lazos: lo que no vale y lo que si vale.

Dos ejemplos para sgemm:

  • Más ILP: loop unrolling.
  • Más ancho de banda de memoria: blocking.

Presenter Notes