En esta sección se van a proponer distintos experimentos que tienen por objetivo ilustrar algunos de los mecanismos básicos de optimización que incluyen los modernos compiladores de hoy en día. En cada uno de los apartados que siguen a continuación donde se describen las optimizaciones básicas aparecen varios campos:

• un título: OPTIMIZACIÓN, que indica el tipo de optimización de que se trata.
• un código de partida: ANTES, que representa un código sin optimizar.
• un código final: DESPUÉS, que representa el código resultante de aplicar la optimización indicada en el título.

Pasos para la realización de la práctica:

• 1.- Para cada una de las Optimizaciones Básicas que se relacionan más abajo, se ha de desarrollar un programa que siga la siguiente estructura general:

---


                double    utime0, stime0, wtime0,
                               utime1, stime1, wtime1,
                               utime2, stime2, wtime2;

                /* Establecimiento del instante inicial de medición de tiempo. */
                uswtime(&utime0, &stime0, &wtime0);

             /* Código ANTES. */

                    . . .    . . .   . . .
 

             /* Instante final del tiempo de ejecución del código ANTES. */
                /* Establecimiento del instante inicial del medición de tiempo para código
                    DESPUÉS. */
                uswtime(&utime1, &stime1, &wtime1);

             /* Código DESPUÉS. */

                    . . .    . . .   . . .

             /* Instante final del tiempo de ejecución del código ANTES. */
                uswtime(&utime2, &stime2, &wtime2);

             /* --- Cálculo de los tiempos de ejecución. --- */

                /* Código ANTES: */
                 printf("\nCódigo ANTES:\n");
                 printf("real  %.3f\n",  wtime1 - wtime0);
                 printf("user  %.3f\n",  utime1 - utime0);
                 printf("sys   %.3f\n",  stime1 - stime0);
                 printf("\n");
                 printf("CPU/Wall   %.3f %% \n",
                             100.0 * (utime1 - utime0 + stime1 - stime0) / (wtime1 - wtime0));
                 printf("\n");

               /* Código DESPUÉS: */
                 printf("\nCódigo DESPUÉS:\n");
                 printf("real  %.3f\n",  wtime2 - wtime1);
                 printf("user  %.3f\n",  utime2 - utime1);
                 printf("sys   %.3f\n",  stime2 - stime1);
                 printf("\n");
                 printf("CPU/Wall   %.3f %% \n",
                             100.0 * (utime2 - utime1 + stime2 - stime1) / (wtime2 - wtime1));
                 printf("\n");

                /* Factor de Ganancia */
                 printf("\nFactor de Ganancia:\n");
                 printf("CPU        %.2f \n",
                        (utime1 - utime0 + stime1 - stime0) / (utime2 - utime1 + stime2 - stime1));
                 printf("Wall       %.2f \n", (wtime1 - wtime0) / (wtime2 - wtime1));
                 printf("\n");

---

• 2.- Compilación del programa con el compilador gcc, sin emplear ninguna opción de optimización:

gcc -o programa programa.c -lm
• 3.- A continuación se procede a la ejecución del programa, obteniendo los tiempos de ejecución (CPU time, el conjunto de los tiempos de usuario y sistema) de los segmentos de código ANTES y DESPUÉS, así como el factor de ganancia.

• 4.- Compilación del programa con el compilador gcc,  empleando optimización del compilador:

• 5.-  Ejecución del programa, obteniendo los tiempos de ejecución (CPU time, el conjunto de los tiempos de usuario y sistema) de los segmentos de código ANTES y DESPUÉS, así como el factor de ganancia.

• 6.- Repetir los pasos anteriores para varios valores de N (tamaño del problema): potencias de 2 hasta llegar a un máximo de la la memoria RAM del computador. El objetivo es realizar una gráfica de los factores de ganancia en función del tamaño del problema. El valor de N se puede establecer como una constante definida en el programa:

