En informática , la canalización de software es una técnica utilizada para optimizar bucles , de forma paralela a la canalización de hardware . La canalización de software es un tipo de ejecución fuera de orden , 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 informáticas tienen soporte explícito para la canalización de software, en particular la arquitectura IA-64 de Intel .
Es importante distinguir la canalización de software , que es una técnica de código objetivo para iteraciones de bucles superpuestos, de la programación módulo , la técnica de compilador conocida actualmente más eficaz para generar bucles canalizados 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 existían tales arquitecturas. La generación efectiva de compilador de dicho código data de la invención de la programación módulo por Rau y Glaeser. [1] Lam demostró que no es necesario un hardware especial para una programación módulo efectiva. Su técnica, la expansión de variable módulo , se usa ampliamente en la práctica. [2] Gao et al. formularon la canalización de software óptima en programación lineal entera, que culminó en la validación de heurísticas avanzadas en un artículo de evaluación. [3] Este artículo tiene un buen conjunto de referencias sobre el tema.
Consideremos el siguiente bucle:
para i = 1 a número grande Ai) Bi) C(yo)fin
En este ejemplo, sean A(i), B(i), C(i)instrucciones que operan sobre datos i, que dependen unas de otras. En otras palabras, A(i)deben completarse antes de B(i)poder comenzar. Por ejemplo, Apodrían cargar datos desde la memoria a un registro , Bpodrían realizar alguna operación aritmética sobre los datos y Cpodrían almacenar los datos nuevamente en la memoria. Sin embargo, sea que no haya dependencia entre operaciones para diferentes valores de i. En otras palabras, A(2)pueden comenzar antes de A(1)que termine.
Sin 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) ...
Supongamos que cada instrucción tarda 3 ciclos de reloj en completarse (ignoremos por el momento el costo del flujo de control en bucle). Supongamos también (como es el caso en la mayoría de los sistemas modernos) que se puede enviar una instrucción en cada ciclo, siempre que no tenga dependencias de una instrucción que ya se esté ejecutando. En el caso no segmentado , cada iteración tarda 9 ciclos en completarse: 3 ciclos de reloj para A(1), 3 ciclos de reloj para B(1)y 3 ciclos de reloj para C(1).
Consideremos ahora la siguiente secuencia de instrucciones con 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 se pueden ejecutar las mismas 3 iteraciones en un total de 9 ciclos, lo que da un promedio de 3 ciclos por iteración.
La segmentación de software se suele utilizar 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 por sí solo. En el ejemplo anterior, podríamos escribir el código de la siguiente manera (supongamos por el momento que bignumberes divisible por 3):
para i = 1 a (número grande - 2) paso 3 Ai) Una(i+1) A(i+2) Bi) B(i+1) B(i+2) C(yo) C(i+1) C(i+2)fin
Por supuesto, las cosas se complican si (como suele ser el caso) no podemos garantizar que el número total de iteraciones será 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 segmentación por software impide el uso del dispositivo de Duff . [ cita requerida ]
En general, la desenrollación de bucles puede no ser la mejor manera de implementar la segmentación de software. Considere un bucle que contenga instrucciones con una latencia alta . Por ejemplo, el siguiente código:
para i = 1 a número grande 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); 3fin
requeriría que se desenrollen 12 iteraciones del bucle 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 la hinchazón del código ). Peor aún, el prólogo (código antes del bucle para manejar el caso de bignumberno divisible por 12) probablemente será incluso más grande que el código para el bucle, 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 hinchazón de código adicional). Además, si bignumberse 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, lo que hará que la optimización de la canalización de software sea ineficaz.
En cambio, aquí está la canalización del software para nuestro ejemplo (el prólogo y el epílogo se explicarán más adelante):
prólogopara i = 1 a (número grande - 6) A(i+6) B(i+5) C(i+4) D(i+2) ; tenga en cuenta que omitimos i+3 E(i+1) F(yo)finepílogo
Antes de llegar al prólogo y al epílogo, que manejan las iteraciones al principio y al final del bucle, verifiquemos que este código hace lo mismo que el original para las iteraciones en el medio del bucle. Específicamente, considere la iteración 7 en el bucle original. La primera iteración del bucle segmentado será la primera iteración que incluya una instrucción de la iteración 7 del bucle original. La secuencia de instrucciones es:
A(7) B(6) C(5) D(3) E(2) F(1)A(8) B(7) C(6) D(4) E(3) F(2)A(9) B(8) C(7) D(5) E(4) F(3)A(10) B(9) C(8) D(6) E(5) F(4)A(11) B(10) C(9) D(7) E(6) F(5)A(12) B(11) C(10) D(8) E(7) F(6)A(13) B(12) C(11) D(9) E(8) F(7)Sin embargo, a diferencia del bucle original, la versión segmentada 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 la instrucción C(7)se utilizan para otras instrucciones en lugar de desperdiciarse.
El prólogo y el epílogo manejan las iteraciones al principio y al final del bucle. A continuación, se muestra un posible prólogo para nuestro ejemplo anterior:
; prólogo en 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); todavía no se puede iniciar D(1)A(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 principal segmentado, pero sin las instrucciones para las iteraciones que aún no han comenzado. De manera similar, el epílogo elimina progresivamente las instrucciones para las iteraciones que se han completado:
; epílogo en bucle (organizado en líneas para mayor claridad)B(número grande), C(número grande-1), D(número grande-3), E(número grande-4), F(número grande-5)C(número grande), D(número grande-2), E(número grande-3), F(número grande-4)D(número grande-1), E(número grande-2), F(número grande-3)D(número grande), E(número grande-1), F(número grande-2)E(número grande), F(número grande-1)F(número grande)
El requisito de un prólogo y un epílogo es una de las principales dificultades de la implementación de la segmentación de software. Tenga en cuenta que el prólogo en este ejemplo tiene 18 instrucciones, 3 veces más grande que el bucle en sí. El epílogo también tendría 18 instrucciones. En otras palabras, el prólogo y el epílogo juntos son 6 veces más grandes que el bucle en sí . Si bien sigue siendo mejor que intentar desenrollar el bucle para este ejemplo, la segmentación de software requiere un equilibrio entre la velocidad y el uso de memoria. Tenga en cuenta, también, que si la hinchazón del código es demasiado grande, afectará la velocidad de todos modos a través de una disminución en el rendimiento de la caché.
Otra dificultad es que en muchas arquitecturas, la mayoría de las instrucciones utilizan un registro como argumento, y el registro específico que se debe utilizar debe estar codificado en la instrucción. En otras palabras, en muchas arquitecturas, es imposible codificar una instrucción como "multiplicar el contenido de registro Xy registro Yy poner el resultado en registro Z", donde X, Yy Zson números tomados de otros registros o de la memoria. Esto se ha citado a menudo como una razón por la que la segmentación por software no se puede implementar de manera efectiva en arquitecturas convencionales.
De hecho, Monica Lam presenta una solución elegante a este problema en su tesis, A Systolic Array Optimizing Compiler (1989) ( ISBN 0-89838-300-5 ). Ella lo llama expansión de variable módulo . El truco es replicar el cuerpo del bucle después de que se haya programado, lo que permite que se utilicen 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 entonces:
A(i+2); B(i)
La asignación de registros de este cuerpo de bucle se enfrenta al problema de que el resultado de A(i+2)debe permanecer activo durante dos iteraciones. Si se utiliza el mismo registro para el resultado de A(i+2)y la entrada de, B(i)se obtendrán resultados incorrectos.
Sin embargo, si replicamos el cuerpo del bucle programado, el problema se resuelve:
A(i+2); B(i) A(i+3); B(i+1)
Ahora se puede asignar un registro independiente a los resultados de A(i+2)y A(i+3). Para ser más concretos:
r1 = A(i+2); B(i) = r1 r2 = A(i+3); B(i+1) = r2 i = i + 2 // Para que quede claro
Suponiendo que cada conjunto 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, r1contiene el valor de A(i+2)de la iteración del bucle replicado anterior. Dado que ise ha incrementado en 2 mientras tanto, este es en realidad el valor de A(i)en esta iteración del bucle replicado.
Por supuesto, la replicación de código aumenta el tamaño del código y la presión de la memoria caché, al igual que el prólogo y el epílogo. Sin embargo, en el caso de bucles con un gran número de recorridos en arquitecturas con suficiente paralelismo a nivel de instrucciones, la técnica funciona lo suficientemente bien como para que valga la pena cualquier aumento en el tamaño del código.
La arquitectura IA-64 de Intel ofrece un ejemplo de una arquitectura diseñada teniendo en cuenta las dificultades de la canalización de software. Algunas de las arquitecturas compatibles con la canalización de software incluyen: