Tema 2. Predictores de salto multinivel y adaptativos

                 El pipelining ofrece una gran ventaja aumentando la velocidad del procesador, pero desafortunadamente, la presencia de instrucciones de saltos condicionales en el programa en ejecución reduce fuertemente este aumento de la capacidad de procesamiento.

                 Esto se debe a que los saltos condicionales se resuelven (el salto es tomado o no) en las últimas etapas. Si el salto se realiza, debe vaciarse la mayoría de las etapas del pipeline, y completarse nuevamente con las instrucciones que siguen a la de la dirección de salto, lo cual significa una pérdida de tiempo. Esta pérdida de beneficio en el pipeline se realiza cada vez que un salto condicional ingresa al procesador, es decir por cada salto dinámico del código en ejecución. En el caso de los saltos incondicionales, no existe este problema, dado que se conoce de antemano la dirección de salto y no existe duda alguna de que éste será tomado. Sin embargo, el hardware del microprocesador debe identificar este tipo de instrucciones antes de que ingresen a la etapa DECODE. Para reducir la pérdida de eficacia del pipeline ante la presencia de saltoscondicionales se introdujo el concepto de Predicción de Salto (Branch Prediction).

                 El Predictor de Salto es un bloque de hardware adicional, ubicado fuera de la línea del pipeline, el cual le indica a la Unidad de Búsqueda de Instrucción la dirección de la próxima instrucción a ejecutar, empleando para ello una determinada estrategia de predicción. Los predictores de salto no aparecieron en los microprocesadores hasta la década del 90. Algunos de los primeros microprocesadores en usar prediccióndurante ejecución (run-time) fueron MOTOROLA MC88110, DEC Alpha 21064 eINTEL Pentium. La exactitud en la predicción del salto impacta fuertemente en el desempeño del procesador.

                 Todas las técnicas que vamos a ver a continuación se basan en predecir si los saltos se van a tomar o no.

Buffer de predicción de saltos


                 Es la técnica más sencilla, también se denomina tabla de historia de saltos. Es una pequeña memoria que se indexa con la parte baja de la dirección de las instrucciones de salto. Como sólo se utiliza la parte baja de las direcciones cabe la posibilidad de que varios saltos se indexen en el buffer con la misma etiqueta, de manera que van sobreescribiendo sus predicciones. Esta memoria contiene una serie de bits que resumen el comportamiento del salto en ejecuciones anteriores y que permiten predecir cuál va a ser su comportamiento esta vez.

Puede implementarse de dos maneras diferentes:
- Como una pequeña caché a la que se accede en la fase IF al mismo tiempo que se busca la instrucción por si fuera un salto.
- Como un bloque de bits que se almacena junto a las instrucciones de salto en la caché de instrucciones.

Cuando se decodifica una instrucción y resulta ser un salto, se utilizan los bits de predicción para realizar la predicción del salto.
- Si se predice como no tomado, se sigue con la búsqueda secuencial de instrucciones.
- Si se predice como tomado, en cuanto se conoce la dirección destino de salto se pasa a buscar esa instrucción.

                 Si se ha acertado la predicción se habrá reducido la penalización por riesgo de control. Si se falla, se busca la instrucción adecuada y se corrige el predictor en el buffer. La mejora global que se obtendrá gracias al buffer de predicción dependerá de la tasa de fallos, de la frecuencia de las instrucciones de salto y de la penalización que supone un fallo de predicción. Para mejorar el rendimiento de un buffer de predicción los diseñadores suelen centrarse en disminuir la tasa de fallos en todo lo posible.

Para reducir la tasa de fallos del buffer de predicción existen varias posibles soluciones:
- Si el predictor es de un único bit, se puede mejorar haciéndolo de 2 bits.
- Si el buffer de predicción tiene menos de 4096 entradas, se puede aumentar su tamaño.

Se pueden utilizar predictores multinivel o correlados. Con estos predictores se tiene en cuenta el comportamiento que han tenido recientemente todos los saltos, no sólo el del salto para el que estamos haciendo la predicción.

