En este
artículo exploraremos con un poco más de profundidad algunas de las técnicas de
resolución de riesgos de control, de los que ya hablamos en un artículo anterior.
Los riesgos de control son aún más frecuentes que los
de datos, se dan en una de cada cinco instrucciones habitualmente, y tienen un
impacto muy negativo sobre el cauce de ejecución de las instrucciones,
penalizando incluso las soluciones tomadas para resolver los otros tipos de
riesgo.
Nos centraremos en los predictores de salto
multinivel y adaptativos.
Los
predictores multinivel se denominan así porque pueden tener en cuenta información
tanto local (del salto que se está intentando predecir) como global (de los
demás saltos del programa). Estarán compuestos entonces de predictores locales
y predictores globales y seguirán una notación como la siguiente (G, L) en la
que la letra G indica el número de saltos globales que se tienen en cuenta y la
L el número de bits del predictor local.
De los predictores locales hay dos tipos que son los
que se usan con más frecuencia: los de 1 y 2 bits que en la notación vista se
denominarían (0,1) y (0,2) respectivamente.
El de 1 bit sigue el esquema siguiente: tiene valor 1
si la última vez se tomó el salto y 0 si no fue así. Si la predicción falla se
cambia su valor. Es un planteamiento muy sencillo y con una utilidad limitada
ya que para ciclos repetitivos se suele fallar dos veces.
Con dos bits el esquema se vuelve un poco más
complejo y nos protegemos de las excepciones en bucles condicionales
repetitivos, se puede observar mejor su comportamiento en la siguiente figura:
Pueden implementarse predictores de más de dos bits
pero la práctica ha demostrado que no merece la pena.
El uso de los predictores multinivel se basa en que
se puede predecir el resultado del salto de una instrucción en función de los
resultados de instrucciones de salto anteriores.
Los
predictores adaptativos (o tournament predictors) 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.
Si el buffer de predicción predice que el salto no se
toma, no hay ningún retraso puesto que al ciclo siguiente se busca la
instrucción siguiente. Pero si se 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 llamado BTB (Branch Target Buffer).
El uso del BTB resulta especialmente importante en
arquitecturas como la MIPS en la que conocemos a la vez el resultado de evaluar
la condición de salto y la dirección de destino del mismo. El BTB es en esencia
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.
Otra forma de predicción de saltos adaptativa y que
resulta especialmente útil para aquellos saltos que se evalúan en tiempo de
ejecución (saltos indirectos) es la pila de direcciones. La razón por la que no
se puede usar el BTB con la misma fiabilidad para este tipo de saltos radica en
que la dirección de destino del salto va variando en cada ejecución de la
instrucción de retorno.
Esta pila funciona de manera que se almacenan las
direcciones desde las que se llama a los procedimientos. Si la pila es lo
suficientemente profunda, cuando se realicen los retornos se irán recuperando
las direcciones adecuadas de la pila y se cumplirán las predicciones con un
elevado porcentaje de acierto.
En el gráfico siguiente se puede ver el rendimiento
de esta técnica en distintos procesadores.
