Nicolás Wolovick 20160329
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.
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>:
Grafo de flujo, donde cada bloque es un straight-line program.
Es fácil sacar informacion de definición-uso, propagación de constantes, bloques no-alcanzables, etc.
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.
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 ʘ_ʘ
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, ...
1 for(i=0; i<N; ++i)
El idioma xorl %eax, %eax
para setear variables a 0 es otro caso típico.
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.
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)
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.
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
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
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:
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!
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.
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:
Ojo! Para ciertos compiladores (nvcc
) esto produce 3 versiones distintas.
(Agner Fog, Optimizing software in C++ ...)
(Agner Fog, Optimizing software in C++ ...)
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 }
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 }
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™
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.
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
Dos ejemplos para sgemm
:
Table of Contents | t |
---|---|
Exposé | ESC |
Full screen slides | e |
Presenter View | p |
Source Files | s |
Slide Numbers | n |
Toggle screen blanking | b |
Show/hide slide context | c |
Notes | 2 |
Help | h |