Arquitectura macroescalar, Parte I: De pipelines y compiladores por Juan de Dios Santander

Hace poco hablamos en Faq-mac que Apple había recibido una patente para microprocesadores macroescalares, y hacían referencia a un artículo de ZDNet donde se explicaba en qué consiste esa arquitectura.

Sin embargo, la explicación que había en ambos artículos resultaba a mi entender poco satisfactoria, porque se mezclaban conceptos que venían a ser una mezcla de software y hardware.

Para intentar entender un poco mejor qué es lo que se ha patentado, y si corresponde a un nuevo diseño de microprocesadores, voy a dedicar un primer artículo a explicar algunos conceptos de arquitectura de procesadores, como qué es un pipeline, o la segmentación de instrucciones, mientras que en el próximo artículo abordaremos directamente la patente.

Segmentando instrucciones

Las instrucciones en los microprocesadores son conjuntos de bits que indican al microprocesador qué instrucción realizar, y con qué recursos. Los recursos en microprocesadores CISC (como los 80486 y anteriores, o los microprocesadores 680×0 de los Mac pre-PowerPC) podían ser algunos de los registros internos, o zonas de la memoria. En microprocesadores RISC, como los PowerPC, o los procesadores ARM, esos recursos son exclusivamente los registros internos, y a la memoria sólo se accede para leer y a escribir en registros.

Podemos dividir los pasos necesarios para ejecutar una instrucción en:

1. Obtener la instrucción de la memoria.
2. Decodificar la instrucción, y saber qué parte del procesador tendrá que llevarla a cabo.
3. Ejecutar la instrucción: sumar, multiplicar, dividir… o si es de otro tipo, esperar a la siguiente.
4. Si es necesario acceder a memoria para acceder a operandos, hacerlo.
5. Escribir resultados.

Originalmente, estas operaciones se realizaban secuencialmente: esto es, el microprocesador cogía una instrucción, la decodificaba, según la decodificación pasaba las instrucciones a la unidad correspondiente, si era necesario leer datos de memoria los leía, y escribía los resultados.

Sin embargo, esto es muy poco eficiente: es el equivalente a tener a única persona montando un coche, de forma que hasta que no ha terminado un coche no puede empezar con el siguiente.

Si dedicamos un área del microprocesador a realizar cada una de las funciones anteriores, y las conectamos, el área de obtención de instrucciones puede estar obteniendo una instrucción, y pasarla a la fase de decodificación, mientras obtiene otra; la de decodificación puede pasar resultados a ejecución y pasar a decodificar; y así sucesivamente, de forma parecida a una cadena de montaje.

Puesto que se puede aplicar las matemáticas de las cadenas de montaje a los pipelines, está claro que el tiempo mínimo para cada fase es el máximo de los tiempos de las fases, esto es, la fase más lenta es la que marca el ritmo del pipeline.

Si por cada tic-tac del reloj se realiza una fase, el tiempo total para la ejecución de una instrucción en particular es de 5 tics (pasar por las cinco fases), pero si mantenemos el pipeline siempre con instrucciones, el tiempo en promedio por cada instrucción será de 1 tic, porque a la fase final del pipeline llega una instrucción por cada tic.

Burbujas en la tubería

En el último párrafo poníamos la condición de mantener el pipeline siempre con instrucciones. Pero en la práctica esto no siempre es posible, y una de las razones principales son las instrucciones de salto condicional, porque en esos casos son dos las posibles instrucciones siguientes.

Por ejemplo, si estoy contando de 1 a 100, y haciendo una operación para cada número, como sumar 3 a la cuenta y almacenarlo, y después voy a hacer una multiplicación, las instrucciones serían:

1. Poner acumulador a 0
2. Poner contador a 1
3. Coger valor de contador, y sumar 3 al acumulador
4. Comparar valor de contador, y ver si es mayor que 100.
5. Si no es mayor, ir a 3; si no, ir a 6.
6. Multiplicar el acumulador por 4.

Pero el flujo de instrucciones para el microprocesador es:

1 2 3 4 5 3 4 5 3 4 5 ... 3 4 5 6

