Con la aparición de Meltdown y Spectre la gran mayoría de usuarios de dispositivos móviles y computadoras han descubierto que sus CPU hacen algo llamado ejecución especulativa, pero muchos no tienen claro qué es o por qué se ha incluído en los microprocesadores. El objetivo de este post es clarificar ese concepto para aquellos que no lo logran asimilarlo.
Todo empiza con la definición más sencilla de una computadora que la Máquina de Turing, que de acuerdo a cómo lo definió Turing es:
… una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por ese símbolo, pero los símbolos en otros lugares de la cinta no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad
Esto que parece tan enrevesado y genérico puede ser expresado de otra forma para describir una computadora digital moderna como: una máquina capaza de explorar secuencialmente una información almacenada en su memoria llamada programa, es capaz de interpretarla y ejecutar los comandos alli contenidos.
No importa que tan complejo sea un microprocesador, cuántos núcleos tenga o cuál sea la arquitectura internal del mismo, consideramos que se comporta como una Máquina de Turing.
No hay nada mejor que explicar con ejemlos, para ellos consideremos que tenemos un programa bastante sencillo como el siguiente:
t = a+b
u = c+d
v = e+f
w = v+g
x = h+i
y = j+k
El tipo más simple de procesador moderno ejecuta una instrucción por cada ciclo de reloj, por lo cual lo llamamos un procesador escalar. Por lo tanto el programa que mostramos como ejemplo anteriormente se ejecutaría en seis ciclos de reloj en un procesador escalar. El ejemplo más típico de procesador escalar es el ahora arcaíco Intel 486.
La forma obvia de hacer que un procesador escalar (o cualquier otro tipo de procesador) corra más rápido es aumentar la velocidad del reloj. Pero existe un límite físico de cuán rápido pueden cambiar su estado las puertas lógicas dentro de los procesador; Por lo tanto, los diseñadores de procesadores comenzaron a buscar maneras de hacer varias cosas a la vez dentro de los procesadores.
Un procesador superescalar en orden examina la secuencia entrante de instrucciones e intenta ejecutar más de una a la vez, usando una de varias tuberías (pipes en inglés), sujeto a dependencias entre las instrucciones. Las dependencias son importantes: podría pensarse que un procesador superescalar de dos vías podría emparejar las seis instrucciones en nuestro ejemplo de esta manera:
Tuberia-1 Tuberia-2
t = a+b u = c+d
v = e+f w = v+g
x = h+i y = j+k
Pero eso no tiene sentido, ya que tenemos que calcular v antes de poder calcular w, por lo que las instrucciones tercera y cuarta de nuestro ejemplo inicial no se pueden ejecutar a la vez. Nuestro procesador superescalar de dos vías en realidad no podrá encontrar nada para emparejar con la tercera instrucción, por lo que nuestro ejemplo se ejecutará en cuatro ciclos de la siguiente manera:
Tuberia-1 Tuberia-2
t = a+b u = c+d
v = e+f
w = v+g x = h+i
y = j+k
Como ejemplos de procesadores superescalares podemos mencionar al Intel Pentium y los procesadores basados en núcleos ARM Cortex-A7 que son utilizados en las tarjetas de prototipado Raspberry Pi, Banana Pi y Orange Pi. .
¿Cómo podemos obtener aún más rendimiento de un procesador superescalar?
Volviendo a nuestro ejemplo inicial, podemos ver que, aunque tenemos una dependencia entre v y w, tenemos otras instrucciones independientes más adelante en el programa que podríamos haber utilizado para llenar la tubería vacía durante el segundo ciclo. Un procesador superescalar fuera de orden tiene la capacidad de mezclar el orden de las instrucciones entrantes (nuevamente sujeto a dependencias) para mantener sus tuberías ocupadas.
Un procesador fuera de orden podría intercambiar efectivamente las instrucciones para calcular w y x en nuestro ejemplo de esta manera:
t = a+b
u = c+d
v = e+f
x = h+i
w = v+g
y = j+k
lo que le permite ejecutar el programa en sólo tres ciclos:
Tuberia-1 Tuberia-2
t = a+b u = c+d
v = e+f x = h+i
w = v+g y = j+k
Entre los ejemplos de procesadores superescalares fuera de orden se incluyen el Intel Pentium 2 (y la mayoría de los procesadores Intel y AMD x86 posteriores, con la excepción de algunos dispositivos Atom y Quark) y muchos núcleos ARM recientes, incluidos el Cortex-A9, el Cortex-A15, el Cortex-A17 y el Cortex-A57.
¿Qué es la predicción de salto?
En nuestro ejemplo anterior tenemos un programa que se ejecuta linealmente. Los programas reales no son así por supuesto, también contienen ramas en las cuales el flujo de ejecución se bifurca, este tipo de instrucciones se suelen reprecentar por la palabra if. Una rama puede ser incondicional (por ejemplo un salto a otra línea) o condicional (en base a una condición lógica se decide si se sigue por una u otra rama). Además las instrucciones de salto puede ser directo (se especifica explícitamente una dirección de destino) o indirecto (se toma la dirección de destino de un registro, ubicación de memoria o de la pila del procesador).
Mientras busca instrucciones, un procesador puede encontrarse con una rama condicional que depende de un valor que aún no se ha calculado. Para evitar un bloqueo (el procesador no hace nada hasta que la dependencia se resuelva), debe adivinar qué instrucción buscar a continuación: la siguiente en orden de memoria (correspondiente a una rama no tomada) o la que está en el destino de la rama (correspondiente a una rama tomada). Un predictor de salto ayuda al procesador a hacer una suposición inteligente sobre si se tomará una rama o no. Lo hace mediante la recopilación de estadísticas sobre la frecuencia con que las ramas particulares se han tomado en el pasado.
Los predictores de salto modernos son extremadamente sofisticados y pueden generar predicciones muy precisas. Sin embargo, al ejecutar una serie de ramas elaboradas, un atacante puede entrenar de forma equivocada al pronosticador de rama para hacer que este tome malas predicciones.
Finalmente, ¿qué es ejecución especulativa?
Reordenar las instrucciones secuenciales es una forma poderosa de recuperar más paralelismos a nivel de instrucción, pero a medida que los procesadores se vuelven más potentes (capaces de triplicar o cuadruplicar las instrucciones ejecutadas en cada ciclo de reloj) se vuelve más difícil mantener ocupadas todas esas tuberías. Por lo tanto, los procesadores modernos han añadido la capacidad de especular qué código se ejecutará proximamente. La ejecución especulativa nos permite procesar instrucciones que podrían no ser necesarias (porque puede haber una ramificación): esto tiene como objetivo mantener un canal ocupado (que de otra forma estaría inactivo). Y si resulta que la instrucción no se ejecuta, solo tendriamos que descartar el resultado.
La ejecución especulativa de instrucciones innecesarias (y la infraestructura necesaria para permitir la especulación y el reordenamiento de instrucciones) consume energía extra, pero en muchos casos esto se considera un intercambio rentable para obtener un rendimiento superior. El predictor de salto se utiliza para elegir la ruta más probable a través del programa, lo que maximiza la posibilidad de que la especulación valga la pena.
Para demostrar los beneficios de la especulación, veamos otro ejemplo:
t = a+b
u = t+c
v = u+d
if v:
w = e+f
x = w+g
y = x+h
Ahora tenemos que u depente de t, que v depende de u y además que x depende de w y y depende de x, en una disposición tal que un procesador fuera de orden, bidireccional y sin ejecución especulativa nunca podrá llenar su segunda tubería. Pasa tres ciclos computando t, u y v, luego de lo cual sabe si el cuerpo de la sentencia if se ejecutará, en cuyo caso pasará tres ciclos computando w, x, y y. Suponiendo que if (implementado por una instrucción de bifurcación) toma sólo un ciclo, nuestro ejemplo se ejecutaría en cuatro ciclos (si v resulta cero) o siete ciclos (si v no es cero).
Si el predictor de rama indica que es probable que se ejecute el cuerpo de la sentencia if, la ejecución especulativa reordenaría el programa de la siguiente manera:
t = a+b
u = t+c
v = u+d
w_ = e+f
x_ = w_+g
y_ = x_+h
if v:
w = w_
x = x_
y = y_
Entonces ahora tenemos un paralelismo de nivel de instrucción adicional para mantener nuestras tuberías ocupadas de la siguiente manera:
Tuberia-1 Tuberia-2
t = a+b w_ = e+f
u = t+c x_ = w_+g
v = u+d y_ = x_+h
if v: w = w_, x = x_, y = y_
Aunque el conteo de los ciclos está menos definido en los procesadores superescalares con ejecución especulativa fuera de orden, la rama y la actualización condicional de w, x y y son (aproximadamente) instántaneos, por lo cual nuestro ejemplo se ejecuta en (aproximadamente) tres ciclos de reloj.
De lo anterior se desprende por qué crear procesadores superescalares, con ejecución especulativa y fuera de orden representa una gran ganacia de rendimiento y de alli la razón de que todos lo hayan adoptado. Cómo se menciona hay un incremento en el consumo de enegía y la complejidad del procesador, pero eso es compensado con ganacias de rendimientos del 30% o más.
Ahora que los términos ya están más claros, puedes releer si quieres los posts que explican cómo funcionan las vulnerabilidades Meltdown y Spectre.
Para escribir este post nos basamos en el excelente post de Ebe Upton en el blog de la comunidad de Raspberry Pi.