Ir al contenido

Desenroscado de bucles

De Wikipedia, la enciclopedia libre
Este artículo o sección necesita referencias que aparezcan en una publicación acreditada.
Busca fuentes: «Desenroscado de bucles» – noticias · libros · académico · imágenes
Este aviso fue puesto el 13 de mayo de 2014.

El Desenroscado de bucles (conocido en inglés como loop unrolling o Loop unwinding) es una técnica de optimización de bucles que intenta mejorar la velocidad de ejecución de un programa a costa de aumentar su tamaño binario (Situación de compromiso espacio-tiempo). Esta transformación puede hacerla manualmente el programador o un Compilador optimizador.

El objetivo del desenroscado de bucles es incrementar la velocidad del programa al reducir (o eliminar) instrucciones que controlan el bucle, como aritmética de punteros o la verificación de final de bucle en cada iteración;[1]​ reduciendo la penalización por ramificación además de “ocultar latencias, en particular, la espera de la lectura de datos de memoria”.[2]​ Para eliminar esta sobrecarga en la computación, los bucles pueden ser reescritos como una repetición de sentencias similares independientes.[3]​

Ventajas

[editar]

El mayor peso en los bucles pequeños se localiza en las instrucciones que incrementan el puntero o índice al siguiente elemento del array y en los test de “¿ha finalizado el bucle?”. Si un compilador o ensamblador de optimización es capaz de precalcular compensaciones para cada variable de la matriz referenciada individualmente, éstas pueden incorporarse directamente en las instrucciones de código de máquina, por lo que no requieren operaciones aritméticas adicionales en tiempo de ejecución.

  • Puede conseguirse una mejora significativa si la reducción de instrucciones a ejecutar compensa por cualquier pérdida de rendimiento causada por el incremento en el tamaño del programa.
  • La predicción de saltos se minimiza.[4]​
  • Si las instrucciones del bucle son independientes entre sí (es decir: si las instrucciones de un ciclo del bucle no afectan a las instrucciones del ciclo siguiente), éstas pueden ser ejecutadas en paralelo.
  • El desenroscado puede realizarse dinámicamente si el número de elementos del array no se conoce en tiempo de compilación (como en el Dispositivo de Duff).

Los compiladores optimizadores pueden desenroscar bucles automáticamente o bajo demanda.

Desventajas

[editar]
  • El tamaño del programa aumenta, este efecto puede no ser deseado, particularmente en aplicaciones embebidas.
  • Puede que también cause un incremento en los fallos de caché de instrucción, que afectan negativamente al rendimiento.
  • A menos que la transformación sea aplicada de manera transparente por un compilador optimizador, el código resultante es menos legible.
  • Si en el cuerpo del bucle se realizan llamadas a función, puede que no sea posible combinar el desenroscado con Inlining, ya que el incremento del tamaño el código podría ser excesivo. Por lo tanto, puede que se deba escoger entre ambas optimizaciones.
  • Posible aumento del uso de los registros en una sola iteración para almacenar variables temporales[cita requerida], lo que puede reducir el rendimiento, aunque dependerá mucho de posibles optimizaciones[5]​
  • Con la excepción de códigos muy pequeños y simples, los bucles desenroscados que contienen ramificaciones son más lentos que si se usa recursión.[6]​

Desenroscado de bucles estático o manual

[editar]

El desenroscado de bucles manual (o estático) requiere que el programador analice el bucle e interprete sus iteraciones como una secuencia de instrucciones que pueden reducir la sobrecarga del bucle. Sería el desenroscado opuesto al desenroscado dinámico, que es realizado por el compilador.

Ejemplo de desenroscado manual en C

[editar]

Supongamos que debemos optimizar una función que borra exactamente 100 objetos de una colección. Esta operación se haría normalmente con un bucle for que llamaría a la función borrar(indice_de_objeto);. Si la carga de trabajo del bucle es mayor que la requerida por la función de borrado, desenroscar el bucle puede acelerar el proceso.

Bucle normal Bucle desenroscado 
for (int indice = 0; indice < 100; ++indice)
{
    borrar(indice);
}

for (int indice = 0; indice < 100; indice += 5)
{
    borrar(indice);
    borrar(indice + 1);
    borrar(indice + 2);
    borrar(indice + 3);
    borrar(indice + 4);
}

Como consecuencia de esta modificación, el nuevo programa debe hacer 20 iteraciones en lugar de 100. Por lo tanto sólo deben hacerse el 20% de los saltos y ramificaciones condicionales, lo cual puede ser un descenso potencialmente significativo de la carga de administración del bucle. Para un óptimo beneficio no deben usarse variables que requieran aritmética de punteros en el código desenroscado.

