Predictor de saltos

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Un predictor de saltos (Branch predictor en Inglés) es un Circuito digital utilizado en los procesadores que utilizan segmentación de la unidad de proceso para reducir ciclos de parada en el pipeline.

Los saltos condicionales introducen retardo en estos procesadores, ya que normalmente no se evalúa la condición del salto hasta pasadas varias etapas, lo que hace que se tenga que parar el cauce, o que se puedan introducir instrucciones en el pipeline que no deben de ser ejecutadas, teniendo que convertirse posteriormente en NOPs, y decrementando así el rendimiento.

La predicción es posible anotando el comportamiento del programa en saltos anteriores.

Predictor dinámico[editar]

Un predictor dinámico trabaja en tiempo de ejecución, intentando aprender el comportamiento del programa para predecir con la mínima tasa de fallos si un salto será o no tomado. Existen varios tipos dependiendo de la información que son capaces de recoger sobre el programa para hacer predicciones.

Tabla de historia de saltos[editar]

Conocido como BHT (Branch History Table), son pequeñas memorias indexadas por la dirección del PC de la instrucción de salto.

Para almacenar todas las posibles instrucciones del PC, se necesitarían  2^{30} ó 2^{62}(en procesadores de 64 bits) posiciones (suponiendo que las direcciones del PC fueran múltiplos de 4, los 2 bits de menos peso son siempre 00), por lo que esas memorias se harían increíblemente grandes, y lentas, además de que se desperdiciaría la mayor parte de las entradas. En vez de eso, sólo se utiliza una parte de la dirección del PC, pero se produce el efecto aliasing(más de una dirección puede referirse a la misma posición de la tabla).

Así, las tablas de predicción guardan unos valores que se utilizan para predecir el comportamiento del siguiente salto. Su funcionamiento consiste en incrementar o decrementar -siempre con saturación- el contador cuando un salto ha sido tomado o no respectivamente.

Predictor de 1 bit[editar]

Guarda un bit de historia que dice si el salto fue tomado o no la última vez. Dado que en un bit sólo almacena el estado del salto anterior, su actualización es muy violenta, cambiando la predicción de un salto sólo por un comportamiento puntual.

Predictor de 2 bits[editar]

Usa un contador de 2 bits para cada salto, con lo que puede contar hasta 4 valores(0, 1, 2 y 3), si el salto anteriormente fue tomado, incrementa el contador, en caso contrario lo decrementa, y predecirá que el salto es tomado si se encuentra en los valores 2 ó 3 (bit más significativo a 1), y predecirá no tomado en caso que sea 0 ó 1 (bit más significativo a 0). Con lo que consigue mayor número de aciertos que el anterior, además de un reajuste más real del comportamiento del salto, no variando la predicción por un salto puntual.

Predictor de 3 bits[editar]

Igual que el anterior, solo que ahora puede contar hasta 8 valores. Aun así, tener más de 2 bits de predicción no implica tener mayor tasa de aciertos, pues en este caso el tiempo de adaptación de la predicción a un nuevo comportamiento del salto es más alto.

Predictores con correlación[editar]

Usan información de otros saltos recientes, además de la historia del salto a predecir en si.

Tendríamos ahora varias tablas funcionando como predictores de historia independientes entre si. Con bits adicionales, se lleva la cuenta, de forma similar a la anterior, de si los últimos saltos que ocurrieron en el programa fueron tomados o no, y dependiendo de estos, se elegirá una de las tablas de historia para hacer la predicción, que se indexan con el valor del PC y van actualizando sus valores como se hacía anteriormente.

La notación para referirse al número de bits de este predictor es (x,y), siendo 'x' el número de bits de correlación(los utilizados para elegir cada tabla), e 'y' el número de bits de historia que tendrá cada una de las tablas(predictor de 1 bit, predictor de 2 bits, etc). Así, un predictor (2,2), tendría 2 bits para referirse a cada una de las 4 tablas, las cuales tendrían cada una 2 bits de historia. Un predictor(8,1) tendría 256 tablas de 1 bit de historia.

Por lo tanto, un predictor de 2 bits normal, podría considerarse como un predictor de correlación (0,2).

Predictor híbrido[editar]

Los predictores híbridos combinan las dos estrategias de predicción anteriores. Tiene un predictor de cada tipo, que se van actualizando de manera independiente, se van contando los aciertos y los fallos que tiene cada uno, y se va entonces eligiendo cual usar en cada momento.

La idea es darle más peso al predictor que más acierte.

Buffer de destino de saltos[editar]

Conocido como BTB (Branch Target Buffer), es una caché que almacena la dirección de la siguiente instrucción que sigue a un salto.

Se accede a la BTB en la etapa de captación de la instrucción (IF) usando la dirección del PC actual. Si se encuentra una entrada, se obtiene del BTB cuál es la siguiente instrucción a ejecutar, que puede ser la siguiente en el orden secuencial o la del destino del salto; la elección dependerá del valor de los bits de predicción asignados a esa entrada. Si no se encuentra la dirección en la BTB, la instrucción no es un salto, o lo es y aún no ha sido ejecutado ninguna vez (la primera vez siempre falla la predicción, puesto que dicho salto no puede estar almacenado en la BTB. Esto se conoce como fallo forzoso).

En caso de que la dirección se encuentre en la BTB pero la predicción (salto tomado o no tomado) falle, se modificará la entrada correspondiente del BTB para predecir los futuros saltos correctamente.