• Comentarios: En condiciones normales, los segmentos de código DESPUÉS han de mostrar tiempos de ejecución más bajos que los correspondientes códigos ANTES. El alumno ha de reflexionar y pensar en las posibles causas por las cuales se consigue ese ahorro en tiempo de ejecución, intentando relacionarlo con los conceptos vistos en clase de teoría. Por ejemplo, en el caso de la optimización por intercambio de bucles, la razón por la cual se gana de forma sustancial en tiempo de ejecución es porque se logra acceso a memoria por stride unidad. Otras razones que se pueden dar es por la sustitución de determinadas operaciones complejas por operaciones más simples (p.ej. la división en punto flotante se sustituye por la multiplicación en punto flotante porque en la mayoría de los computadores la multiplicación es menos costosa y, además, en algunos procesadores la unidad funcional de división ni siquiera está segmentada, con lo cual el throughput asociado es mínimo.

• Para obtener un tiempo de computación y un factor de ganancia significativo, los bucles se repiten ITER iteraciones, donde ITER es una constante definida como 100 al principio de los programas:

            El tiempo de computación mínimo para que sea significativo ha de ser de 1 segundo al menos.

Optimizaciones básicas:

Los mecanismos básicos de optimización que se han de implementar son los que se relacionan a continuación:
 

---

pr1: OPTIMIZACIÓN: Eliminación de expresiones comunes.

---

                       ANTES:

main()
{
int i, j;
float a, b, c, d, k, x, y, z, t;
static float A[N];

for(j=0; j<ITER; j++)
   for(i=0; i<N; i++){
       a = x * y * z * A[i];
       b = x * z * t;
       c = t * A[i];
       d = k * A[i];
       A[i] = z * x * A[i];
       }
}

                      DESPUÉS:

main()
{
int i, j;
float a, b, c, d, k, x, y, z, t;
static float A[N];

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        register float tmp1, tmp2, tmp3;
        tmp1 = x * z;
        tmp2 = A[i];
        tmp3 = tmp1 * tmp2;
        a = tmp3 * y;
        b = tmp1 * t;
        c = t * tmp2;
        d = k * tmp2;
        A[i] = tmp3;
        }
}

---

pr2: OPTIMIZACIÓN: Reemplazo de multiplicaciones/divisiones enteras por operaciones de
                            desplazamiento.

---

                          ANTES:

main()
{
int i, j, a, b;

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        a = i * 128;
        b = a / 32;
        }
}

                       DESPUÉS:

main()
{
int i, j, a, b;
 

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        a = i << 7;
        b = a >> 5;
        }
}

---

pr3: OPTIMIZACIÓN: Reemplazo de divisiones enteras de 32 bits por divisiones  punto flotante de
                            64 bits.

---

                          ANTES:

main()
{
int i, j, a;

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        a = i / 545;
        }
}

                         DESPUÉS:

main()
{
int i, j, a;

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        a = (int)((float)i / 545.0);
        }
}

---

pr4: OPTIMIZACIÓN: Reemplazo de divisiones en punto flotante por una sola división y
                            multiplicaciones

---

                        ANTES:

main()
{
int i, j;
float a, b, c ,d, t, u, v, x, y, z, tmp;

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        x = i+1.0;
        y = j+x;
        a = u / x;
        b = t / x;
        c = z / y;
        d = v /(x*y);
        }
}

                       DESPUÉS:

main()
{
int i, j;
float a, b, c ,d, t, u, v, x, y, z, tmp;

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        x = i+1.0;
        y = j+x;
        tmp = 1/(x*y);
        a = u * y * tmp;
        b = t * y * tmp;
        c = z * x * tmp;
        d = v * tmp;
        }

}

---

pr5: OPTIMIZACIÓN: Pasar bucles dentro del procedimiento/función

---

                        ANTES:
 

void add(float x, float y, float *z)
{
*z = x + y;
}

...

main()
{
int i, j;
static float x[N], y[N], z[N];

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        add(x[i], y[i], &z[i]);
        }
}

                       DESPUÉS:
 

void add2(float *x, float *y, float *z)
{
register int i, j;

for(j=0; j<ITER; j++)
   for(i=0; i<N; i++)
       z[i] = x[i] + y[i];
}

