Canalización de software

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 23 de mayo de 2016; las comprobaciones requieren 8 ediciones .

La canalización de bucles por software es una  técnica utilizada por los compiladores para optimizar los bucles , similar a la canalización computacional de los microprocesadores . Es una forma de ejecución fuera de orden , con la diferencia de que el reordenamiento no lo realiza el procesador, sino el compilador (o, en el caso de la optimización manual, el programador). Algunas arquitecturas informáticas, como Intel IA-64 [1] , tienen soporte de hardware explícito para simplificar la canalización de bucles de software.

Al canalizar un ciclo, en cada punto en el tiempo, hay un código en ejecución que se relaciona con varias iteraciones del ciclo, pero con diferentes partes del ciclo.

Ejemplo

Considere un bucle:

para i = 1 a número grande Ai) Bi) C(yo) final

En este ejemplo, A(i), B(i), C(i), denotan instrucciones, cada una de las cuales opera en el número de elemento iy cada instrucción depende de la anterior. En otras palabras, A(i)debe ejecutarse antes de que pueda B(i)ejecutarse. Una instrucción Apuede significar, por ejemplo, cargar un elemento de la memoria en un registro del procesador , B - alguna operación aritmética en un elemento en un registro, y C - escribir un elemento en la memoria . Al mismo tiempo, asumimos que no hay dependencias entre las iteraciones del bucle con diferentes valores i, es decir, la instrucción A(2)se puede iniciar antes de que finalice la instrucción A(1).

Sin la técnica de tubería de bucle, las operaciones se realizarían 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 requerirá tres ciclos para completarse (no tomaremos en cuenta el costo de ejecutar el ciclo en sí). Además, suponga que las instrucciones están programadas para ejecutarse en cada ciclo de reloj si no dependen de instrucciones ejecutables. Sin canalización, cada iteración de ciclo tomará 9 ciclos, 3 ciclos para A(1), 3 ciclos para B(1), 3 ciclos para C(1).

Ahora apliquemos la canalización de bucles. La secuencia de ejecución será:

A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...

En este caso, las instrucciones irán a ejecución cada ciclo, y cada tres iteraciones se ejecutarán en 9 ciclos, lo que dará una media de 3 ciclos por iteración.

En este ejemplo, la canalización se usó junto con el desenrollado de bucles . Pero, de manera más general, el desenrollado puede evitar que un bucle canalizado funcione de la mejor manera. Esto puede suceder en bucles que tienen operaciones de ejecución prolongada (como funciones matemáticas o de división). Los bucles como este se canalizan para ocultar el retraso de las operaciones largas.

Soporte de hardware

Las siguientes soluciones de hardware simplifican la optimización descrita: [2]

• "Registros rotativos" (a veces cambio de nombre de módulo en inglés  ): parte del archivo de registro se asigna al área de registros rotativos. Las instrucciones que utilizan algún registro arquitectónico de esta región accederán a diferentes registros físicos a medida que itera (y avanza en la región de rotación). Después de un cierto número de iteraciones, se volverá a acceder al registro físico original. Esto le permite trabajar con diferentes iteraciones del bucle al mismo tiempo, sin necesidad de transferencias explícitas entre registros. [1] [3]
• Predicados y ejecución de predicados de instrucciones, en los que algunos predicados de ciclos especiales funcionan como predicado. Estos predicados le permiten activar y desactivar algunas instrucciones de bucle durante las iteraciones, implementando así el prólogo y el epílogo del bucle en su código principal, y también simplifican la divulgación de operaciones condicionales en el cuerpo del bucle. [4] [5]
• Soporte de hardware para bucles, en el que el programa le da al procesador información sobre el tamaño del bucle y sobre los parámetros de la variable de índice. Esto le permite reducir los gastos generales para la organización del ciclo. También le permite ajustar la velocidad de rotación y el tamaño del grupo de registros giratorios. [6] [7]

Notas

1. ↑ 1 2 Microarquitectura del procesador Itanium psu.edu PDF Archivado el 5 de marzo de 2016 en Wayback Machine H Sharangpani, K Arora - IEEE Micro, 2000
2. ↑ M. Lam, "Canalización de software: una técnica de programación eficaz para máquinas VLIW", en 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).
3. ↑ Ah, 10.5.12
4. ↑ El impacto de la conversión if y la predicción de bifurcaciones en la ejecución del programa en el procesador Intel Itanium
5. ↑ Ah, 10.5.11
6. ↑ Compatibilidad con bucles superpuestos en Cydra-5 . brtop, siguientes instrucciones
7. ↑ Arquitectura de Itanium para programadores: comprensión de los procesadores de 64 bits , página 313, 10.4.2 "utilizados en la canalización de software incluyen el registro de recuento de bucles (ar.lc) (Sección 5.6), el registro de recuento de epílogos (ar.ec) y la rama especial instrucciones para construir bucles contados o while utilizando la rotación de registros", 10.4.5 "Instrucciones de bifurcación para canalización de software .. br.ctop, .. br.cexit.. br.wtop... br.wexit"

Literatura

• Aho. compiladores. Principios, tecnologías, herramientas. 2ª edición, 2008. Capítulo 10.5