Predictores Multinivel

                 La característica diferenciante de los predictores multinivel es que tienen en cuenta información local (del salto para el que se realiza la predicción) y global (del resto de saltos del programa). La manera más sencilla de entender este tipo de predictores es estudiando el caso (1,1), que además es el más frecuente. En este caso, el predictor asociado a cada salto es de dos bits:
- El primero es la predicción para el salto si el último salto del programa no se tomó.
- El segundo es la predicción para el salto si el último salto del programa se tomó.

Predictor de saltos

                 Este predictor se llama (1,1) porque utiliza el comportamiento del último salto para escoger un predictor de un bit para el salto actual. En general, un predictor (m,n) utiliza el comportamiento de los m últimos saltos tomados para escoger un predictor de n bits para el salto actual. Teniendo en cuenta información global (de todas las instrucciones de salto) se puede mejorar la tasa de acierto de un predictor local (que tan sólo tiene en cuenta información relacionada con el salto para el que se va a hacer la predicción). Pero esta mejora no necesariamente tiene que compensar la utilización de un hardware más complejo, puede incluso que no exista mejora alguna.

Predictores Adaptativos

                Los predictores adaptativos tienen la capacidad de escoger un predictor local o un predictor global según cuál se vaya a comportar mejor para un determinado salto. En todas las arquitecturas en las que se conoce la dirección destino de salto al mismo tiempo que el resultado de la evaluación de la condición el buffer de predicción de saltos no resulta muy eficiente.

                 Si el buffer de predicción pronostica que el salto no se toma, no hay ningún retraso puesto que al ciclo siguiente se busca la instrucción siguiente. Pero si el buffer de predicción predice que el salto se va a tomar, no se puede buscar la instrucción destino de salto hasta que no se haya calculado la dirección de esta instrucción. Y una vez que se conozca esta instrucción ya se conoce si el salto se toma realmente o no, así que no tiene sentido continuar utilizando la predicción.

                 La solución está en implementar algún mecanismo que permita predecir también la dirección destino de salto. Este mecanismo es el buffer de predicción de destino de salto.

Buffer de predicción de destino de salto - Branch Target Buffer (BTB)

                 Esta técnica trata de resolver el problema de la predicción de saltos para cauces como el del MIPS, en los que se conoce al mismo tiempo la dirección destino de salto que la evaluación de la condición. El BTB es una caché que almacena la dirección destino que tuvo cada salto la última vez que se tomó. El acceso al BTB se hace durante la etapa IF de las instrucciones: al mismo tiempo que se busca la instrucción en la memoria de instrucciones, con su dirección se accede al BTB para saber si se trata de una instrucción de salto.

Pila de direcciones

                Esta técnica se ha incorporado recientemente a la mayor parte de las arquitecturas para realizar predicciones en el caso de saltos indirectos, o lo que es lo mismo, saltos que se resuelven en tiempo de ejecución. La mayor parte de estos saltos son retornos de procedimiento y aunque se puede utilizar el BTB para estos saltos, no es la técnica más adecuada puesto que se puede llamar al mismo procedimiento desde diferentes partes del programa y entonces las direcciones de retorno (los destinos del salto) irán variando en cada ejecución de la instrucción de retorno.

                 La solución es usar una pila para almacenar las direcciones desde las que se llama a los procedimientos. Así se tienen guardadas las direcciones de retorno. Si esta pila es lo suficientemente profunda, cuando se realicen los retornos se irán desapilando las direcciones adecuadas y se acertarán todas las predicciones.

Referencias:

Predictores de salto multinivel:
 http://triton.javeriana.edu.co/carrera/tgrado/2001-1/saltos.PDF


Eficacia de los Predictores de Salto en procesadores: http://www.frcu.utn.edu.ar/deptos/depto_3/32JAIIO/ast/ast_04.pdf

Apuntes de la URJC: http://gdhwsw.escet.urjc.es/AIC/Tema3-2.pdf