El desenrollado de bucles , también conocido como desenrollado de bucles , es una técnica de transformación de bucles que intenta optimizar la velocidad de ejecución de un programa a expensas de su tamaño binario , lo cual es un enfoque conocido como compensación de espacio-tiempo . La transformación puede ser realizada manualmente por el programador o por un compilador de optimización . En los procesadores modernos, el desarrollo del bucle suele ser contraproducente, ya que el aumento del tamaño del código puede provocar más errores de caché; cf. El dispositivo de Duff . [1]
El objetivo del desenrollado del bucle es aumentar la velocidad de un programa reduciendo o eliminando las instrucciones que controlan el bucle, como la aritmética de punteros y las pruebas de "fin de bucle" en cada iteración; [2] reducir las sanciones a las sucursales; así como ocultar latencias, incluido el retraso en la lectura de datos de la memoria. [3] Para eliminar esta sobrecarga computacional , los bucles se pueden reescribir como una secuencia repetida de declaraciones independientes similares. [4]
El desenrollado de bucles también forma parte de ciertas técnicas de verificación formal , en particular la verificación de modelos acotados . [5]
La sobrecarga en los bucles "estrechos" a menudo consiste en instrucciones para incrementar un puntero o índice al siguiente elemento de una matriz ( aritmética de punteros ), así como pruebas de "fin de bucle". Si un compilador o ensamblador de optimización puede precalcular compensaciones para cada variable de matriz a la que se hace referencia individualmente , estas pueden integrarse directamente en las instrucciones del código de máquina , por lo que no requieren operaciones aritméticas adicionales en tiempo de ejecución.
Los compiladores de optimización a veces realizarán el desenvolvimiento automáticamente o previa solicitud.
El desenrollado manual (o estático) del bucle implica que el programador analice el bucle e interprete las iteraciones en una secuencia de instrucciones que reducirán la sobrecarga del bucle. Esto contrasta con el desenrollado dinámico que realiza el compilador.
Un procedimiento en un programa de computadora consiste en eliminar 100 elementos de una colección. Esto normalmente se logra mediante un forbucle que llama a la función eliminar(número_artículo) . Si se va a optimizar esta parte del programa y la sobrecarga del bucle requiere recursos significativos en comparación con los de la función eliminar (x) , se puede utilizar el desenrollado para acelerarlo.
Como resultado de esta modificación, el nuevo programa tiene que realizar sólo 20 iteraciones, en lugar de 100. Después, sólo es necesario realizar el 20% de los saltos y ramas condicionales, y representa, tras muchas iteraciones, una disminución potencialmente significativa en el sobrecarga de administración del bucle. Para producir el beneficio óptimo, no se deben especificar variables en el código desenrollado que requieran aritmética de punteros . Esto generalmente requiere un direccionamiento " base más desplazamiento", en lugar de referencias indexadas.
Por otro lado, este desarrollo manual del bucle expande el tamaño del código fuente de 3 líneas a 7, que deben producirse, verificarse y depurarse, y es posible que el compilador tenga que asignar más registros para almacenar variables en la iteración del bucle expandido [ dudoso ] . Además, las variables de control del bucle y el número de operaciones dentro de la estructura del bucle desenrollado deben elegirse cuidadosamente para que el resultado sea realmente el mismo que en el código original (suponiendo que se trate de una optimización posterior del código que ya funciona). Por ejemplo, considere las implicaciones si el recuento de iteraciones no fuera divisible por 5. Las modificaciones manuales requeridas también se vuelven algo más complicadas si las condiciones de la prueba son variables. Véase también Dispositivo de Duff .
En el caso simple, el control del bucle es simplemente una sobrecarga administrativa que organiza las declaraciones productivas. El bucle en sí no contribuye en nada a los resultados deseados, simplemente le ahorra al programador el tedio de replicar el código cien veces, lo que podría haberlo hecho un preprocesador que genera las replicaciones o un editor de texto. De manera similar, iflas declaraciones - y otras declaraciones de control de flujo podrían reemplazarse por replicación de código, excepto que el resultado puede ser un exceso de código . Los programas de computadora rastrean fácilmente las combinaciones, pero los programadores encuentran esta repetición aburrida y cometen errores. Considerar:
Pero, por supuesto, el código ejecutado no tiene por qué ser la invocación de un procedimiento, y el siguiente ejemplo involucra la variable de índice en el cálculo:
que, si se compila, podría producir una gran cantidad de código ( las declaraciones impresas son notorias), pero es posible una mayor optimización. Este ejemplo hace referencia sólo a x(i) y x(i - 1) en el bucle (este último sólo para desarrollar el nuevo valor x(i) ), por lo tanto, dado que no hay ninguna referencia posterior a la matriz x desarrollada aquí, sus usos podrían reemplazarse por una variable simple. Sin embargo, tal cambio significaría una variable simple cuyo valor se cambia, mientras que si se permanece con la matriz, el análisis del compilador podría notar que los valores de la matriz son constantes, cada uno derivado de una constante anterior y, por lo tanto, traslada los valores constantes para que el código se convierte
imprimir 2, 2;imprimir 3, 6;imprimir 4, 24;...etc.
En general, el contenido de un bucle puede ser grande e implicar una intrincada indexación de matrices. Probablemente sea mejor dejar estos casos en manos de los compiladores optimizadores para su desarrollo. La replicación de los bucles más internos podría permitir muchas optimizaciones posibles y, sin embargo, producir sólo una pequeña ganancia a menos que n sea grande.
Considere un pseudocódigo WHILE bucle similar al siguiente:
En este caso, el desenrollado es más rápido porque ENDWHILE (un salto al inicio del bucle) se ejecutará un 66% menos a menudo.
Aún mejor, el ejemplo de pseudocódigo "modificado", que algunos compiladores de optimización pueden realizar automáticamente, eliminando por completo los saltos incondicionales.
Dado que los beneficios del desenrollado de bucles dependen con frecuencia del tamaño de una matriz (que a menudo puede no conocerse hasta el momento de la ejecución), los compiladores JIT (por ejemplo) pueden determinar si invocar una secuencia de bucle "estándar" o, en su lugar, generar una secuencia (relativamente corta). ) secuencia de instrucciones individuales para cada elemento. Esta flexibilidad es una de las ventajas de las técnicas justo a tiempo frente a la optimización estática o manual en el contexto del desarrollo de bucles. En esta situación, a menudo es con valores relativamente pequeños de n donde los ahorros siguen siendo útiles, lo que requiere un aumento general bastante pequeño (si es que hay alguno) en el tamaño del programa (que podría incluirse sólo una vez, como parte de una biblioteca estándar).
Los programadores en lenguaje ensamblador (incluidos los escritores de compiladores optimizadores) también pueden beneficiarse de la técnica de desenrollado de bucles dinámicos, utilizando un método similar al utilizado para tablas de bifurcación eficientes . Aquí, la ventaja es mayor cuando el desplazamiento máximo de cualquier campo al que se hace referencia en una matriz particular es menor que el desplazamiento máximo que se puede especificar en una instrucción de máquina (que será marcado por el ensamblador si se excede).
Este ejemplo es para ensambladores IBM/360 o Z/Architecture y supone que se copiará un campo de 100 bytes (en el desplazamiento cero) de la matriz FROM a la matriz TO ; ambas tienen 50 entradas con longitudes de elemento de 256 bytes cada una.
*La dirección del remitente está en R14.* Inicialice los registros R15, R0, R1 y R2 a partir de los datos definidos al final de * el programa que comienza con la etiqueta INIT/MAXM1. LM R15,R2,INIT Establecer R15 = número máximo de MVC* instrucciones (MAXM1 = 16), * R0 = número de entradas de la matriz,* R1 = dirección de la matriz 'DESDE', y* R2 = dirección de la matriz 'TO'.** El bucle comienza aquí.LOOP EQU * Definir etiqueta LOOP.* En este punto, R15 siempre contendrá el número 16 (MAXM1). SR R15,R0 Resta el número restante de * entradas en la matriz (R0) de R15. BNP TODOS Si R15 no es positivo, significa que* tener más de 16 entradas restantes* en la matriz, salta para hacer todo* Secuencia MVC y luego repetir.** Calcular un desplazamiento (desde el inicio de la secuencia MVC) para la rama incondicional a * el bucle MVC 'desenrollado' a continuación.* Si el número de entradas restantes en las matrices es cero, R15 será 16, por lo que * Se omitirán todas las instrucciones MVC. MH R15,=AL2(ILEN) Multiplicar R15 por la longitud de uno* Instrucción MVC. B ALL(R15) Salta a ALL+R15, la dirección del* instrucción MVC específica calculada * con acceso directo al resto de ellos.** 'tabla' de instrucciones MVC. * La primera entrada tiene el desplazamiento máximo permitido con un solo registro = hexadecimal F00* (15*256) en este ejemplo.* Las 16 siguientes instrucciones MVC ('mover carácter') utilizan base más desplazamiento * el direccionamiento y cada desplazamiento hacia/desde disminuye en la longitud de un elemento de la matriz* (256). Esto evita que se requiera aritmética de punteros para cada elemento hasta un * desplazamiento máximo permitido dentro de la instrucción de FFF hexadecimal * (15*256+255). Las instrucciones están en orden de compensación decreciente, por lo que la última * el elemento del conjunto se mueve primero.TODOS MVC 15*256(100,R2),15*256(R1) Mover 100 bytes de la entrada 16 de * matriz 1 a matriz 2 (con * caer a través).ILEN EQU *-ALL Establece ILEN en la duración del anterior* Instrucción MVC. MVC 14*256(100,R2),14*256(R1) Mueve 100 bytes de la decimoquinta entrada. MVC 13*256(100,R2),13*256(R1) Mueve 100 bytes de la 14.ª entrada. MVC 12*256(100,R2),12*256(R1) Mueve 100 bytes de la decimotercera entrada. MVC 11*256(100,R2),11*256(R1) Mueve 100 bytes de la 12.ª entrada. MVC 10*256(100,R2),10*256(R1) Mueve 100 bytes de la undécima entrada. MVC 09*256(100,R2),09*256(R1) Mueve 100 bytes de la décima entrada. MVC 08*256(100,R2),08*256(R1) Mueve 100 bytes de la novena entrada. MVC 07*256(100,R2),07*256(R1) Mueve 100 bytes de la octava entrada. MVC 06*256(100,R2),06*256(R1) Mueve 100 bytes de la séptima entrada. MVC 05*256(100,R2),05*256(R1) Mueve 100 bytes de la sexta entrada. MVC 04*256(100,R2),04*256(R1) Mueve 100 bytes de la quinta entrada. MVC 03*256(100,R2),03*256(R1) Mueve 100 bytes de la cuarta entrada. MVC 02*256(100,R2),02*256(R1) Mueve 100 bytes de la tercera entrada. MVC 01*256(100,R2),01*256(R1) Mueve 100 bytes de la segunda entrada. MVC 00*256(100,R2),00*256(R1) Mueve 100 bytes de la primera entrada.* S R0,MAXM1 Reducir el número de entradas restantes* para procesar. BNPR R14 Si no hay más entradas para procesar, devolver*a la dirección en R14. AH R1,=AL2(16*256) Incrementar el puntero de matriz 'DESDE' más allá* primer set. AH R2,=AL2(16*256) Incrementar el puntero de la matriz 'TO' más allá* primer set. L R15,MAXM1 Recarga el número máximo de MVC * instrucciones por lote en R15* (destruido por el cálculo en el * primera instrucción del bucle). B LOOP Ejecutar el bucle nuevamente.** Constantes y variables estáticas (éstas podrían pasarse como parámetros, excepto * MAXM1).INIT DS 0A 4 direcciones (punteros) a ser * precargado con la instrucción 'LM'*al inicio del programa.MAXM1 DC A(16) Número máximo de instrucciones MVC* ejecutado por lote.N DC A(50) Número de entradas reales en la matriz (a * variable, establecida en otro lugar). DC A(FROM) Dirección de inicio de la matriz 1 * ("puntero"). DC A(TO) Dirección de inicio de la matriz 2 * ("puntero").** Arreglos estáticos (estos podrían adquirirse dinámicamente).DE DS 50CL256 Matriz de 50 entradas de 256 bytes cada una.TO DS 50CL256 Matriz de 50 entradas de 256 bytes cada una.En este ejemplo, se necesitarían aproximadamente 202 instrucciones con un bucle "convencional" (50 iteraciones), mientras que el código dinámico anterior requeriría sólo unas 89 instrucciones (o un ahorro de aproximadamente el 56%). Si la matriz hubiera consistido solo en dos entradas, todavía se ejecutaría aproximadamente al mismo tiempo que el bucle desenrollado original. El aumento en el tamaño del código es sólo de unos 108 bytes, incluso si hay miles de entradas en la matriz.
Por supuesto, se pueden utilizar técnicas similares cuando intervienen varias instrucciones, siempre que la longitud combinada de las instrucciones se ajuste en consecuencia. Por ejemplo, en este mismo ejemplo, si es necesario borrar el resto de cada entrada de la matriz a valores nulos inmediatamente después de copiar el campo de 100 bytes, se XC xx*256+100(156,R1),xx*256+100(R2)puede agregar una instrucción de borrado adicional, inmediatamente después de cada MVC en la secuencia (donde xxcoincide con el valor en el MVC encima de él).
Por supuesto, es perfectamente posible generar el código anterior "en línea" utilizando una única macro declaración en ensamblador, especificando sólo cuatro o cinco operandos (o alternativamente, convertirlo en una subrutina de biblioteca, a la que se accede mediante una simple llamada, pasando una lista de parámetros), haciendo que la optimización sea fácilmente accesible.
El siguiente ejemplo demuestra el desarrollo de un bucle dinámico para un programa simple escrito en C. A diferencia del ejemplo de ensamblador anterior, en este ejemplo el compilador todavía genera la aritmética de puntero/índice porque todavía se usa una variable (i) para direccionar el elemento de la matriz. La optimización completa sólo es posible si se utilizan índices absolutos en las declaraciones de reemplazo.
#incluir <stdio.h> /* El número de entradas procesadas por iteración del bucle. */ /* Tenga en cuenta que este número es una "constante constante" que refleja el código siguiente. */ #define BUNCHSIZE (8)int principal ( vacío ) { int i = 0 ; /* contador */ int entradas = 50 ; /* número total a procesar */ int repetir ; /* número de repeticiones while*/ int left = 0 ; /* resto (procesar más tarde) */ /* Si el número de elementos no es divisible por BUNCHSIZE, */ /* obtiene los tiempos de repetición necesarios para realizar la mayor parte del procesamiento en el bucle while */ repetir = ( entradas / BUNCHSIZE ); /* número de veces para repetir */ left = ( entradas % BUNCHSIZE ); /* calcular el resto */ /* Desenrolla el bucle en 'racimos' de 8 */ while ( repetir -- ) { printf ( "proceso(%d) \n " , i ); printf ( "proceso(%d) \n " , i + 1 ); printf ( "proceso(%d) \n " , i + 2 ); printf ( "proceso(%d) \n " , i + 3 ); printf ( "proceso(%d) \n " , i + 4 ); printf ( "proceso(%d) \n " , i + 5 ); printf ( "proceso(%d) \n " , i + 6 ); printf ( "proceso(%d) \n " , i + 7 ); /* actualiza el índice por cantidad procesada de una sola vez */ i += BUNCHSIZE ; } /* Utilice una instrucción de cambio para procesar el resto saltando a la etiqueta del caso */ /* en la etiqueta que luego pasará para completar el conjunto */ switch ( left ) { case 7 : printf ( "process(%d) \ norte " , yo + 6 ); /* procesar y confiar en el drop- through */ caso 6 : printf ( "proceso(%d) \n " , i + 5 ); caso 5 : printf ( "proceso(%d) \n " , i + 4 ); caso 4 : printf ( "proceso(%d) \n " , i + 3 ); caso 3 : printf ( "proceso(%d) \n " , i + 2 ); caso 2 : printf ( "proceso(%d) \n " , i + 1 ); /* quedan dos */ caso 1 : printf ( "proceso(%d) \n " , i ); /* solo queda uno por procesar */ case 0 : ; /* nadie */ } } La duplicación de código podría evitarse escribiendo las dos partes juntas como en el dispositivo de Duff .
El siguiente ejemplo calculará un producto escalar de dos vectores A y B de 100 entradas de tipo double. Aquí está el código en C:
producto de punto doble = 0 ; para ( int yo = 0 ; yo < 100 ; yo ++ ) { Productopunto += A [ i ] * B [ i ]; }El siguiente es el código ensamblador MIPS que calculará el producto escalar de dos vectores de 100 entradas, A y B, antes de implementar el desenrollado del bucle. El siguiente código omite las inicializaciones del bucle:
A[i]el puntero ($5) a la dirección base de A.B[i]el puntero ($6) a la dirección base de B.Tenga en cuenta que el tamaño de un elemento de las matrices (a double) es de 8 bytes.
bucle3: ld $f10 , 0 ( $5 ) ; $f10 ← A[yo] ld $f12 , 0 ( $6 ) ; $f12 ← B[yo] mul.d $f10 , $f10 , $f12 ; $f10 ← A[i]*B[i] agregar.d $f8 , $f8 , $f10 ; $f8 ← $f8 + A[i]*B[i] agregar $5 , $5 , 8 ; puntero de incremento para A[i] por el tamaño ; de un doble. agregar $6 , $6 , 8 ; puntero de incremento para B[i] por el tamaño ; de un doble. agregar $7 , $7 , -1 ; recuento de bucles decrecientes prueba: bgtz $7 , bucle3 ; Continuar si el recuento de bucles > 0 Lo siguiente es igual que el anterior, pero con el desenrollado del bucle implementado en un factor de 4. Tenga en cuenta nuevamente que el tamaño de un elemento de las matrices (a double) es de 8 bytes; de ahí los 0, 8, 16, 24 desplazamientos y los 32 desplazamientos en cada bucle.
bucle3: ld $f10 , 0 ( $5 ) ; iteración con desplazamiento 0 ld $f12 , 0 ( $6 ) mul.d $f10 , $f10 , $f12 agregar.d $f8 , $f8 , $f10 ld $f10 , 8 ( $5 ) ; iteración con desplazamiento 8 ld $f12 , 8 ( $6 ) mul.d $f10 , $f10 , $f12 agregar.d $f8 , $f8 , $f10 ld $f10 , 16 ( $5 ) ; iteración con desplazamiento 16 ld $f12 , 16 ( $6 ) mul.d $f10 , $f10 , $f12 agregar.d $f8 , $f8 , $f10 ld $f10 , 24 ( $5 ) ; iteración con desplazamiento 24 ld $f12 , 24 ( $6 ) mul.d $f10 , $f10 , $f12 agregar.d $f8 , $f8 , $f10 agregar $5 , $5 , 32 añadir $6 , $6 , 32 agregar $7 , $7 , -4 prueba: bgtz $7 , bucle3 ; Continuar bucle si $7 > 0 Jim Gettys tiene una maravillosa explicación de este efecto en el servidor X. Resulta que con las predicciones de rama y la velocidad relativa de la CPU frente a la memoria cambiando durante la última década, el desarrollo del bucle es prácticamente inútil. De hecho, al eliminar todas las instancias del dispositivo de Duff del servidor XFree86 4.0, el tamaño del servidor se redujo a la mitad _un_ megabyte_ (!!!), y su arranque fue más rápido, porque la eliminación de todo ese exceso de código significó que el servidor X No estaba sacudiendo tanto las líneas de caché.
{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Citar diario requiere |journal=( ayuda )12.11 Desenrollado del bucle