Y deberían empezar a ejecutarse a razón de una por ciclo, después de haber pasado los cinco ciclos de la primera. ¿O no?

El problema aquí es que en 5 hay que esperar a que se haya terminado de ejecutar 4 antes de poder ejecutarla. Eso significa que hay que esperar a que 4 haya llegado a la fase de escritura de resultados, antes de que 5 pueda entrar en la fase de ejecución.

Además, puesto que la instrucción siguiente no puede entrar en el pipeline hasta que no se sepa si será 3 o 6, en realidad el flujo anterior se parece más a:

T +++++++++++++++++++++++++++++++++++++++++++

W 1234 5 34 5 34 5 5 34 5 6

Donde cada + significa un ciclo de reloj, y F representa la etapa de obtención de la instrucción (Fetch), D la etapa de decodificación (Decode), E la de ejecución (Execute), M la de acceso a memoria (Memory Access), y W la de escritura (Writeback).

La última fase es la de escritura, así que podemos ver que hemos necesitado 11 ciclos para terminar la primera vuelta, y a partir de ahí 8 por cada ciclo otras 99 veces, más 4 ciclos más para la última instrucción. En total, 11+8·99+4 = 807 ciclos para un total de 4+3·99+1 = 302 instrucciones, de modo que tenemos un promedio de 807/302 = 2,67 ciclos por instrucción, o 0,37 instrucciones por ciclo (IPC), muy por debajo del máximo teórico de una instrucción por ciclo.

Bitomancia informática, o de cómo evitar burbujas leyendo los bits

Si la quiromancia es el arte de leer el futuro en las manos, y la cartomancia el de leer el futuro en las cartas, la bitomancia sería el arte de leer el futuro en los bits.

Para un humano, está claro que el bucle anterior va a consistir en saltos a la instrucción 3 casi siempre, 99 de cada 100 veces, y sólo en la última se va a saltar a la 3.

Así que una solución sería saltar siempre a la instrucción 3, y sólo si a posteriori descubrimos que nos equivocamos, invalidar las instrucciones, y saltar a la 6. Estaríamos prediciendo que el salto se va a producir, y obteniendo la ristra de instrucciones que corresponde a saber que el salto se ha producido:

T ++++++++++++++++++++++++++

W 1234534534...5345 6

¿Qué sucede aquí? Ahora tenemos una lista de instrucciones continua, excepto cuando se produce la centésima evaluación de 5, y se descartan los resultados anteriores, y se carga la instrucción 6, que necesita todo el tiempo para ejecutarse. De este modo, necesitamos solamente 5+99·3+5 = 307 ciclos para completar las 5+99·3+1 = 303 instrucciones, o lo que es lo mismo, 0,987 IPC, mucho más cerca del máximo teórico.

Sin embargo, podemos ver que si en vez de 100 fuesen n veces las que hay que hacer este bucle, la eficiencia es:

IPC = [3(n–1)+5+1]/[3*(n–1)+2·5]

Para bucles grandes, es como la teórica, pero para bucles pequeños (menos de cinco veces, por ejemplo), la eficiencia (instrucciones por ciclo) es peor que el 80%.

Además, hay otro problema: no es posible sincronizar los relojes en distancias demasiado grandes dentro de un microprocesador, de modo que si queremos aumentar la frecuencia de reloj, la mas lenta de las fases será la que nos diga cuán rápido puede ir ese reloj. Así que para poder subir la frecuencia, es común dividir las etapas del pipeline en fases más cortas, pero el astuto lector se habrá dado cuenta de que la ecuación anterior se puede escribir como:

IPC = [3(n–1)+p+1]/[3*(n–1)+2p]

Donde p es el número de pasos del pipeline, y se puede ver que si el número de pasos es comparable al número de ciclos, el rendimiento es del 80%, o peor para pipelines más profundos, o bucles más cortos.

Así que aumentar el número de etapas de un pipeline nos permite subir la frecuencia de reloj, pero al mismo tiempo nos baja la eficiencia (en número de instrucciones por ciclo) del microprocesador. De otra parte, si conseguimos que nuestros bucles contengan más instrucciones, podemos mejorar la eficiencia si aumentamos el tamaño de los pipelines. ¿Cómo resolver el dilema?