...

main()
{
static float x[N], y[N], z[N];

add2(x, y, z);
}

---

pr6: OPTIMIZACIÓN: Inlining: Sustituir la llamada a una función por el propio cuerpo de la función.

---

                        ANTES:

void add(float x, float y, float *z)
{
*z = x + y;
}

...

main()
{
int i, j;
static float x[N], y[N], z[N];

for(j=0; j<ITER; j++)
    for(i=0; i<N; i++){
        add(x[i], y[i], &z[i]);
        }
}

                       DESPUÉS:

main()
{
int i, j;
static float x[N], y[N], z[N];

for(j=0; j<ITER; j++)
   for(i=0; i<N; i++)
       z[i] = x[i] * y[i];
}
 

---

pr7: OPTIMIZACIÓN: Fusión de bucles: Combinar los cuerpos de varios bucles en un solo bucle

---

                        ANTES:

main()
{
int i, j;
static float  x[N], y[N], z[N], k[N], t[N], u[N];

for(j=0; j<ITER; j++){
    for(i=0; i<N; i++)
     z[i] = x[i] + y[i];
    for(i=0; i<N; i++)
     k[i] = x[i] - y[i];
    for(i=0; i<N; i++)
     t[i] = x[i] * y[i];
    for(i=0; i<N; i++)
     u[i] = z[i] + k[i] + t[i];
    }
}

                       DESPUÉS:

main()
{
int i, j;
static float  x[N], y[N], z[N], k[N], t[N], u[N];

for(j=0; j<ITER; j++){
    for(i=0; i<N; i++) {
        register float tmpx, tmpy;
        tmpx = x[i];
        tmpy = y[i];
        z[i] = tmpx + tmpy;
        k[i] = tmpx - tmpy;
        t[i] = tmpx * tmpy;
        u[i] = z[i] + k[i] + t[i];
        }
     }
}

---

pr8: OPTIMIZACIÓN: Fusión de bucles (II)

---

                        ANTES:

main()
{
int i, j;
typedef struct {float x, y, z;} nuevotipo;
static nuevotipo v1[N], v2[N], v3[N];

for(j=0; j<ITER; j++){
    for(i=0; i<N; i++)
     v3[i].x = v1[i].x + v2[i].x;
    for(i=0; i<N; i++)
     v3[i].y = v1[i].y - v2[i].y;
    for(i=0; i<N; i++)
     v3[i].z = v1[i].z * v2[i].z;
    }
}
 

                       DESPUÉS:

main()
{
int i, j;
typedef struct {float x, y, z;} nuevotipo;
static nuevotipo v1[N], v2[N], v3[N];

for(j=0; j<ITER; j++){
    for(i=0; i<N; i++) {
     v3[i].x = v1[i].x + v2[i].x;
     v3[i].y = v1[i].y - v2[i].y;
     v3[i].z = v1[i].z * v2[i].z;
     }
    }
}

---

pr9: OPTIMIZACIÓN: Intercambio de bucles: Intercambio de bucles para permitir acceso a memoria
                            por stride.

---

                        ANTES:

main()
{
int i, j, k;
static float  x[N][N], y[N][N];

for(k=0; k<ITER; k++){
    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
            y[j][i] = x[j][i] + 3.0;
        }
}

                       DESPUÉS:

main()
{
int i, j, k;
static float  x[N][N], y[N][N];

for(k=0; k<ITER; k++){
    for(j=0; j<N; j++)
        for(i=0; i<N; i++)
            y[j][i] = x[j][i] + 3.0;
        }
}

---

pr10: OPTIMIZACIÓN: Loop peeling.

---

                        ANTES:

main()
{
int i, j, k;
static float  x[N], y[N];

for(k=0; k<ITER; k++)
    for(i=0; i<N; i++)
       if(i==0) x[i] = 0;
       else if(i==N-1) x[i] = N-1;
       else x[i] = x[i]+y[i];
}

                       DESPUÉS:

