El desenrollado de bucles , también conocido como loop unwinding , 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 que es un enfoque conocido como compensación espacio-tiempo . La transformación puede ser realizada manualmente por el programador o por un compilador optimizador . En los procesadores modernos, el desenrollado de bucles suele ser contraproducente, ya que el aumento del tamaño del código puede provocar más errores de caché; cf. Dispositivo de Duff . [1]
El objetivo del desenrollado de bucles es aumentar la velocidad de un programa reduciendo o eliminando instrucciones que controlan el bucle, como la aritmética de punteros y las pruebas de "fin de bucle" en cada iteración; [2] reduciendo las penalizaciones de bifurcación; así como ocultando 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 bucles "apretados" 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 optimizador puede calcular previamente los desplazamientos de cada variable de matriz referenciada individualmente , estos pueden incorporarse directamente en las instrucciones del código de máquina , por lo que no se requieren operaciones aritméticas adicionales en tiempo de ejecución.
Los compiladores optimizadores a veces realizarán el desenrollado automáticamente o bajo pedido.
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á la sobrecarga del bucle. Esto contrasta con el desenrollado dinámico que realiza el compilador.
Un procedimiento en un programa informático consiste en eliminar 100 elementos de una colección. Esto se lleva a cabo normalmente mediante un forbucle que llama a la función delete(item_number) . Si se desea optimizar esta parte del programa y la sobrecarga del bucle requiere recursos significativos en comparación con los de la función delete(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 se necesita realizar el 20% de los saltos y bifurcaciones condicionales, y representa, a lo largo de muchas iteraciones, una disminución potencialmente significativa en la 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 direccionamiento de " base más desplazamiento", en lugar de referencia indexada.
Por otra parte, este desenrollado manual del bucle expande el tamaño del código fuente de 3 a 7 líneas, que deben producirse, verificarse y depurarse, y el compilador puede tener que asignar más registros para almacenar variables en la iteración del bucle expandido [ dudoso – discutir ] . Además, las variables de control del bucle y el número de operaciones dentro de la estructura del bucle desenrollado deben elegirse con cuidado para que el resultado sea de hecho el mismo que en el código original (asumiendo que se trata de una optimización posterior en un 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 prueba son variables. Consulte también el dispositivo de Duff .
En el caso simple, el control de bucle es simplemente una sobrecarga administrativa que organiza las sentencias 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 haber hecho un preprocesador que generara las réplicas, o un editor de texto. De manera similar, iflas sentencias - y otras sentencias de control de flujo podrían reemplazarse por la 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 aburrida esta repetición y cometen errores. Considere lo siguiente:
Pero, por supuesto, el código ejecutado no necesita ser la invocación de un procedimiento, y el siguiente ejemplo involucra la variable de índice en el cálculo:
que, si se compila, puede producir mucho código ( las sentencias de impresión son notorias), pero es posible una mayor optimización. Este ejemplo hace referencia solo a x(i) y x(i - 1) en el bucle (este último solo para desarrollar el nuevo valor x(i) ); por lo tanto, dado que no hay una 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 mantiene 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 convierta en
impresión 2, 2;impresión 3, 6;impresión 4, 24;...etc.
En general, el contenido de un bucle puede ser grande e implicar una indexación de matriz compleja. Probablemente sea mejor dejar que los compiladores optimizadores se encarguen de estos casos. Replicar los bucles más internos puede permitir muchas optimizaciones posibles, pero producir solo una pequeña ganancia a menos que n sea grande.
Considere un bucle WHILE de pseudocódigo similar al siguiente:
En este caso, el desenrollado es más rápido porque ENDWHILE (un salto al inicio del bucle) se ejecutará con un 66% menos de frecuencia.
Mejor aún, el ejemplo de pseudocódigo "modificado", que puede ser realizado automáticamente por algunos compiladores optimizadores, eliminando por completo los saltos incondicionales.
Dado que los beneficios del desenrollado de bucles dependen frecuentemente del tamaño de una matriz (que a menudo no se conoce hasta el momento de la ejecución), los compiladores JIT (por ejemplo) pueden determinar si invocar una secuencia de bucles "estándar" o generar en su lugar una secuencia (relativamente corta) 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 desenrollado de bucles. En esta situación, es a menudo con valores relativamente pequeños de n donde los ahorros siguen siendo útiles, requiriendo un aumento general bastante pequeño (si es que hay alguno) en el tamaño del programa (que podría incluirse solo una vez, como parte de una biblioteca estándar).
Los programadores de lenguaje ensamblador (incluidos los escritores de compiladores optimizadores) también pueden beneficiarse de la técnica de desenrollado dinámico de bucles, utilizando un método similar al que se utiliza para las tablas de ramificación eficientes . Aquí, la ventaja es mayor cuando el desplazamiento máximo de cualquier campo referenciado en una matriz particular es menor que el desplazamiento máximo que se puede especificar en una instrucción de máquina (que será marcada por el ensamblador si se excede).
Este ejemplo es para ensambladores IBM/360 o Z/Architecture y supone que se debe copiar un campo de 100 bytes (en el desplazamiento cero) de la matriz FROM a la matriz TO (ambas con 50 entradas con longitudes de elementos de 256 bytes cada una).
*La dirección de devolución está en R14.* Inicializar 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 'FROM', y* R2 = dirección de la matriz 'TO'.**El bucle empieza aquí.LOOP EQU * Define la 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) desde R15. BNP ALL Si R15 no es positivo, es decir,* tienen 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) Multiplica R15 por la longitud de uno*Instrucción MVC. B ALL(R15) Salta a ALL+R15, la dirección de la* instrucción MVC específica calculada * con acceso directo al resto.** Instrucción MVC 'tabla'. * 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 personaje') utilizan base más desplazamiento * el direccionamiento y cada desplazamiento hacia/desde disminuyen 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 decreciente de desplazamiento, por lo que la última *El elemento del conjunto se mueve primero.ALL MVC 15*256(100,R2),15*256(R1) Mover 100 bytes de la entrada 16 desde * matriz 1 a matriz 2 (con * caída libre).ILEN EQU *-ALL Establece ILEN en la longitud del anterior*Instrucción MVC. MVC 14*256(100,R2),14*256(R1) Mueve 100 bytes de la entrada 15. MVC 13*256(100,R2),13*256(R1) Mover 100 bytes de la entrada 14. MVC 12*256(100,R2),12*256(R1) Mover 100 bytes de la entrada 13. MVC 11*256(100,R2),11*256(R1) Mover 100 bytes de la entrada 12. MVC 10*256(100,R2),10*256(R1) Mueve 100 bytes de la entrada 11. MVC 09*256(100,R2),09*256(R1) Mueve 100 bytes de la décima entrada. MVC 08*256(100,R2),08*256(R1) Mover 100 bytes de la novena entrada. MVC 07*256(100,R2),07*256(R1) Mover 100 bytes de la octava entrada. MVC 06*256(100,R2),06*256(R1) Mover 100 bytes de la 7ma entrada. MVC 05*256(100,R2),05*256(R1) Mover 100 bytes de la sexta entrada. MVC 04*256(100,R2),04*256(R1) Mover 100 bytes de la quinta entrada. MVC 03*256(100,R2),03*256(R1) Mover 100 bytes de la 4ta entrada. MVC 02*256(100,R2),02*256(R1) Mover 100 bytes de la tercera entrada. MVC 01*256(100,R2),01*256(R1) Mover 100 bytes de la 2.ª entrada. MVC 00*256(100,R2),00*256(R1) Mover 100 bytes de la primera entrada.* S R0,MAXM1 Reduce el número de entradas restantes* para procesar. BNPR R14 Si no hay más entradas para procesar, devuélvalas* para abordar en R14. AH R1,=AL2(16*256) Incrementa el puntero de la matriz 'FROM' más allá* primer conjunto. AH R2,=AL2(16*256) Incrementa el puntero de la matriz 'TO' más allá* primer conjunto. L R15,MAXM1 Recargar 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 bucle nuevamente.** Constantes y variables estáticas (estas 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").** Matrices estáticas (estas podrían adquirirse dinámicamente).DESDE 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 solo unas 89 instrucciones (o un ahorro de aproximadamente el 56%). Si la matriz hubiera consistido en solo dos entradas, se habría ejecutado en aproximadamente el mismo tiempo que el bucle desenrollado original. El aumento en el tamaño del código es de solo unos 108 bytes, incluso si hay miles de entradas en la matriz.
Por supuesto, se pueden utilizar técnicas similares cuando se utilizan varias instrucciones, siempre que la longitud de la instrucción combinada se ajuste en consecuencia. Por ejemplo, en este mismo ejemplo, si se requiere borrar el resto de cada entrada de la matriz a valores nulos inmediatamente después de copiar el campo de 100 bytes, XC xx*256+100(156,R1),xx*256+100(R2)se 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 que está por encima).
Por supuesto, es perfectamente posible generar el código anterior "en línea" usando una única declaración macro de 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 dinámico de un bucle para un programa simple escrito en C. A diferencia del ejemplo de ensamblador anterior, en este ejemplo el compilador aún genera la aritmética de punteros e índices porque aún se usa una variable (i) para direccionar el elemento de la matriz. La optimización completa solo es posible si se usan índices absolutos en las instrucciones 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 main ( void ) { int i = 0 ; /* contador */ int entradas = 50 ; /* número total a procesar */ int repeat ; /* número de repeticiones while*/ int left = 0 ; /* resto (procesar más tarde) */ /* Si el número de elementos no es divisible por BUNCHSIZE, */ /* obtener los tiempos de repetición necesarios para realizar la mayor parte del procesamiento en el bucle while */ repetir = ( entradas / BUNCHSIZE ); /* número de veces a repetir */ izquierda = ( entradas % BUNCHSIZE ); /* calcular resto */ /* Desenrolla el bucle en 'grupos' de 8 */ while ( repeat -- ) { 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 ; } /* Use una declaración switch para procesar lo restante saltando a la etiqueta del caso */ /* en la etiqueta que luego pasará para completar el conjunto */ switch ( left ) { case 7 : printf ( "process(%d) \n " , i + 6 ); /* procesar y confiar en el drop -through */ case 6 : printf ( "process(%d) \n " , i + 5 ); case 5 : printf ( "process(%d) \n " , i + 4 ); case 4 : printf ( "process(%d) \n " , i + 3 ); case 3 : printf ( "process(%d) \n " , i + 2 ); case 2 : printf ( "process(%d) \n " , i + 1 ); /* quedan dos */ case 1 : printf ( "process(%d) \n " , i ); /* solo queda uno para procesar */ case 0 : ; /*no queda ninguno*/ } } 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 de 100 entradas A y B de tipo double. Aquí está el código en C:
doble puntoProducto = 0 ; para ( int i = 0 ; i < 100 ; i ++ ) { puntoProducto += A [ i ] * B [ i ]; }El siguiente es un 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 código a continuación 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[i] ld $f12 , 0 ( $6 ) ; $f12 ← B[i] mul.d $f10 , $f10 , $f12 ; $f10 ← A[i]*B[i] añadir.d $f8 , $f8 , $f10 ; $f8 ← $f8 + A[i]*B[i] addi $5 , $5 , 8 ; incrementa el puntero para A[i] por el tamaño ;de un doble. addi $6 , $6 , 8 ; incrementa el puntero para B[i] por el tamaño ;de un doble. addi $7 , $7 , -1 ; decrementar el número de bucles prueba: bgtz $7 , loop3 ; Continuar si el número de bucles > 0 Lo siguiente es lo mismo que lo anterior, pero con el desenrollado de bucle implementado en un factor de 4. Observe nuevamente que el tamaño de un elemento de las matrices (a double) es de 8 bytes; de ahí los desplazamientos 0, 8, 16, 24 y el desplazamiento 32 en cada bucle.
bucle3: ld $f10 , 0 ( $5 ) ; iteración con desplazamiento 0 ld $f12 , 0 ( $6 ) función multívoca $f10 , $f10 , $f12 añadir.d $f8 , $f8 , $f10 ld $f10 , 8 ( $5 ) ; iteración con desplazamiento 8 $f12 , 8 ( $ 6 ) función multívoca $f10 , $f10 , $f12 añadir.d $f8 , $f8 , $f10 ld $f10 , 16 ( $5 ) ; iteración con desplazamiento 16 $f12 , 16 ( $ 6 ) función multívoca $f10 , $f10 , $f12 añadir.d $f8 , $f8 , $f10 ld $f10 , 24 ( $5 ) ; iteración con desplazamiento 24 $ 12,24 ( 6 dólares ) función multívoca $f10 , $f10 , $f12 añadir.d $f8 , $f8 , $f10 adicional $5 , $5 , 32 adicional $6 , $6 , 32 adicional $7 , $7 , -4 prueba: bgtz $7 , loop3 ; Continuar el bucle si $7 > 0 Jim Gettys tiene una explicación maravillosa de este efecto en el servidor X. Resulta que con las predicciones de bifurcación y la velocidad relativa de la CPU frente a la memoria cambiando durante la última década, el desenrollado de bucles es prácticamente inútil. De hecho, al eliminar todas las instancias del dispositivo de Duff del servidor XFree86 4.0, el servidor se redujo en tamaño en _medio_ _megabyte_ (!!!), y fue más rápido al arrancar, porque la eliminación de todo ese exceso de código significaba que el servidor X no estaba agotando tanto las líneas de caché.
{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: Requiere citar revista |journal=( ayuda )12.11 Desenrollado de bucles