Compilando soluciones

La solución es intentar que el programa que lee las instrucciones en lenguajes como Objective-C (el lenguaje propio para Mac OS X), y las traduce a las secuencias de bits que puede ejecutar el microprocesador, conozca los detalles del microprocesador destino, como el número de recursos disponibles, y el tamaño de los pipelines, e intente mantener el pipeline lleno. Pero, ¿cómo hacerlo?

Una solución, cuando se tiene un número fijo de repeticiones (esto es, el número n de repeticiones del ciclo es conocido cuando se crea el programa, no depende de qué pase cuando se ejecute), es que el compilador desenrolle el bucle, produciendo la serie de instrucciones exacta que tiene que darse, de forma que no son necesarias las comparaciones, y además el orden de las instrucciones es predeterminado.

Si tenemos un bucle interno desenrollado en múltiples instrucciones, los bucles exteriores que puedan rodearlo afectan mucho menos al rendimiento, puesto que la parte interior ya está realizada.

¿Qué ocurre cuando el bucle que queremos realizar no afecta sólo a instrucciones estáticas, sino que hay contenido sobre el que iterar? Por ejemplo, queremos operar sobre los elementos de una imagen. Podemos imaginar una línea en una zona de contraste con valores en blanco y negro entre 0 y 100:

2 3 1 0 2 3 27 33 58 89 99 88 97

Si quisiéramos calcular la mediana de los valores en cada pixel para quitar ruido, tendríamos que ir, por ejemplo de tres en tres valores, rellenando al principio y al final con valores duplicados:

En la figura anterior, se muestra qué tres valores se usan para ordenar, y después calcular la mediana usando el valor intermedio por orden.

Una forma de hacerlo en un programa es, en pseudocódigo:

usar un índice i = 0

fin mientras

Pero ya sabemos que las instrucciones tendrán un parón cada vez que comprobemos el fin del bucle y resulte que tenemos que terminar.

Además, puede haber un “bucle oculto” en la ordenación de los tres elementos.

Para un procesador macroescalar, con un ingente número de registros, podemos escribir:

poner valores en primer, segundo y tercer lugar en r1, r2, r3

devolver r2, r5, r8...

Así, no tendríamos bucle, y el flujo de instrucciones podría ser perfecto.

Además, como las instrucciones son independientes entre sí, se pueden ejecutar en cualquier orden, de forma que el microprocesador puede organizar su flujo de instrucciones para mantener el pipeline lleno al máximo.

Pero este truco no es propio sólo de procesadores macroescalares, sino que la reordenación de instrucciones aparece en muchos procesadores con pipelines profundos, justamente para intentar mantenerlos llenos.

Puede que el lector se haya dado cuenta de que para poder mantener el flujo de instrucciones, hemos utilizado:

Todas las técnicas anteriores pueden utilizarse en un compilador, a cambio de tener una sección absolutamente específica para cada microprocesador, mientras que la parte dedicada al reconocimiento de bucles y su desenrollado es específica de cada lenguaje de programación.

Además, las dos primeras técnicas se pueden implementar en el microprocesador, y de hecho, microprocesadores como los Pentium III y posteriores, o los PowerPC G5, las implementan. Pero esas técnicas son más bien el resultado de que hubo que tener pipelines largos para aumentar la frecuencia de reloj. A cambio, se trata de más circuitería que está consumiendo energía, y que no va en provecho directo del rendimiento de cada instrucción (que necesita más ciclos de reloj para pasar por el pipeline completo).

Así que si Apple decide perseguir los procesadores macroescalares, es necesario que cree una microarquitectura en la que haya muchísimos registros (al menos tantos como había en los PowerPC), y que exista una gran parte de circuitería dedicada al reconocimiento de bucles, y su interpretación en forma de instrucciones desenrolladas.

Veremos en qué consiste realmente la patente, y si realmente indica que Apple va a crear un nuevo tipo de microprocesador, en el siguiente artículo.

Un artículo de Juan de Dios Santander en Memoria de Acceso Aleatorio