Predictor de ramificaciones

La predicción estática es la técnica de predicción de bifurcaciones más simple porque no depende de información sobre el historial dinámico de ejecución del código. En cambio, predice el resultado de una bifurcación basándose únicamente en la instrucción de bifurcación. ^{[ 7 ]} Las primeras implementaciones de SPARC y MIPS (dos de las primeras arquitecturas RISC comerciales ) usaban predicción de bifurcaciones estáticas unidireccionales: siempre predecían que un salto condicional no se tomaría, por lo que siempre buscaban la siguiente instrucción secuencial. Solo cuando la bifurcación o el salto se evalúa y se encuentra que se toma, el puntero de instrucción se establece en una dirección no secuencial.

Ambas CPU obtienen las instrucciones en un ciclo y evalúan las bifurcaciones en la etapa de decodificación. Como resultado, la recurrencia del destino de la bifurcación dura dos ciclos, y la máquina siempre obtiene la instrucción inmediatamente después de cualquier bifurcación tomada. Ambas arquitecturas definen intervalos de retardo de bifurcación para utilizar estas instrucciones obtenidas.

Una forma más avanzada de predicción estática asume que las bifurcaciones hacia atrás se tomarán y las bifurcaciones hacia adelante no. (Una bifurcación hacia atrás es aquella cuya dirección de destino es menor que su propia dirección). Esta regla aumenta la precisión de la predicción en bucles, que pueden construirse con una bifurcación hacia atrás al final que se toma mayoritariamente, o una bifurcación hacia adelante al principio que no se toma mayoritariamente. Con los procesadores que utilizan este método de predicción, el orden de las instrucciones puede maximizar la precisión de la predicción de bifurcaciones. El conjunto de instrucciones RISC-V recomienda que el software escrito para núcleos RISC-V (hilos de hardware), o generado para ejecutarse en núcleos RISC-V, se optimice bajo el supuesto de que las bifurcaciones hacia atrás se toman y las bifurcaciones hacia adelante no. (Incluso cuando el procesador incorpora un predictor más avanzado que disminuye el valor relativo de la predicción estática). ^{[ 8 ]}

Algunos procesadores aceptan sugerencias de predicción de bifurcaciones que anulan la predicción estática. Los procesadores Intel Pentium 4 y Pentium 4E aceptan sugerencias de predicción de bifurcaciones como prefijos. En presencia de predicción dinámica, la predicción estática no ofrece prácticamente ningún beneficio, y anularla ayuda aún menos. Los procesadores posteriores Intel Pentium M y Core2 ignoran los prefijos de sugerencias de predicción de bifurcaciones. ^{[ 9 ]} Ningún fabricante de x86 ha reintroducido las sugerencias de predicción.

Los predictores de bifurcación dinámicos recurren naturalmente a la predicción de bifurcación estática cuando no tienen información en caché (como la primera vez que se encuentra una bifurcación determinada). Tanto el Motorola MPC7450 (G4e) como el Intel Pentium 4 recurren a la predicción estática. ^{[ 10 ]}

En la predicción estática, todas las decisiones se toman en tiempo de compilación, antes de la ejecución del programa. ^{[ 11 ]}

La predicción dinámica de bifurcaciones ^{[ 2 ]} utiliza información sobre las bifurcaciones tomadas o no tomadas recopilada en tiempo de ejecución para predecir el resultado de una bifurcación. ^{[ 1 ]}

La predicción aleatoria de bifurcaciones implica adivinar al azar si una bifurcación se tomará cada vez que se ejecuta. El costo de un generador de números pseudoaleatorios es bajo en comparación con otras técnicas. La predicción aleatoria garantiza una tasa de predicción correcta del 50%, que no se puede aumentar ni reducir de ninguna manera. (Y hace que la sincronización sea aún más no determinista o impredecible que otros métodos). La predicción estática de bifurcaciones (suponiendo que las bifurcaciones hacia adelante se toman y las bifurcaciones hacia atrás no) predice cada bifurcación con una precisión que va del 0% al 100%, con una tasa de éxito general en algún punto intermedio. Es muy probable que el código no optimizado se ejecute con una precisión de predicción superior al 50%; incluso es probable que alcance el 90%. Si el compilador realiza algún reordenamiento de instrucciones, la tasa de predicción correcta de bifurcaciones es mayor que para el código no optimizado. La predicción estática de bifurcaciones superó hace mucho tiempo a la predicción aleatoria de bifurcaciones. La predicción dinámica de bifurcaciones ha superado a la predicción estática de bifurcaciones y es común, a pesar de la complejidad adicional.

