En arquitectura de computadoras , un predictor de rama [1] [2] [3] [4] [5] es un circuito digital que intenta adivinar en qué dirección irá una rama (por ejemplo, una estructura si-entonces-si no ) antes de que esto sea conocido definitivamente. El propósito del predictor de bifurcación es mejorar el flujo en la canalización de instrucciones . Los predictores de rama desempeñan un papel fundamental para lograr un alto rendimiento en muchas arquitecturas modernas de microprocesadores canalizados .
La bifurcación bidireccional generalmente se implementa con una instrucción de salto condicional . Un salto condicional se puede "realizar" y saltar a un lugar diferente en la memoria del programa, o se puede "no realizar" y continuar la ejecución inmediatamente después del salto condicional. No se sabe con certeza si se realizará o no un salto condicional hasta que se haya calculado la condición y el salto condicional haya pasado la etapa de ejecución en el canal de instrucciones (ver figura 1).
Sin predicción de bifurcación, el procesador tendría que esperar hasta que la instrucción de salto condicional haya pasado la etapa de ejecución antes de que la siguiente instrucción pueda ingresar a la etapa de búsqueda en la tubería. El predictor de rama intenta evitar esta pérdida de tiempo intentando adivinar si es más probable que se realice o no el salto condicional. La rama que se supone que es la más probable se recupera y se ejecuta especulativamente . Si más tarde se detecta que la suposición fue incorrecta, entonces las instrucciones ejecutadas especulativamente o parcialmente ejecutadas se descartan y la canalización comienza de nuevo con la rama correcta, lo que incurre en un retraso.
El tiempo que se pierde en caso de una predicción errónea de una rama es igual al número de etapas en el proceso desde la etapa de recuperación hasta la etapa de ejecución. Los microprocesadores modernos tienden a tener canales bastante largos, por lo que el retraso en la predicción errónea es de entre 10 y 20 ciclos de reloj . Como resultado, alargar un proceso aumenta la necesidad de un predictor de sucursales más avanzado. [6]
La primera vez que se encuentra una instrucción de salto condicional, no hay mucha información en la que basar una predicción. Pero el predictor de sucursales mantiene registros de si las sucursales se toman o no. Cuando encuentra un salto condicional que se ha visto varias veces antes, puede basar la predicción en el historial. El predictor de rama puede, por ejemplo, reconocer que el salto condicional se realiza la mayoría de las veces, o que se realiza cada dos veces.
La predicción de rama no es lo mismo que la predicción de objetivo de rama . La predicción de rama intenta adivinar si se realizará o no un salto condicional. La predicción del objetivo de rama intenta adivinar el objetivo de un salto condicional o incondicional antes de calcularlo decodificando y ejecutando la instrucción misma. La predicción de rama y la predicción de objetivo de rama a menudo se combinan en el mismo circuito.
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 ) utilizaban predicción de rama estática unidireccional: siempre predicen que no se realizará un salto condicional, por lo que siempre obtienen la siguiente instrucción secuencial. Sólo cuando se evalúa la bifurcación o el salto y se determina que se ha realizado, el puntero de instrucción se establece en una dirección no secuencial.
Ambas CPU evalúan ramas en la etapa de decodificación y tienen una búsqueda de instrucciones de un solo ciclo. Como resultado, la recurrencia del objetivo de la bifurcación tiene una duración de dos ciclos y la máquina siempre recupera la instrucción inmediatamente después de cualquier bifurcación realizada. Ambas arquitecturas definen ranuras de retardo de rama para utilizar estas instrucciones recuperadas.
Una forma más avanzada de predicción estática supone que se tomarán ramas hacia atrás y no hacia adelante. Una rama hacia atrás es aquella que tiene una dirección de destino inferior a su propia dirección. Esta técnica puede ayudar con la precisión de la predicción de los bucles, que generalmente son ramas que apuntan hacia atrás y se toman la mayoría de las veces.
Algunos procesadores permiten que se inserten sugerencias de predicción de rama en el código para indicar si la predicción estática debe tomarse o no. El Intel Pentium 4 acepta sugerencias de predicción de ramas, pero esta característica se abandonó en los procesadores Intel posteriores. [8]
La predicción estática se utiliza como técnica alternativa en algunos procesadores con predicción de rama dinámica cuando los predictores dinámicos no tienen suficiente información para usar. Tanto el Motorola MPC7450 (G4e) como el Intel Pentium 4 utilizan esta técnica como alternativa. [9]
En la predicción estática, todas las decisiones se toman en tiempo de compilación, antes de la ejecución del programa. [10]
La predicción de rama dinámica [2] utiliza información sobre ramas tomadas o no tomadas recopilada en tiempo de ejecución para predecir el resultado de una rama. [1]
El uso de un bit aleatorio o pseudoaleatorio (una suposición pura) garantizaría a cada rama una tasa de predicción correcta del 50%, que no se puede mejorar (ni empeorar) reordenando las instrucciones. (Con la predicción estática más simple de "suponer toma", los compiladores pueden reordenar las instrucciones para obtener una predicción correcta superior al 50%). Además, haría que el tiempo sea [mucho más] no determinista.
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 siguiente línea maneja la predicción del objetivo de la rama , así como la predicción de la dirección de la rama.
Cuando un predictor de siguiente línea apunta a grupos alineados de 2, 4 u 8 instrucciones, el objetivo de la bifurcación generalmente no será la primera instrucción recuperada, por lo que las instrucciones iniciales obtenidas se desperdician. Suponiendo por simplicidad, una distribución uniforme de los objetivos de bifurcación, se descartan 0,5, 1,5 y 3,5 instrucciones recuperadas, respectivamente.
Dado que la bifurcación en sí generalmente no será la última instrucción en un grupo alineado, las instrucciones posteriores a la bifurcación tomada (o su ranura de retraso ) se descartarán. Una vez más, suponiendo una distribución uniforme de las ubicaciones de instrucciones de rama, se descartan 0,5, 1,5 y 3,5 instrucciones recuperadas.
Las instrucciones descartadas en las líneas de rama y destino suman casi un ciclo de recuperación completo, incluso para un predictor de siguiente línea de ciclo único.
Un contador de saturación de 1 bit (esencialmente un flip-flop ) registra el último resultado de la rama. Esta es la versión más simple posible del predictor de rama dinámica, aunque no es muy precisa.
Un contador de saturación de 2 bits [1] es una máquina de estados con cuatro estados:
Cuando se evalúa una rama, se actualiza la máquina de estado correspondiente. Las ramas evaluadas como no tomadas cambian el estado a fuertemente no tomadas, y las ramas evaluadas como tomadas cambian el estado a fuertemente ocupadas. La ventaja del esquema de contador de dos bits sobre el esquema de un bit es que un salto condicional tiene que desviarse dos veces de lo que más ha hecho en el pasado antes de que cambie la predicción. Por ejemplo, un salto condicional de cierre de bucle se predice erróneamente una vez en lugar de dos.
El procesador Intel Pentium original, que no es MMX , utiliza un contador de saturación, aunque con una implementación imperfecta. [8]
En los puntos de referencia SPEC '89, los predictores bimodales muy grandes se saturan con un 93,5% de precisión, una vez que cada rama se asigna a un contador único. [11] : 3
La tabla de predicción está indexada con los bits de dirección de instrucción , de modo que el procesador pueda obtener una predicción para cada instrucción antes de decodificarla.
El predictor de rama de dos niveles, también conocido como predictor de rama basado en correlación, utiliza una tabla de contadores bidimensional, también llamada "tabla de historial de patrones". Las entradas de la tabla son contadores de dos bits.
Si una ifdeclaración se ejecuta tres veces, la decisión que se tome en la tercera ejecución podría depender de si se tomaron o no las dos anteriores. En tales escenarios, un predictor adaptativo de dos niveles funciona de manera más eficiente que un contador de saturación. El contador de saturación no predice bien los saltos condicionales que se realizan cada dos veces o que tienen algún otro patrón que se repite regularmente. Un predictor adaptativo de dos niveles recuerda el historial de las últimas n apariciones de la rama y utiliza un contador de saturación para cada uno de los 2 n patrones históricos posibles. Este método se ilustra en la figura 3.
Considere el ejemplo de n = 2. Esto significa que las dos últimas apariciones de la rama se almacenan en un registro de desplazamiento de dos bits . Este registro de historial de sucursales puede tener cuatro valores binarios diferentes , 00, 01, 10 y 11, donde cero significa "no tomado" y uno significa "tomado". Una tabla de historial de patrones contiene cuatro entradas por rama, una para cada uno de los 2 2 = 4 posibles historiales de rama, y cada entrada de la tabla contiene un contador de saturación de dos bits del mismo tipo que en la figura 2 para cada rama. El registro del historial de sucursales se utiliza para elegir cuál de los cuatro contadores de saturación usar. Si el historial es 00, entonces 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 rama es 001001001... En este caso, la entrada número 00 en la tabla del historial de patrones pasará al estado "fuertemente tomado", lo que indica que después de dos ceros viene un uno. La entrada número 01 pasará al estado "totalmente 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 consecutivas.
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. [8]
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 . [13] Desde la publicación inicial en 1991, este método se ha vuelto muy popular. En la mayoría de los microprocesadores modernos se utilizan variantes de este método de predicción. [ cita necesaria ]
Se ha propuesto un predictor de rama de dos niveles donde el segundo nivel se reemplaza con una red neuronal . [14]
Un predictor de rama 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 está separado para cada instrucción de salto condicional, mientras que la tabla de historial de patrones también puede estar separada o puede compartirse entre todos los saltos condicionales.
Los Intel Pentium MMX , Pentium II y Pentium III tienen predictores de sucursales 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 puntos de referencia SPEC '89, los predictores locales muy grandes se saturan con un 97,1% de acierto. [11] : 6
Un predictor de rama global no mantiene un registro histórico separado para cada salto condicional. En lugar de eso, mantiene un historial compartido de todos los saltos condicionales. La ventaja de una historia compartida es que cualquier correlación entre diferentes saltos condicionales es parte de la realización de 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 del historial puede no incluir ningún bit de la misma rama si hay muchas otras ramas intermedias. Puede utilizar un predictor adaptativo de dos niveles.
Este esquema es mejor que el esquema de contador de saturación sólo para tablas de gran tamaño y rara vez es tan bueno como la predicción local. El buffer del historial debe ser más largo para poder hacer 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 grandes debe compartirse entre todos los saltos condicionales.
Un predictor adaptativo de dos niveles con un búfer de historial compartido globalmente y una tabla de historial de patrones se denomina predictor "gshare" si valora el historial global y la rama de PC, y "gselect" si los concatena . La predicción de rama global se utiliza en los procesadores AMD y en los procesadores Atom basados en Intel Pentium M , Core , Core 2 y Silvermont .
Un predictor de ramas aleado [15] combina los principios de predicción local y global concatenando historiales de ramas locales y globales, posiblemente también con algunos bits del contador del programa . Las pruebas indican que el procesador VIA Nano puede estar utilizando esta técnica. [8]
Un predictor de acuerdo es un predictor adaptativo de dos niveles con un búfer de historial compartido globalmente y una tabla de historial de patrones, y un contador de saturación local adicional. Las salidas de los predictores locales y globales se realizan mediante operación XOR entre sí para dar la predicción final. El propósito es reducir las disputas en la tabla de historial de patrones donde dos ramas con predicción opuesta comparten la misma entrada en la tabla de historial de patrones. [dieciséis]
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 hecho las mejores predicciones en el pasado, o en una función de voto mayoritario basada en un número impar de predictores diferentes.
Scott McFarling propuso la predicción de ramas combinadas en su artículo de 1993. [11]
En los puntos de referencia SPEC'89, un predictor de este tipo es tan bueno como el predictor local. [ cita necesaria ]
Los predictores como gshare utilizan múltiples entradas de tabla para rastrear el comportamiento de cualquier rama en particular. Esta multiplicación de entradas hace que sea mucho más probable que dos ramas se asignen a la misma entrada de la tabla (una situación llamada aliasing), lo que a su vez hace que sea mucho más probable que la precisión de la predicción se vea afectada para esas ramas. Una vez que tenga varios predictores, es beneficioso disponer que cada predictor tenga diferentes patrones de alias, de modo que sea más probable que al menos un predictor no tenga alias. Los predictores combinados con diferentes funciones de indexación para los diferentes predictores se denominan predictores gskew y son análogos a los cachés asociativos sesgados utilizados para el almacenamiento en caché de datos e instrucciones.
Un salto condicional que controla un bucle se predice mejor con un predictor de bucle especial. Un salto condicional en la parte inferior de un bucle que se repite N veces se realizará N-1 veces y luego no se realizará una vez. Si el salto condicional se coloca en la parte superior del bucle, no se realizará N-1 veces y luego se realizará una vez. Se detecta que un salto condicional que va muchas veces en una dirección y luego en la otra dirección tiene un comportamiento de bucle. Un salto condicional de este tipo se puede predecir fácilmente con un simple contador. Un predictor de bucle es parte de un predictor híbrido donde un metapredictor detecta si el salto condicional tiene un 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. [17] [18] Los procesadores más nuevos de Intel [19] y AMD [20] pueden predecir ramas indirectas mediante el uso de un predictor adaptativo de dos niveles. Este tipo de instrucción contribuye con más de un bit al búfer histórico. Los procesadores zEC12 y posteriores z/Architecture de IBM admiten una instrucción BRANCH PREDICTION PRELOAD que puede precargar la entrada del predictor de rama para una instrucción dada con una dirección de destino de rama construida agregando el contenido de un registro de propósito general a un valor de desplazamiento inmediato. [21] [22]
Los procesadores sin este mecanismo simplemente predecirán un salto indirecto para ir al mismo objetivo que la última vez. [8]
Una función normalmente volverá 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 devolución. Este mecanismo se basa en el llamado búfer de pila de retorno , que es un espejo local de la pila de llamadas. El tamaño del búfer de la pila de retorno suele ser de 4 a 16 entradas. [8]
El equilibrio entre una predicción de rama rápida y una buena predicción de rama a veces se resuelve teniendo dos predictores de rama. El primer predictor de rama es rápido y sencillo. El segundo predictor de rama, que es más lento, más complicado y con tablas más grandes, anulará una predicción posiblemente incorrecta realizada por el primer predictor.
Los microprocesadores Alpha 21264 y Alpha EV8 utilizaron un predictor rápido de siguiente línea de ciclo único para manejar la recurrencia del objetivo de rama y proporcionar una predicción de rama simple y rápida. Debido a que el predictor de la siguiente línea es tan inexacto y la recurrencia de la resolución de la rama tarda tanto, ambos núcleos tienen predictores de rama secundarios de dos ciclos que pueden anular la predicción del predictor de la siguiente línea a costa de un único ciclo de recuperación perdido.
El Intel Core i7 tiene dos búferes de destino de rama y posiblemente dos o más predictores de rama. [23]
Lucian Vintan ( Universidad Lucian Blaga de Sibiu ) propuso el aprendizaje automático para la predicción de ramas utilizando LVQ y perceptrones multicapa , llamado " predicción de ramas neuronales " . [24] Un año más tarde desarrolló el predictor de rama del perceptrón. [25] La investigación sobre predictores de ramas neuronales fue desarrollada mucho más por Daniel Jiménez. [26] En 2001, [26] se presentó el primer predictor de perceptrón que era factible de implementar en hardware. La primera implementación comercial de un predictor de rama de perceptrón fue en la microarquitectura Piledriver de AMD . [27]
La principal ventaja del predictor neuronal es su capacidad para explotar historias largas mientras requiere solo un crecimiento lineal de recursos. Los predictores clásicos requieren un crecimiento exponencial de los recursos. Jiménez informa una mejora global del 5,7% con respecto a un predictor híbrido estilo McFarling. [28] También utilizó un gshare/perceptrón que anula los predictores híbridos. [28]
La principal desventaja del predictor de perceptrón es su alta latencia. Incluso después de aprovechar los trucos aritméticos 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 del perceptrón elige sus pesos de acuerdo con la ruta de la rama actual, en lugar de según la PC de la rama. Muchos otros investigadores desarrollaron este concepto (A. Seznec, M. Monchiero, D. Tarjan & K. Skadron, V. Desmet, Akkary et al., K. Aasaraai, Michael Black, etc.). [ cita necesaria ]
La mayoría de los predictores de ramas de última generación utilizan un predictor de perceptrón (consulte el "Competencia de predicción de ramas de campeonato" de Intel [29] ). Intel ya implementa esta idea en uno de los simuladores del IA-64 (2003). [30]
Infinity Fabric del procesador multinúcleo AMD Ryzen [31] [32] [33] y el procesador Samsung Exynos incluyen un predictor de rama neuronal basado en perceptrón.
El IBM 7030 Stretch , diseñado a finales de la década de 1950, ejecuta previamente todas las ramas incondicionales y cualquier rama condicional que dependiera de los registros de índice. Para otras ramas condicionales, los dos primeros modelos de producción implementados predicen no consumidos; Los modelos posteriores se cambiaron para implementar predicciones basadas en los valores actuales de los bits indicadores (correspondientes a los códigos de condición actuales). [34] Los diseñadores de Stretch habían considerado bits de sugerencias estáticas en las instrucciones de la rama al principio del proyecto, pero decidieron no hacerlo. La recuperación de predicciones erróneas fue proporcionada por la unidad de anticipación en Stretch, y parte de la reputación de Stretch por su desempeño no tan estelar se atribuyó al tiempo requerido para la recuperación de predicciones erróneas. Los diseños posteriores de grandes computadoras de IBM no utilizaron predicción de ramas con ejecución especulativa hasta la IBM 3090 en 1985.
Los predictores de dos bits fueron introducidos por Tom McWilliams y Curt Widdoes en 1977 para la supercomputadora S-1 del Laboratorio Nacional Lawrence Livermore y de forma independiente por Jim Smith en 1979 en los CDC. [35]
Los procesadores microprogramados, populares entre los años 1960 y 1980 y más allá, requerían múltiples ciclos por instrucción y, en general, no requerían predicción de rama. Sin embargo, además del IBM 3090, hay varios otros ejemplos de diseños microprogramados que incorporaron predicción de rama.
La Burroughs B4900 , una máquina COBOL microprogramada lanzada alrededor de 1982, fue canalizada y utilizó predicción de ramas. El estado del historial de predicción de bifurcaciones B4900 se almacena nuevamente en las instrucciones en memoria durante la ejecución del programa. El B4900 implementa predicción de rama de 4 estados mediante el uso de 4 códigos de operación de rama semánticamente equivalentes para representar cada tipo de operador de rama. El código de operación utilizado indicó el historial de esa instrucción de bifurcación en particular. Si el hardware determina que es necesario actualizar el estado de predicción de una rama en particular, reescribe el código de operación con el código de operación semánticamente equivalente que indica el historial adecuado. Este esquema obtiene una tasa de acierto del 93%. Se concedieron la patente estadounidense 4.435.756 y otras sobre este plan.
El DEC VAX 9000 , anunciado en 1989, está microprogramado y canalizado, y realiza predicciones de ramas. [36]
Los primeros procesadores RISC comerciales, los MIPS R2000 y R3000 y los anteriores procesadores SPARC , sólo hacen predicciones triviales de ramas "no tomadas". Debido a que utilizan ranuras de retardo de bifurcación, obtienen solo una instrucción por ciclo y se ejecutan en orden, no hay pérdida de rendimiento. El R4000 posterior utiliza la misma predicción trivial de rama "no tomada" y pierde dos ciclos en cada rama tomada porque la recurrencia de la resolución de la rama tiene una duración de cuatro ciclos.
La predicción de ramas se volvió más importante con la introducción de procesadores superescalares canalizados como Intel Pentium , DEC Alpha 21064 , MIPS R8000 y la serie IBM POWER . Todos estos procesadores se basan en predictores bimodales simples o de un bit.
El DEC Alpha 21264 (EV6) utiliza un predictor de siguiente línea anulado por un predictor local y un predictor global combinados, donde la elección combinada la realiza un predictor bimodal. [37]
El AMD K8 tiene un predictor bimodal y global combinado, donde la elección combinada es otro predictor bimodal. Este procesador almacena en caché los contadores predictores bimodales base y de elección en bits de la caché L2 que de otro modo se usaría para ECC. Como resultado, tiene efectivamente tablas base y de predicción de opciones muy grandes, y paridad en lugar de ECC en las instrucciones en la caché L2. El diseño de paridad es suficiente, ya que cualquier instrucción que sufra un error de paridad puede invalidarse y recuperarse de la memoria.
El Alpha 21464 [37] (EV8, cancelado tarde en el diseño) tenía una penalización mínima por error de predicción de rama de 14 ciclos. Se trataba de utilizar un predictor de siguiente línea complejo pero rápido anulado por un predictor combinado bimodal y de voto mayoritario. La mayoría de votos fue entre los predictores bimodales y dos gskew.
En 2018, el Proyecto Cero de Google y otros investigadores hicieron pública una vulnerabilidad de seguridad catastrófica llamada Spectre . La vulnerabilidad , que afecta prácticamente a todas las CPU modernas , implica preparar los predictores de rama para que otro proceso (o el núcleo) prediga erróneamente una rama y utilice datos secretos como índice de matriz, expulsando una de las líneas de caché del atacante. El atacante puede cronometrar el acceso a su propia matriz para descubrir cuál, convirtiendo este estado interno (microarquitectónico) de la CPU en un valor que el atacante puede guardar y que contiene información sobre valores que no pudo leer directamente. [38]