Por otro lado, este desenroscado manual hace crecer el código de 4 a 8 líneas, pudiendo provocar durante la ejecución que se usen más registros para almacenar las variables de cada iteración[cita requerida]. Además, las variables de control del bucle y la cantidad de operaciones en la estructura desenroscada deben ser escogidas cuidadosamente para asegurar que el comportamiento es el mismo que en el código original. Por ejemplo, debemos considerar la posibilidad de que la cantidad de iteraciones no fuese divisible por 5. Los cambios requeridos también se complican si las condiciones de finalización del bucle son variables.

Complejidad prematura

[editar]

En este simple caso, el control del bucle es tan solo un trabajo extra que organiza las instrucciones. El bucle en sí mismo no contribuye a obtener el resultado deseado, tan sólo ahorra al programador del tedio de replicar el código varias veces, esta tarea podría haber sido delegada al preprocesador o a las herramientas de los editores de texto. De manera parecida, las instrucciones if y otras estructuras de control del flujo de programa pueden ser sustituidas por código replicado, con la salvedad de que inflan el código. Es trivial para un programa realizar las combinaciones, pero un programador puede encontrar la repetición aburrida y cometer errores.

Bucle normal Bucle desenroscado 
  for (indice = 1; indice <= 8; indice++){
      if (indice % 2 == 0)
          cosas_pares(indice);
      else
          cosas_impares(indice);
  }

  cosas_impares(1); cosas_pares(2);
  cosas_impares(3); cosas_pares(4);
  cosas_impares(5); cosas_pares(6);
  cosas_impares(7); cosas_pares(8);

El siguiente ejemplo incluye la variable de índice en el cómputo:

Bucle normal Bucle desenroscado 
  x(1) = 1;
  for (indice = 2; indice <= 9; indice++){
      x(indice) = x(indice - 1) * indice;
      printf("%d %d",indice,x(indice));
  }

  x(1) = 1;
  x(2) = x(1) * 2; printf("2%d",x(2));
  x(3) = x(2) * 3; printf("3%d",x(3));
  x(4) = x(3) * 4; printf("4%d",x(4));
  ...etc.

que al ser compilado, producirá gran cantidad de código (se podrán ver muchas instrucciones print) pero es posible aplicar más optimizaciones. En el ejemplo anterior sólo se hace referencia a x(indice) y x(indice - 1) en el bucle, por lo tanto: al no haber más referencias a la colección x sus usos pueden ser reemplazados por una variable. Pero hacer dicho cambio puede evitar que el compilador se de cuenta de que los valores del array son constantes, cada uno de ellos derivado de una constante previa y que por lo tanto podría resumir el código para que quedase: 

  printf ("2,2");
  printf ("3,6");
  printf ("4,24");
  ...etc.

En general, el contenido de un bucle puede ser grande, implicando complejas indexaciones de array. Probablemente estos casos sean los mejores para dejar que un compilador optimizador desenrosque el bucle. Al replicar los bucles más internos puede permitir varias optimizaciones aunque la ganancia sea pequeña a no ser que el índice del bucle sea grande.

Desenroscando bucles WHILE

[editar]

Un bucle WHILE similar al siguiente (expresado en pseudocódigo)

Bucle normal Bucle desenroscado Bucle desenroscado y retocado 
  WHILE (condición) DO
      acción
  ENDWHILE
  ...

  WHILE (condición) DO
      acción
      IF NOT(condición) THEN GOTO salir
      acción
      IF NOT(condición) THEN GOTO salir
      acción
  ENDWHILE
  LABEL salir:
  .

  IF (condición) THEN
      REPEAT {
          acción
          IF NOT(condición) THEN GOTO salir
          acción
          IF NOT(condición) THEN GOTO salir
          acción
      } WHILE (condición)
  LABEL salir:

Este desenroscado acelera el bucle ya que la instrucción ENDWHILE (que se compilará como un salto al inicio del bucle) se ejecutará tan sólo una tercera parte de las veces.

Es incluso mejor el ejemplo de pseudocódigo retocado, en que algunos compiladores optimizadores eliminarán por completo los saltos incondicionales.

Desenroscado dinámico

[editar]

Dado que los beneficios del desenroscado de bucles suelen depender del tamaño del array (del que habitualmente no se sabe el tamaño hasta que se ejecuta el código) los compiladores en tiempo de ejecución pueden decidir si ejecutar un bucle normal o generar una secuencia (relativamente corta) de instrucciones individuales para cada elemento. Esta flexibilidad es una de las ventajas de las técnicas de compilación en tiempo de ejecución frente a la compilación estática o la optimización manual en el contexto del desenroscado de bucles. En esta situación, incluso con valores de índice la mejora es útil al requerir poco (o ningún) incremento del tamaño del programa.