Algunos procesadores superescalares (MIPS R8000 , Alpha 21264 y Alpha 21464 (EV8)) obtienen cada línea de instrucciones con un puntero a la siguiente línea. Este predictor de la siguiente línea gestiona tanto la predicción del destino de la bifurcación como la predicción de su dirección.

Cuando un predictor de la siguiente línea apunta a grupos alineados de 2, 4 u 8 instrucciones, el destino de la bifurcación generalmente no será la primera instrucción capturada, por lo que las instrucciones iniciales capturadas se desperdician. Suponiendo, para simplificar, una distribución uniforme de los destinos de bifurcación, se descartan 0,5, 1,5 y 3,5 instrucciones capturadas, respectivamente.

Dado que la bifurcación en sí no suele ser la última instrucción de un grupo alineado, las instrucciones posteriores a la bifurcación ejecutada (o su intervalo de retardo ) se descartan. Una vez más, suponiendo una distribución uniforme de las ubicaciones de las instrucciones de bifurcación, se descartan 0,5, 1,5 y 3,5 instrucciones obtenidas.

Las instrucciones descartadas en las líneas de bifurcación y destino suman casi un ciclo de recuperación completo, incluso para un predictor de la siguiente línea de un solo ciclo.

El predictor de bifurcaciones de dos niveles, también conocido como predictor de bifurcaciones basado en correlación, utiliza una tabla bidimensional de contadores, también llamada "tabla de historial de patrones". Las entradas de la tabla son contadores de dos bits.

Predictor adaptativo de dos niveles

Si una ifinstrucción se ejecuta tres veces, la decisión tomada en la tercera ejecución podría depender de si las dos anteriores se ejecutaron o no. En tales casos, un predictor adaptativo de dos niveles funciona de manera más eficiente que un contador de saturación. Los saltos condicionales que se ejecutan cada dos veces o que presentan algún otro patrón recurrente no se predicen bien con el contador de saturación. Un predictor adaptativo de dos niveles recuerda el historial de las últimas n ocurrencias de la bifurcación y utiliza un contador de saturación para cada uno de los 2n posibles ^patrones de historial. Este método se ilustra en la figura 3.

Consideremos el ejemplo de n  = 2. Esto significa que las dos últimas ocurrencias de la rama se almacenan en un registro de desplazamiento de dos bits . Este registro de historial de rama puede tener cuatro valores binarios diferentes : 00, 01, 10 y 11, donde cero significa "no tomada" y uno significa "tomada". Una tabla de historial de patrones contiene cuatro entradas por rama, una para cada uno de los 2² ⁼  4 historiales de rama posibles, y cada entrada en la tabla contiene un contador de saturación de dos bits del mismo tipo que en la figura 2 para cada rama. El registro de historial de rama se utiliza para elegir cuál de los cuatro contadores de saturación utilizar. Si el historial es 00, se utiliza el primer contador; si el historial es 11, se utiliza el último de los cuatro contadores.

Supongamos, por ejemplo, que se realiza un salto condicional cada tres veces. La secuencia de bifurcación es 001001001... En este caso, la entrada número 00 en la tabla de historial de patrones pasará al estado "fuertemente tomada", lo que indica que después de dos ceros viene un uno. La entrada número 01 pasará al estado "fuertemente no tomada", lo que indica que después de 01 viene un cero. Lo mismo ocurre con la entrada número 10, mientras que la entrada número 11 nunca se utiliza porque nunca hay dos unos consecutivos.

La regla general para un predictor adaptativo de dos niveles con un historial de n bits es que puede predecir cualquier secuencia repetitiva con cualquier período si todas las subsecuencias de n bits son diferentes. ^{[ 9 ]}

La ventaja del predictor adaptativo de dos niveles es que puede aprender rápidamente a predecir un patrón repetitivo arbitrario. Este método fue inventado por T.-Y. Yeh y Yale Patt en la Universidad de Michigan . ^{[ 14 ]} Desde su publicación inicial en 1991, este método se ha vuelto muy popular y se utiliza en procesadores Pentium posteriores, como el Pentium MMX. ^{[ 15 ]} Variantes de este método de predicción se utilizan en la mayoría de los microprocesadores modernos.

Un predictor de bifurcación local tiene un búfer de historial independiente para cada instrucción de salto condicional. Puede utilizar un predictor adaptativo de dos niveles. El búfer de historial es independiente para cada instrucción de salto condicional, mientras que la tabla de historial de patrones también puede ser independiente o compartida entre todos los saltos condicionales.

