- Predictor de saltos
-
Predictor de saltos
Un predictor de saltos es un mecanismo hardware 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.
Contenido
Predictor dinámico
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
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 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).
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
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
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
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, 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
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
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
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(ID) 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. Si no se encuentra la dirección, 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, porque no la hay).
En caso de que la predicción haya fallado, se modificará la entrada correspondiente del BTB para predecir futuros saltos correctamente.
Enlaces externo =
Categoría: Unidad central de procesamiento
Wikimedia foundation. 2010.