Los programadores de lenguaje ensamblador (incluyendo los desarrolladores de compiladores optimizadores) también pueden beneficiarse del desenroscado dinámico de bucles, usando un método similar al que se usa para las tablas de saltos eficientes. En este caso, el mejor rendimiento se da cuando el índice máximo de cualquier campo referenciado en un array es menor al desplazamiento máximo que puede ser especificado en una instrucción en código máquina (que será marcado por el compilador si se sobrepasa).

El siguiente ejemplo es para los ensambladores de IBM S/360 o Z/Architecture y asume que un campo de 100 bytes será copiado desde un array llamado FROM a uno llamado TO (ambos con elementos de 256 bytes con 50 entradas).

Ejemplo en ensamblador (IBM/360 o Z/Architecture)

[editar]
Para un ejemplo en x86 ver Enlaces externos.
 * initialize all the registers to point to arrays etc  (R14 is return address)
          LM    R15,R2,INIT                       load R15= '16', R0=number in array, R1--> 'FROM array', R2--> 'TO array'
 LOOP     EQU   *
          SR    R15,R0                            get 16 minus the number in the array
          BNP   ALL                               if n > 16 need to do all of the sequence, then repeat
 * (if # entries = zero, R15 will now still be 16, so all the MVC's will be bypassed)
 * calculate an offset (from start of MVC sequence) for unconditional branch to 'unwound' MVC loop
          MH    R15,=AL2(ILEN)                    multiply by length of (MVC..) instruction (=6 in this example)
          B     ALL(R15)                          indexed branch instruction (to MVC with drop through)
 * Assignment (move) table - (first entry has maximum allowable offset with single register = X'F00' in this example)
 ALL      MVC   15*256(100,R2),15*256(R1)         * move 100 bytes of 16th entry  from array 1 to array 2 (with drop through)
 ILEN     EQU   *-ALL                                         length of (MVC...) instruction sequence; in this case =6
          MVC   14*256(100,R2),14*256(R1)         *
          MVC   13*256(100,R2),13*256(R1)         *
          MVC   12*256(100,R2),12*256(R1)         * All 16 of these 'move character' instructions use base plus offset addressing
          MVC   11*256(100,R2),11*256(R1)         * and each to/from offset decreases by the length of one array element (256).
          MVC   10*256(100,R2),10*256(R1)         * This avoids pointer arithmetic being required for each element up to a 
          MVC   09*256(100,R2),09*256(R1)         * maximum permissible offset within the instruction of X'FFF'. The instructions 
          MVC   08*256(100,R2),08*256(R1)         * are in order of decreasing offset, so the first element in the set is moved
          MVC   07*256(100,R2),07*256(R1)         * last.
          MVC   06*256(100,R2),06*256(R1)         *
          MVC   05*256(100,R2),05*256(R1)         *
          MVC   04*256(100,R2),04*256(R1)         *
          MVC   03*256(100,R2),03*256(R1)         *
          MVC   02*256(100,R2),02*256(R1)         *
          MVC   01*256(100,R2),01*256(R1)         move 100 bytes of 2nd entry
          MVC   00*256(100,R2),00*256(R1)         move 100 bytes of 1st entry
 *
          S     R0,MAXM1                          reduce Count = remaining entries to process
          BNPR  R14                               ... no more, so return to address in R14
          AH    R1,=AL2(16*256)                   increment 'FROM' register pointer beyond first set
          AH    R2,=AL2(16*256)                   increment 'TO'   register pointer beyond first set
          L     R15,MAXM1                         re-load (maximum MVC's) in R15 (destroyed by calculation earlier)
          B     LOOP                              go and execute loop again
 *
 * ----- Define static Constants and variables (These could be passed as parameters) ---------------------------------  *
 INIT     DS    0A                                4 addresses (pointers) to be pre-loaded with a 'LM' instruction
 MAXM1    DC    A(16)                             maximum MVC's 
 N        DC    A(50)                             number of actual entries in array (a variable, set elsewhere)
          DC    A(FROM)                           address of start of array 1 ("pointer")
          DC    A(TO)                             address of start of array 2 ("pointer")
 * ----- Define static Arrays (These could be dynamically acquired) --------------------------------------------------  *
 FROM     DS    50CL256                          array of (max) 50 entries of 256 bytes each
 TO       DS    50CL256                          array of (max) 50 entries of 256 bytes each

En este ejemplo, se necesitarán aproximadamente 202 instrucciones para un bucle 'conventional' (50 iteraciones) mientras que en el código dinámico anterior necesita sólo unas 89 instrucciones (un ahorro del 56% aproximadamente). Si el array consistiera de tan sólo 2 entradas, aún se ejecutaría en aproximadamente el mismo tiempo que el bucle sin desenroscar. El incremento del código es de tan sólo unos 108 bytes (incluso con miles de entradas en el array). Pueden usarse técnicas similares cuando intervienen múltiples instrucciones, siempre y cuando la longitud del conjunto de instrucciones se ajuste. Por ejemplo, en este ejemplo, si se necesita borrar el resto del array (asignando un valor nulo) después de haber copiado los 100 bytes, se puede añadir una instrucción de borrado XC xx*256+100(156,R1),xx*256+100(R2) inmediatamente después de cada MVC en la secuencia (entendiendo que xx coincide con el valor anterior en el MVC). También es perfectamente posible generar el código anterior 'en línea' usando una macro de ensamblador, especificando 4 o 5 operadores (u otra alternativa, crear una subrutina, que se accedería con una simple llamada, pasando una lista de parámetros), haciendo que la optimización quede accesible a programadores poco experimentados.

Ejemplo en C

[editar]

El siguiente ejemplo muestra un desenroscado dinámico de bucle para un programa escrito en C. A diferencia del ejemplo anterior en ensamblador, la aritmética de punteros se genera por el compilador porque la variable indice se usa para indexar los elementos del array. La optimización más completa sólo es posible cuando se usan índices absolutos. 

#include<stdio.h>

#define BLOQUE (8)

int main()
{ 
  int indice = 0; 
  int elementos = 50;                     // Numero a procesar.
  int iteraciones = (elementos / BLOQUE); // Cantidad de iteraciones.
  int resto = (elementos % BLOQUE);       // Resto (a procesar posteriormente).

  /* Si la cantidad de elementos no es divisible por BLOQUE
     calcula los elementos restantes a procesar */

  // Desenrosca el bucle en 'bloques' de 8 elementos
  while (iteraciones-- > 0) 
  { 
    printf("procesando(%d)\n", indice    );
    printf("procesando(%d)\n", indice + 1); 
    printf("procesando(%d)\n", indice + 2); 
    printf("procesando(%d)\n", indice + 3); 
    printf("procesando(%d)\n", indice + 4); 
    printf("procesando(%d)\n", indice + 5); 
    printf("procesando(%d)\n", indice + 6); 
    printf("procesando(%d)\n", indice + 7);

    // Actualiza el indice con los elementos procesados en la iteracion.
    indice += BLOQUE; 
  }

  /* Se usa una instruccion switch para procesar el resto no divisible por BLOQUE
     saltando a la etiqueta case que procesara en cascada el resto de casos para
     completar la operacion (Dispositivo de Duff). */
  switch (resto) 
  {
    case 7 : printf("process(%d)\n", indice + 6);
    case 6 : printf("process(%d)\n", indice + 5);
    case 5 : printf("process(%d)\n", indice + 4);
    case 4 : printf("process(%d)\n", indice + 3);
    case 3 : printf("process(%d)\n", indice + 2);
    case 2 : printf("process(%d)\n", indice + 1);
    case 1 : printf("process(%d)\n", indice    );
    case 0 :                                    ;
  }
  return 0;
}

Véase también

[editar]

Referencias

[editar]
  1. ↑ Ullman, Jeffrey D.; Aho, Alfred V. (1977). Principios de diseño de compiladores. Reading, Mass: Addison-Wesley Pub. Co. pp. 471–2. ISBN 0-201-10073-8. 
  2. ↑ Petersen, W.P., Arbenz, P. (2004). Introducción a la computación paralela. Oxford University Press. p. 10. 
  3. ↑ Nicolau, Alexandru (1985). Loop Quantization: Desenroscar para la explotación del Paralelismo a bajo nivel. Dept. of Computer Science Technical Report. Ithaca, NY: Cornell University. OCLC 14638257. 
  4. ↑ Fog, Agner (29 de febrero de 2012). «Optimizando subrutinas en lenguaje ensamblador». Copenhagen University College of Engineering. p. 100. Consultado el 22 de septiembre de 2012. «12.11 Loop unrolling». 
  5. ↑ Sarkar, Vivek (2001). «Desenroscado eficiente de bucles anidados». International Journal of Parallel Programming 29 (5): 545-581. doi:10.1023/A:1012246031671. 
  6. ↑ Adam Horvath "Code unwinding - performance is far away"

Lectura adicional

[editar]
  • Kennedy, Ken; Allen, Randy (2001). Optimizando los compiladores para arquitecturas modernas: Una aproximación basada en dependencias. Morgan Kaufmann. ISBN 1-55860-286-0. 

Enlaces externos

[editar]
Obtenido de «https://es.wikipedia.org/eswiki/w/index.php?title=Desenroscado_de_bucles&oldid=161551881»