Los procesadores Intel Pentium MMX , Pentium II y Pentium III cuentan con predictores de bifurcación locales con un historial local de 4 bits y una tabla de historial de patrones local con 16 entradas para cada salto condicional.

En los benchmarks SPEC '89, los predictores locales muy grandes se saturan al 97,1 % de precisión. ^{[ 12 ] : 6}

Un predictor de bifurcaciones global no guarda un registro histórico independiente para cada salto condicional. En su lugar, mantiene un historial compartido de todos los saltos condicionales. La ventaja de un historial compartido es que cualquier correlación entre diferentes saltos condicionales forma parte de la elaboración de las predicciones. La desventaja es que el historial se diluye con información irrelevante si los diferentes saltos condicionales no están correlacionados, y que el búfer de historial puede no incluir ningún bit de la misma bifurcación si existen muchas otras bifurcaciones intermedias. Puede utilizar un predictor adaptativo de dos niveles.

Este esquema es mejor que el esquema de contador de saturación solo para tablas de gran tamaño, y rara vez es tan bueno como la predicción local. El búfer de historial debe ser más largo para realizar una buena predicción. El tamaño de la tabla de historial de patrones crece exponencialmente con el tamaño del búfer de historial. Por lo tanto, la tabla de historial de patrones grande debe compartirse entre todos los saltos condicionales.

Un predictor adaptativo de dos niveles con búfer de historial compartido globalmente y tabla de historial de patrones se denomina predictor "gshare" si aplica la operación XOR al historial global y al PC de ramificación, y "gselect" si los concatena . La predicción de ramificación global se utiliza en procesadores AMD y en procesadores Intel Pentium M , Core , Core 2 y Atom basados ​​en Silvermont .

Un predictor de bifurcación aleado ^{[ 17 ]} combina los principios de predicción local y global mediante la concatenación de historiales de bifurcación locales y globales, posiblemente con algunos bits del contador de programa . Las pruebas indican que el procesador VIA Nano podría estar utilizando esta técnica. ^{[ 9 ]}

Un predictor de concordancia es un predictor adaptativo de dos niveles con un búfer de historial y una tabla de historial de patrones compartidos globalmente, y un contador de saturación local adicional. Las salidas de los predictores local y global se combinan mediante la operación XOR para obtener la predicción final. El objetivo es reducir las contenciones en la tabla de historial de patrones cuando dos ramas con predicciones opuestas comparten la misma entrada. ^{[ 18 ]}

Un predictor híbrido, también llamado predictor combinado, implementa más de un mecanismo de predicción. La predicción final se basa en un metapredictor que recuerda cuál de los predictores ha realizado las mejores predicciones en el pasado, o en una función de votación mayoritaria basada en un número impar de predictores diferentes.

Scott McFarling propuso la predicción de ramas combinadas en su artículo de 1993. ^{[ 12 ]}

En las pruebas de rendimiento SPEC'89, dicho predictor es prácticamente tan bueno como el predictor local.

Los predictores como gshare utilizan múltiples entradas de tabla para rastrear el comportamiento de cada rama. Esta multiplicación de entradas aumenta considerablemente la probabilidad de que dos ramas se asocien a la misma entrada de tabla (una situación denominada aliasing), lo que a su vez reduce significativamente la precisión de la predicción para dichas ramas. Una vez que se dispone de varios predictores, es conveniente que cada uno tenga patrones de aliasing diferentes, de modo que sea más probable que al menos uno de ellos no presente aliasing. Los predictores combinados con diferentes funciones de indexación se denominan predictores gskew y son análogos a las cachés asociativas sesgadas utilizadas para el almacenamiento en caché de datos e instrucciones.

Un salto condicional que controla un bucle se predice mejor con un predictor de bucles especial. Un salto condicional en la parte inferior de un bucle que se repite N veces se ejecutará N-1 veces y luego no se ejecutará una vez. Si el salto condicional se coloca en la parte superior del bucle, no se ejecutará N-1 veces y luego se ejecutará una vez. Un salto condicional que va muchas veces en una dirección y luego una vez en la otra se detecta como un comportamiento de bucle. Dicho salto condicional se puede predecir fácilmente con un contador simple. Un predictor de bucles forma parte de un predictor híbrido donde un metapredictor detecta si el salto condicional tiene comportamiento de bucle.

