Pipeline de software

En informática , la segmentación de software es una técnica que se utiliza para optimizar bucles , de forma similar a la segmentación de hardware . La segmentación de software es un tipo de ejecución fuera de orden , con la diferencia de que la reordenación la realiza un compilador (o, en el caso del código ensamblador escrito a mano , el programador) en lugar del procesador . Algunas arquitecturas informáticas ofrecen soporte explícito para la segmentación de software, en particular la arquitectura IA-64 de Intel .

Es importante distinguir el software pipelining , que es una técnica de código objetivo para iteraciones de bucle superpuestas, de la planificación modular , la técnica de compilador conocida actualmente más eficaz para generar bucles de software pipelining. El software pipelining ha sido conocido 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 eficaz de dicho código por parte del compilador se remonta a la invención de la planificación modular por Rau y Glaeser. ^{[ 1 ]} Lam demostró que no se necesita hardware especial para una planificación modular eficaz. Su técnica, la expansión de variables modular, se utiliza ampliamente en la práctica. ^{[ 2 ]} Gao et al. formularon el software pipelining óptimo en programación lineal entera, culminando 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.

Considere el siguiente bucle:

para i = 1 hasta número grande Ai) Bi) C(i) fin

En este ejemplo, sean A(i), B(i), C(i)instrucciones, cada una operando sobre datos i, que dependen unas de otras. En otras palabras, A(i)debe completarse antes de B(i)que pueda comenzar. Por ejemplo, Apodría cargar datos de la memoria en un registro , Bpodría realizar alguna operación aritmética sobre los datos y Cpodría almacenar los datos de nuevo en la memoria. Sin embargo, supongamos que no hay dependencia entre las operaciones para diferentes valores de i. En otras palabras, A(2)puede comenzar antes de A(1)que 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) ...

Supongamos que cada instrucción tarda 3 ciclos de reloj en completarse (ignoremos por el momento el coste del flujo de control del bucle). Supongamos también (como ocurre en la mayoría de los sistemas modernos) que una instrucción puede ser despachada en cada ciclo, siempre que no tenga dependencias de una instrucción que ya se esté ejecutando. En el caso sin segmentación , 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).

Ahora consideremos la siguiente secuencia de instrucciones con segmentació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, lo que da un promedio de 3 ciclos por iteración.

La segmentació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 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) A(i+1) A(i+2) Bi) B(i+1) B(i+2) C(i) C(i+1) C(i+2) fin

Por supuesto, la situación se complica si (como suele ocurrir) 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 el desenrollado de bucles para obtener más información sobre las soluciones a este problema, pero tenga en cuenta que la segmentación de software impide el uso del dispositivo de Duff .

En general, el desenrollado de bucles puede no ser la mejor manera de implementar la segmentación de software. Consideremos un bucle que contiene instrucciones con una alta latencia . Por ejemplo, el siguiente código:

para i = 1 hasta 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) ; 3 fin

Se requerirían 12 iteraciones del bucle para desenrollarse y 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 memoria, sino que también puede afectar el rendimiento de la caché , ver inflación de código ). Peor aún, el prólogo (código anterior al bucle para manejar el caso de bignumberno divisible por 12) probablemente será incluso más grande que el código del bucle, y muy probablemente ineficiente porque la segmentación de software no se puede usar en este código (al menos no sin una cantidad significativa de inflació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 (por ejemplo, 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 segmentación de software sea ineficaz.

En cambio, aquí está la secuencia de procesamiento del software para nuestro ejemplo (el prólogo y el epílogo se explicarán más adelante):

prólogo para 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(i) fin epí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 haga lo mismo que el original para las iteraciones en medio del bucle. Específicamente, consideremos la iteración 7 del bucle original. La primera iteración del bucle segmentado será la primera que incluya 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 segmentada evita el cuello de botella en la instrucción C. Nótese 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 gestionan las iteraciones al principio y al final del bucle. He aquí un posible prólogo para nuestro ejemplo anterior:

; prólogo del 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ía 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 han finalizado:

; 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)

La necesidad de un prólogo y un epílogo es una de las principales dificultades para implementar la segmentación de software. Cabe destacar que el prólogo en este ejemplo consta de 18 instrucciones, tres veces más 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 representan seis veces el tamaño del bucle . Si bien esto sigue siendo mejor que intentar desenrollar el bucle en este ejemplo, la segmentación de software exige un equilibrio entre velocidad y uso de memoria. Además, es importante tener en cuenta que si el código es demasiado extenso, afectará la velocidad de todos modos debido a una disminución en el rendimiento de la caché.

Otra dificultad radica en que, en muchas arquitecturas, la mayoría de las instrucciones utilizan un registro como argumento, y el registro específico a utilizar debe estar codificado directamente en la instrucción. En otras palabras, en muchas arquitecturas, es imposible codificar una instrucción como «multiplicar el contenido de los registros Xy Yy colocar el resultado en el registro Z», donde X, Y, y 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 de software no puede implementarse eficazmente 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-5Ella lo llama expansión de variables módulo . El truco consiste en replicar el cuerpo del bucle después de que se haya programado, lo que permite usar diferentes registros para diferentes valores de la misma variable cuando deben estar activos simultáneamente. Para el ejemplo más simple posible, supongamos que A(i)y B(i)se pueden ejecutar en paralelo y que la latencia de la primera es de 2 ciclos. El cuerpo segmentado podría ser entonces:

A(i+2); B(i)

La asignación de registros en el cuerpo de este bucle presenta el problema de que el resultado A(i+2)debe permanecer activo durante dos iteraciones. Usar el mismo registro para el resultado A(i+2)y la entrada B(i)dará como resultado errores.

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 separado 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 // Solo para que quede claro

Suponiendo que cada paquete de instrucciones lee sus registros de entrada antes de escribir en sus registros de salida, este código es correcto. Al inicio del cuerpo del bucle replicado, r1contiene el valor de A(i+2)la iteración anterior del bucle replicado. 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 sobre la caché, al igual que el prólogo y el epílogo. Sin embargo, para bucles con un gran número de iteraciones en arquitecturas con suficiente paralelismo a nivel de instrucciones, la técnica funciona lo suficientemente bien como para justificar cualquier aumento en el tamaño del código.

La arquitectura IA-64 de Intel proporciona un ejemplo de una arquitectura diseñada teniendo en cuenta las dificultades de la segmentación de software. Parte del soporte arquitectónico para la segmentación de software incluye:

• Un banco de registros rotatorio; las instrucciones pueden hacer referencia a un número de registro que se redirige a un registro diferente en cada iteración del bucle (que finalmente regresa al inicio). Esto hace innecesarias las instrucciones adicionales insertadas en el ejemplo anterior.
• Predicados (utilizados para "predicar" instrucciones; véase Predicación de bifurcación ) que toman su valor de instrucciones de bucle especiales. Estos predicados activan o desactivan ciertas instrucciones dentro del bucle, lo que hace innecesario un prólogo y un epílogo separados.