main()
{
int i, j, k;
static float  x[N], y[N];

for(k=0; k<ITER; k++)     {
    x[0] = 0;
    x[N-1] = N-1;
    for(i=1; i<N-1; i++)
        x[i] = x[i]+y[i];
    }

}

---

pr11: OPTIMIZACIÓN: Test promotion.

---

                        ANTES:

main()
{
int i, j, k;
static float a, x[N], y[N];

for(k=0; k<ITER; k++)
    for(i=0; i<N; i++)
       if(a==0.0) x[i] = 0;
       else y[i] = x[i]*y[i];
}

                       DESPUÉS:

main()
{
int i, j, k;
static float  a, x[N], y[N];

for(k=0; k<ITER; k++)     {
    if(a==0) {
        for(i=0; i<N; i++)
           x[i] = 0;
        }
    else {
        for(i=0; i<N; i++)
            y[i] = x[i]*y[i];
        }
    }
}

---

pr12: OPTIMIZACIÓN:  Overhead debido a los if

---

                        ANTES:

main()
{
int i, j, k;
static float x[2*N][2*N], z[2*N][2*N];

for(k=0; k<ITER; k++)
    for(j=-N; j<N; j++)
        for(i=-N; i<N; i++){
            if(i*i+j*j != 0)
              z[N+j][N+i] = x[N+j][N+i] / (i*i+j*j);
            else
              z[N+j][N+i] = 0.0F;
            }
}

                       DESPUÉS:

main()
{
int i, j, k;
static float x[2*N][2*N], z[2*N][2*N];

for(k=0; k<ITER; k++)
    for(j=-N; j<N; j++) {
        for(i=-N; i<0; i++)
            z[N+j][N+i] = x[N+j][N+i] / (i*i+j*j);
        z[N+j][N] = 0.0F;
        for(i=1; i<N; i++)
            z[N+j][N+i] = x[N+j][N+i] / (i*i+j*j);
        }
}
 

---

pr13: OPTIMIZACIÓN: Unión balanceada de operaciones.

---

                        ANTES:

main()
{
int i, j, k;
static float x[N], y[N];

for(k=0; k<ITER; k++){
    for(i=0; i<N; i++)
        x[i] = sqrt((float)i);
    for(i=0; i<N; i++)
        y[i] = (float)i+2.0;
    }
}

                       DESPUÉS:

main()
{
int i, j, k;
static float  x[N], y[N];

for(k=0; k<ITER; k++){
    for(i=0; i<N; i++) {
        x[i] = sqrt((float)i);
        y[i] = (float)i+2.0;
        }
    }

}

---

pr14: OPTIMIZACIÓN: Desenrolle de bucles internos

---

                        ANTES:

main()
{
int i, k;
float a, b;
static float x[N], y[N];

for(k=0; k<ITER; k++){
    for(i=0; i<N; i++)
        y[i] = a * x[i] + b;
    }
}

                       DESPUÉS:

main()
{
int i, k;
float a, b;
static float x[N], y[N];

for(k=0; k<ITER; k++){
    for(i=0; i<N; i+=4){
        y[i]   = a * x[i]   + b;
        y[i+1] = a * x[i+1] + b;
        y[i+2] = a * x[i+2] + b;
        y[i+3] = a * x[i+3] + b;
        }
    }
}

---

pr15: OPTIMIZACIÓN: Desenrolle de bucles internos y optimización de reducciones

---

                        ANTES:

main()
{
int i, j, k;
static float x[N], y[N];
register float a, a1, a2, a3;

for(k=0; k<ITER; k++){
    a=0.0;
    for(i=0; i<N; i++)
        a = a + x[i] * y[i];
    }
}

                       DESPUÉS:

main()
{
int i, j, k;
static float x[N], y[N];
register float a, a1, a2, a3;

for(k=0; k<ITER; k++){
    a = a1 = a2 = a3 = 0.0;
    for(i=0; i<N; i+=4){
        a  = a  + x[i]   * y[i];
        a1 = a1 + x[i+1] * y[i+1];
        a2 = a2 + x[i+2] * y[i+2];
        a3 = a3 + x[i+3] * y[i+3];
        }
    a = a + a1 + a2 + a3;
    }
}

