En informática , la canalización de software es una técnica que se utiliza para optimizar los bucles , de forma paralela a la canalización de hardware . La canalización de software es un tipo de ejecución desordenada , excepto que la reordenación la realiza un compilador (o en el caso de código ensamblador escrito a mano , el programador) en lugar del procesador . Algunas arquitecturas de computadora tienen un apoyo explícito a la segmentación software, en particular Intel 's IA-64 arquitectura.
Es importante distinguir la canalización de software , que es una técnica de código de destino para iteraciones de bucle superpuesto, de la programación de módulo , la técnica de compilación conocida más eficaz actualmente para generar bucles de canalización de software. La canalización de software ha sido conocida por los programadores de lenguaje ensamblador de máquinas con paralelismo a nivel de instrucción desde que existieron tales arquitecturas. La generación efectiva del compilador de dicho código data de la invención de la programación modular por Rau y Glaeser. [1] Lam demostró que no se necesita hardware especial para una programación de módulo eficaz. Su técnica, la expansión de módulo variable, se utiliza ampliamente en la práctica. [2]Gao y col. Formuló la canalización de software óptima en la programación lineal de enteros, que culminó con la validación de heurísticas avanzadas en un documento de evaluación. [3] Este artículo tiene un buen conjunto de referencias sobre el tema.
Ejemplo
Considere el siguiente ciclo:
para i = 1 a bignumber Ai) Bi) C (i)final
En este ejemplo, vamos A(i)
, B(i)
, C(i)
sea instrucciones, cada operación en los datos i
, que son dependientes entre sí. En otras palabras, A(i)
debe completarse antes de B(i)
poder comenzar. Por ejemplo, A
podría cargar datos de la memoria en un registro , B
podría realizar alguna operación aritmética en los datos y C
podría almacenar los datos nuevamente en la memoria. Sin embargo, que no haya dependencia entre operaciones para diferentes valores de i
. En otras palabras, A(2)
puede comenzar antes de que A(1)
termine.
Sin la canalización de software, las operaciones se ejecutan en la siguiente secuencia:
A (1) B (1) C (1) A (2) B (2) C (2) A (3) B (3) C (3) ...
Suponga que cada instrucción tarda 3 ciclos de reloj en completarse (ignore por el momento el costo del flujo de control de bucle). Suponga también (como es el caso en la mayoría de los sistemas modernos) que una instrucción se puede enviar en cada ciclo, siempre que no tenga dependencias de una instrucción que ya se esté ejecutando. En el caso no canalizado , cada iteración toma 9 ciclos para completarse: 3 ciclos de reloj para A(1)
, 3 ciclos de reloj para B(1)
y 3 ciclos de reloj para C(1)
.
Ahora considere la siguiente secuencia de instrucciones con la canalización de software :
A (1) A (2) A (3) B (1) B (2) B (3) C (1) C (2) C (3) ...
Se puede verificar fácilmente que se puede enviar una instrucción en cada ciclo, lo que significa que las mismas 3 iteraciones se pueden ejecutar en un total de 9 ciclos, dando un promedio de 3 ciclos por iteración.
Implementación
La canalización de software se usa a menudo en combinación con el desenrollado de bucles , y esta combinación de técnicas suele ser una optimización mucho mejor que el desenrollado de bucles solo. En el ejemplo anterior, podríamos escribir el código de la siguiente manera (supongamos por el momento que bignumber
es divisible por 3):
para i = 1 a (bignumber - 2) paso 3 Ai) A (i + 1) A (i + 2) Bi) B (yo + 1) B (i + 2) C (i) C (yo + 1) C (i + 2)final
Por supuesto, las cosas se complican si (como suele ser el caso) no podemos garantizar que el número total de iteraciones sea divisible por el número de iteraciones que desenrollamos. Consulte el artículo sobre desenrollado de bucles para obtener más información sobre las soluciones a este problema, pero tenga en cuenta que la canalización de software impide el uso del dispositivo de Duff . [ cita requerida ]
En el caso general, el desenrollado de bucles puede no ser la mejor manera de implementar la canalización de software. Considere un ciclo que contiene instrucciones con una latencia alta . Por ejemplo, el siguiente código:
para i = 1 a bignumber A (i); Latencia de 3 ciclos B (i); 3 C (i); 12 (quizás una operación de punto flotante) D (i); 3 E (i); 3 F (i); 3final
requeriría que se desenrollaran 12 iteraciones del ciclo para evitar el cuello de botella de la instrucción C
. Esto significa que el código del bucle aumentaría en un factor de 12 (lo que no solo afecta el uso de la memoria, sino que también puede afectar el rendimiento de la caché , consulte el código hinchado ). Peor aún, el prólogo (código antes del ciclo para manejar el caso de bignumber
no divisible por 12) probablemente será incluso más grande que el código del ciclo, y muy probablemente ineficiente porque la canalización de software no se puede usar en este código (al menos no sin una cantidad significativa de código adicional hinchado). Además, si bignumber
se espera que sea de tamaño moderado en comparación con el número de iteraciones desenrolladas (digamos 10-20), entonces la ejecución pasará la mayor parte de su tiempo en este código de prólogo ineficiente, haciendo que la optimización de la canalización del software sea ineficaz.
Por el contrario, aquí está la canalización de software para nuestro ejemplo (el prólogo y el epílogo se explicarán más adelante):
prólogopara i = 1 a (bignumber - 6) A (i + 6) B (i + 5) C (i + 4) D (i + 2); tenga en cuenta que nos saltamos i + 3 E (i + 1) F (i)finalepílogo
Antes de llegar al prólogo y al epílogo, que manejan las iteraciones al principio y al final del ciclo, verifiquemos que este código hace lo mismo que el original para las iteraciones en el medio del ciclo. Específicamente, considere la iteración 7 en el ciclo original. La primera iteración del bucle canalizado será la primera iteración que incluye una instrucción de la iteración 7 del bucle original. La secuencia de instrucciones es:
- Iteración 1:
A(7) B(6) C(5) D(3) E(2) F(1)
- Iteración 2:
A(8) B(7) C(6) D(4) E(3) F(2)
- Iteración 3:
A(9) B(8) C(7) D(5) E(4) F(3)
- Iteración 4:
A(10) B(9) C(8) D(6) E(5) F(4)
- Iteración 5:
A(11) B(10) C(9) D(7) E(6) F(5)
- Iteración 6:
A(12) B(11) C(10) D(8) E(7) F(6)
- Iteración 7:
A(13) B(12) C(11) D(9) E(8) F(7)
Sin embargo, a diferencia del bucle original, la versión canalizada evita el cuello de botella en la instrucción C
. Tenga en cuenta que hay 12 instrucciones entre C(7)
y la instrucción dependiente D(7)
, lo que significa que los ciclos de latencia de instrucción C(7)
se utilizan para otras instrucciones en lugar de desperdiciarse.
El prólogo y el epílogo manejan iteraciones al principio y al final del ciclo. Aquí hay un posible prólogo para nuestro ejemplo anterior:
; prólogo de bucle (organizado en líneas para mayor claridad)A (1)A (2), B (1)A (3), B (2), C (1)A (4), B (3), C (2); no se puede iniciar D (1) todavíaA (5), B (4), C (3), D (1)A (6), B (5), C (4), D (2), E (1)
Cada línea anterior corresponde a una iteración del bucle canalizado principal, pero sin las instrucciones para las iteraciones que aún no han comenzado. Del mismo modo, el epílogo elimina progresivamente las instrucciones para las iteraciones que se han completado:
; epílogo de bucle (organizado en líneas para mayor claridad)B (número bign-1), C (número bign-1), D (número bign-3), E (número bign-4), F (número bign-5)C (número bign), D (número bign-2), E (número bign-3), F (número bign-4)D (número bign-1), E (número bign-2), F (número bign-3)D (número bign), E (número bign-1), F (número bign-2)E (número bign), F (número bign-1)F (número bign)
Dificultades de implementación
El requisito de un prólogo y un epílogo es una de las mayores dificultades de implementar la canalización de software. Tenga en cuenta que el prólogo de este ejemplo tiene 18 instrucciones, 3 veces más grande que el bucle en sí. El epílogo también sería de 18 instrucciones. En otras palabras, el prólogo y el epílogo juntos son 6 veces más grandes que el bucle mismo . Aunque sigue siendo mejor que intentar desenrollar el bucle para este ejemplo, la canalización de software requiere un compromiso entre la velocidad y el uso de la memoria. Tenga en cuenta, también, que si el código es demasiado grande, afectará la velocidad de todos modos a través de una disminución en el rendimiento de la caché.
Una dificultad adicional es que en muchas arquitecturas, la mayoría de las instrucciones usan un registro como argumento y que el registro específico que se va a usar debe estar codificado en la instrucción. En otras palabras, en muchas arquitecturas, es imposible codificar una instrucción como "multiplicar el contenido del registro X
y registrar Y
y poner el resultado en el registro Z
", donde X
, Y
y Z
son números tomados de otros registros o memoria. Esto se ha citado a menudo como una razón por la que la canalización de software no se puede implementar de manera efectiva en arquitecturas convencionales.
De hecho, Monica Lam presenta una elegante solución a este problema en su tesis, A Systolic Array Optimizing Compiler (1989) ( ISBN 0-89838-300-5 ). Ella lo llama expansión módulo variable . El truco consiste en replicar el cuerpo del bucle después de que se haya programado, permitiendo que se usen diferentes registros para diferentes valores de la misma variable cuando tienen que estar activos al mismo tiempo. Para el ejemplo más simple posible, supongamos que A(i)
y B(i)
se pueden emitir en paralelo y que la latencia del primero es de 2 ciclos. El cuerpo canalizado podría ser:
A (i + 2); Bi)
La asignación de registros de este cuerpo de bucle se encuentra con el problema de que el resultado A(i+2)
debe permanecer activo durante dos iteraciones. El uso del mismo registro para el resultado de A(i+2)
y la entrada de B(i)
dará como resultado resultados incorrectos.
Sin embargo, si replicamos el cuerpo del ciclo programado, el problema está resuelto:
A (i + 2); Bi) A (i + 3); B (yo + 1)
Ahora se puede asignar un registro separado a los resultados de A(i+2)
y A(i+3)
. Para ser más concreto:
r1 = A (i + 2); B (i) = r1 r2 = A (i + 3); B (yo + 1) = r2 i = i + 2 // Solo para ser claros
Suponiendo que cada paquete de instrucciones lee sus registros de entrada antes de escribir sus registros de salida, este código es correcto. Al comienzo del cuerpo del bucle replicado, r1
contiene el valor de A(i+2)
de la iteración del bucle replicado anterior. Dado que i
se ha incrementado en 2 mientras tanto, este es en realidad el valor de A(i)
en esta iteración de bucle replicado.
Por supuesto, la replicación de código aumenta el tamaño del código y la presión de la caché al igual que lo hacen el prólogo y el epílogo. Sin embargo, para los bucles con un recorrido grande que cuenta con arquitecturas con suficiente paralelismo en el nivel de instrucción, la técnica se desempeña fácilmente lo suficientemente bien como para que valga la pena cualquier aumento en el tamaño del código.
Implementación IA-64
La arquitectura IA-64 de Intel proporciona un ejemplo de una arquitectura diseñada teniendo en cuenta las dificultades de la canalización de software. Parte del soporte arquitectónico para la canalización de software incluye:
- Un banco de registros "rotativo"; las instrucciones pueden referirse a un número de registro que se redirige a un registro diferente en cada iteración del ciclo (eventualmente regresando al principio). Esto hace que las instrucciones adicionales [ especificar ] insertadas en el ejemplo anterior sean innecesarias.
- Predicados (utilizados para "predicar" instrucciones; consulte Predicación de rama ) que toman su valor de instrucciones de bucle especiales. Estos predicados activan o desactivan determinadas instrucciones en el bucle, lo que hace innecesario un prólogo y un epílogo separados.
Referencias
- ^ BR Rau y CD Glaeser, "Algunas técnicas de programación y una arquitectura horizontal fácilmente programable para la informática científica de alto rendimiento", en las actas del decimocuarto taller anual sobre microprogramación (MICRO-14), diciembre de 1981, páginas 183-198
- ^ M. Lam, "Software pipelining: Una técnica de programación eficaz para máquinas VLIW", en las actas de la Conferencia ACM SIGPLAN 88 sobre diseño e implementación de lenguajes de programación (PLDI 88) , julio de 1988 páginas 318-328. También publicado como ACM SIGPLAN Notices 23 (7).
- ^ J. Ruttenberg, GR Gao, A. Stoutchinin y W. Lichtenstein, "Enfrentamiento de canalización de software: métodos óptimos frente a métodos heurísticos en un compilador de producción", en Actas de la Conferencia ACM SIGPLAN 1996 sobre diseño e implementación de lenguajes de programación, junio de 1996 , páginas 1-11. También publicado como ACM SIGPLAN Notices 31 (5).