Una instrucción de salto indirecto puede elegir entre más de dos ramas. Algunos procesadores tienen predictores de ramas indirectas especializados. ^{[ 19 ] [ 20 ]} Los procesadores más recientes de Intel ^{[ 21 ]} y AMD ^{[ 22 ]} pueden predecir ramas indirectas mediante un predictor adaptativo de dos niveles. Este tipo de instrucción aporta más de un bit al búfer de historial. Los procesadores zEC12 y posteriores de la arquitectura z/ de IBM admiten una instrucción BRANCH PREDICTION PRELOAD que puede precargar la entrada del predictor de ramas para una instrucción dada con una dirección de destino de rama construida sumando el contenido de un registro de propósito general a un valor de desplazamiento inmediato. ^{[ 23 ] [ 24 ]}

Los procesadores que no cuentan con este mecanismo simplemente predecirán un salto indirecto para ir al mismo destino que la última vez. ^{[ 9 ]}

Una función normalmente regresa al lugar desde donde fue llamada. La instrucción de retorno es un salto indirecto que lee su dirección de destino de la pila de llamadas . Muchos microprocesadores tienen un mecanismo de predicción independiente para las instrucciones de retorno. Este mecanismo se basa en un búfer de pila de retorno , que es una copia local de la pila de llamadas. El tamaño del búfer de pila de retorno suele ser de 4 a 16 entradas. ^{[ 9 ]}

La disyuntiva entre una predicción de bifurcaciones rápida y una buena predicción se resuelve a veces mediante el uso de dos predictores de bifurcaciones. El primer predictor es rápido y sencillo. El segundo, más lento, complejo y con tablas más grandes, anulará cualquier predicción errónea realizada por el primero.

Los microprocesadores Alpha 21264 y Alpha EV8 utilizaban un predictor de siguiente línea rápido de un solo ciclo para gestionar la recurrencia del destino de la bifurcación y proporcionar una predicción de bifurcación sencilla y rápida. Debido a la imprecisión del predictor de siguiente línea y al tiempo que tarda la resolución de la bifurcación, ambos núcleos cuentan con predictores de bifurcación secundarios de dos ciclos que pueden anular la predicción del predictor de siguiente línea a costa de perder un ciclo de búsqueda.

El Intel Core i7 tiene dos búferes de destino de bifurcación y posiblemente dos o más predictores de bifurcación. ^{[ 25 ]}

El aprendizaje automático para la predicción de bifurcaciones utilizando LVQ y perceptrones multicapa , denominado " predicción neuronal de bifurcaciones", fue propuesto por Lucian Vintan ( Universidad Lucian Blaga de Sibiu ). ^{[ 26 ]} Un año después desarrolló el predictor de bifurcaciones basado en perceptrones. ^{[ 27 ]} La investigación sobre el predictor neuronal de bifurcaciones fue desarrollada mucho más por Daniel Jiménez. ^{[ 28 ]} En 2001, ^{[ 28 ]} se presentó el primer predictor basado en perceptrones que era factible de implementar en hardware. La primera implementación comercial de un predictor de bifurcaciones basado en perceptrones se realizó en la microarquitectura Piledriver de AMD . ^{[ 29 ]}

La principal ventaja del predictor neuronal es su capacidad para explotar historiales extensos, requiriendo únicamente un crecimiento lineal de los recursos. Los predictores clásicos requieren un crecimiento exponencial de los recursos. Jiménez reporta una mejora global del 5,7 % con respecto a un predictor híbrido de estilo McFarling. ^{[ 30 ]} También utilizó un perceptrón gshare que anulaba los predictores híbridos. ^{[ 30 ]}

La principal desventaja del predictor perceptrón es su alta latencia. Incluso aprovechando técnicas aritméticas de alta velocidad, la latencia de cálculo es relativamente alta en comparación con el período de reloj de muchas microarquitecturas modernas. Para reducir la latencia de predicción, Jiménez propuso en 2003 el predictor neuronal de ruta rápida , donde el predictor perceptrón elige sus pesos según la ruta de la rama actual, en lugar de según el PC de la rama. Muchos otros investigadores desarrollaron este concepto (A. Seznec, M. Monchiero, D. Tarjan y K. Skadron, V. Desmet, Akkary et al., K. Aasaraai, Michael Black, etc.).

La mayoría de los predictores de bifurcaciones más avanzados utilizan un predictor perceptrón (véase la "Competencia de predicción de bifurcaciones del campeonato" de Intel ^{[ 31 ]} ). Intel ya implementa esta idea en uno de los simuladores del IA-64 (2003). ^{[ 32 ]}

El Infinity Fabric del procesador multinúcleo AMD Ryzen ^{[ 33 ] [ 34 ] [ 35 ]} y los procesadores Samsung Exynos incluyen predictores de ramificación neuronal basados ​​en perceptrones.