---

pr16: OPTIMIZACIÓN: Desenrolle de bucles internos y optimización de reducciones (2)

---

                        ANTES:

main()
{
int i, j, k;
static int x[N];
register int a, a0, a1, a2, a3;
 

for(k=0; k<ITER; k++){
    a=1.0;
    for(i=0; i<N; i++)
        a = a * x[i];
    }
}

                       DESPUÉS:

main()
{
int i, j, k;
static int x[N];
register int a, a0, a1, a2, a3;

for(k=0; k<ITER; k++){
    a = 1.0;
    for(i=0; i<N; i+=4){
        a0 = x[i];
        a1 = x[i+1];
        a2 = x[i+2];
        a3 = x[i+3];
        a = a * (a0*(a1*(a2*a3)));
        }
    }
}

---

pr17: OPTIMIZACIÓN: Desenrolle de bucles internos y optimización de reducciones (3)

---

                        ANTES:

main()
{
int i, j, k;
static int x[N];
register int a, a0, a1, a2, a3;
 

for(k=0; k<ITER; k++){
    a=1.0;
    for(i=0; i<N; i++)
        a *= x[i];
    }
}

                       DESPUÉS:

main()
{
int i, j, k;
static int x[N];
register int a, a0, a1, a2, a3;
 

for(k=0; k<ITER; k++){
    a = a1 = a2 = a3 = 1.0;
    for(i=0; i<N; i+=4){
        a  *= x[i];
        a1 *= x[i+1];
        a2 *= x[i+2];
        a3 *= x[i+3];
        }
    a = a * (a1*(a2*a3));
    }
}

---

pr18: OPTIMIZACIÓN: Unroll and Jam

---

                        ANTES:

 
main()
{
register int i, j, k, l;
static float  a[N][N], b[N][N], c[N][N];

for(l=0; l<ITER; l++){
    for(i=0; i<N; i++)
     for(j=0; j<N; j++)
        for(k=0; k<N; k++)
           c[k][i] += a[k][j] * b[j][i];
    }
}

                       DESPUÉS:

main()
{
register int i, j, k, l;
static float  a[N][N], b[N][N], c[N][N];

for(l=0; l<ITER; l++){
    for(i=0; i<N; i+=2)
        for(j=0; j<N; j+=2)
           for(k=0; k<N; k++){
              c[k][i] += a[k][j] * b[j][i] + a[k][j+1] * b[j+1][i] ;
              c[k][i+1] += a[k][j] * b[j][i+1] + a[k][j+1] * b[j+1][i+1] ;
              }
    }
}

---

pr19: OPTIMIZACIÓN: Reordenamiento de bucles para mejora de la localidad espacial en la multiplicación de matrices.

---

Considere el problema de la multiplicación de 2 matrices de tamaño NxN: C=A*B. El procedimiento que normalmente se utiliza para implementar esta multiplicación normalmente consta de 3 bucles anidados con índices i, j y k:

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++) {
        sum = 0.0;
        for (k = 0; k < N; k++)
            sum += A[i][k]*B[k][j];
        C[i][j] += sum;
        }

Es posible modificar el orden de los bucles y realizar pequeños cambios en el código para mejorar la localidad espacial y mejorar el rendimiento. En esta práctica se proporciona un programa en C llamado mm.c que contiene 6 versiones funcionalmente equivalentes de este código. Las 6 versiones están denotadas por el orden de los índices de los bucles: ijk, jik, jki, kji, kij, ikj. Para ver la implementación exacta, véase el código fuente mm.c Compile y ejecute el programa. El programa proporciona los tiempos de computación para distintos valores de N.  Realice un gráfica con los tiempos de ejecución en función del tamaño del problema (N). Fíjese en cuáles son los órdenes de los bucles que permiten ejecutar la multiplicación de forma más eficaz, y piense en cuáles pueden ser las razones por las que las distintas versiones funcionan de forma tan distinta.

---