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 20140320

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, dada 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,

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).
  • 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 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.
  • 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.

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.

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.

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.

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

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, bueno ... no hace esto de renaming. Tal vez sea algo que está un poco viejo del libro de Severance-Dowd.

Es interesante ver la diferencia entre -O1 y -O2: planificación.

Presenter Notes

Eliminación de subexpresiones comunes

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

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

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

Los accesos a arreglos A(I,J) son el típico caso de esta simplificación.

Presenter Notes

Un ejemplo más complejo

 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 }
12 // gcc -S -O1 -std=c99 mixed.c

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

 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 }
15 // gcc -S -O1 -std=c99 inlining.c
16 // static inline int square(int i) {

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.

 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 }
10 // gcc -S -O1 -funswitch-loops -std=c99 loop_unswitch.c

Saca el condicional afuera, armando dos lazos, uno en cada rama.

Presenter Notes

Conversiones de tipos constantes

 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 índice

Ejemplo: condiciones de borde no-periódicas

 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 del índice

Esto tampoco lo simplifica

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 }

Algo se debería poder hacer.

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

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