Predictor de saltos
De Wikipedia, la enciclopedia libre
Un predictor de saltos es un mecanismo hardware utilizado en los procesadores que utilizan segmentación de cauce 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.
Tabla de contenidos |
[editar] Predictor dinámico
Un predictor dinámico trabajan 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.
[editar] Tabla de historia de saltos
Conocido como BHB (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 230 ó 262(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).
[editar] Predictor de 1 bit
Guarda un bit de historia que dice si el salto fue tomado o no la última vez. Sólo se actualizará cuando falla en la predicción.
[editar] Predictor de 2 bits
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, y predecirá no tomado en caso que sea 0 ó 1. Con lo que consigue mayor número de aciertos que el anterior.
[editar] Predictor de 3 bits
Igual que el anterior, solo que ahora puede contar hasta 8 valores, aún así, tener más de 2 bits de predicción no implica tener mayor tasa de aciertos.
[editar] Predictores con correlación
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).
[editar] Predictor híbrido
los predictores híbridos combina n 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.
[editar] Buffer de destino de saltos
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 en la etapa de decodificación de la instrucción(IF) usando la dirección del PC actual, si se encuentra una entrada se obtiene del BTB cual 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.
En caso de que la predicción haya fallado, se modificará la entrada correspondiente del BTB para predecir futuros saltos correctamente.
