Predictor de saltos para niños

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 la segmentación.

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 la segmentación que no deben de ser ejecutadas, teniendo que convertirse posteriormente en NOP, y decrementando así el rendimiento.

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

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.

Buffer de predicción de saltos o BPB (Branch Prediction Buffer)

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 o (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, solo se utiliza una parte de la dirección del PC, pero se produce el efecto alias (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.

Predictores 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 solo almacena el estado del salto anterior, su actualización es muy violenta, cambiando la predicción de un salto solo por un comportamiento puntual.

Predictor de 2 bits

Usa un contador de 2 bits para cada salto, con lo que puede contar hasta cuatro valores en binario (00, 01, 10 y 11, en decimal: 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 10 o 11, y predecirá no tomado en caso de que sea 00 o 01. 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. 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

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 sí. 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.

Búfer de destino de saltos o BTB (Branch-Target Buffer)

Conocido como BTB (búfer del siguiente salto) es una caché que almacena la dirección de la siguiente instrucción que sigue a un salto.

Se accede al 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 el 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 el BTB. Esto se conoce como fallo forzoso).

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

Véase también

En inglés: Branch predictor Facts for Kids