En arquitectura informática , un predictor de bifurcación [1] [2] [3] [4] [5] es un circuito digital que intenta adivinar en qué dirección irá una bifurcación (por ejemplo, una estructura if-then-else ) antes de que esto se conozca definitivamente. El propósito del predictor de bifurcación es mejorar el flujo en la secuencia de instrucciones . Los predictores de bifurcación desempeñan un papel fundamental para lograr un alto rendimiento en muchas arquitecturas de microprocesadores segmentados modernos .
La bifurcación bidireccional se suele implementar con una instrucción de salto condicional . Un salto condicional puede "realizarse" y saltar a un lugar diferente en la memoria del programa, o puede "no realizarse" 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 la secuencia de instrucciones (consulte la figura 1).
Sin la predicción de saltos, 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 el pipeline. El predictor de saltos intenta evitar esta pérdida de tiempo al intentar adivinar si es más probable que se realice el salto condicional o no. Luego, se obtiene el salto que se supone que es el más probable y se ejecuta de manera especulativa . Si más tarde se detecta que la suposición fue incorrecta, entonces las instrucciones ejecutadas de manera especulativa o parcialmente ejecutadas se descartan y el pipeline comienza de nuevo con el salto correcto, lo que genera una demora.
El tiempo que se pierde en caso de una predicción errónea de una rama es igual al número de etapas de la secuencia de comandos desde la etapa de obtención hasta la etapa de ejecución. Los microprocesadores modernos tienden a tener secuencias de comandos bastante largas, de modo que el retraso de una predicción errónea es de entre 10 y 20 ciclos de reloj . Como resultado, hacer una secuencia de comandos más larga aumenta la necesidad de un predictor de ramas 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 saltos mantiene registros de si se toman o no saltos. Cuando encuentra un salto condicional que se ha visto varias veces antes, puede basar la predicción en el historial. El predictor de saltos puede, por ejemplo, reconocer que el salto condicional se toma con más frecuencia que no, o que se toma cada dos veces.
La predicción de salto no es lo mismo que la predicción de objetivo de salto . La predicción de salto intenta adivinar si se realizará un salto condicional o no. La predicción de objetivo de salto intenta adivinar el objetivo de un salto condicional o incondicional realizado antes de que se calcule decodificando y ejecutando la instrucción en sí. La predicción de salto y la predicción de objetivo de salto a menudo se combinan en el mismo circuito.
La predicción estática es la técnica de predicción de bifurcaciones más sencilla porque no se basa en información sobre el historial dinámico de la ejecución del código, sino que 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 bifurcación estática unidireccional: siempre predicen que no se realizará un salto condicional, por lo que siempre obtienen la siguiente instrucción secuencial. Solo cuando se evalúa la bifurcación o el salto y se determina que se realizó, el puntero de instrucción se establece en una dirección no secuencial.
Ambas CPU evalúan las bifurcaciones en la etapa de decodificación y tienen una única instrucción de ciclo de búsqueda. Como resultado, la recurrencia del objetivo de la bifurcación tiene una duración de dos ciclos y la máquina siempre busca la instrucción inmediatamente después de cualquier bifurcación realizada. Ambas arquitecturas definen intervalos de retardo de bifurcación para utilizar estas instrucciones buscadas.
Una forma más avanzada de predicción estática presupone que se tomarán las ramas hacia atrás y que no las ramas hacia adelante. Una rama hacia atrás es aquella que tiene una dirección de destino que es inferior a su propia dirección. Esta técnica puede ayudar con la precisión de la predicción de bucles, que suelen ser ramas que apuntan hacia atrás y que se toman con más frecuencia que las que no se toman.
Algunos procesadores permiten insertar sugerencias de predicción de saltos en el código para indicar si se debe tomar o no la predicción estática. El procesador Intel Pentium 4 acepta sugerencias de predicción de saltos, pero esta función se abandonó en los procesadores Intel posteriores. [8]
La predicción estática se utiliza como técnica de respaldo en algunos procesadores con predicción de ramificación 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 técnica de respaldo. [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 dinámica de ramas [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 "asumir toma", los compiladores pueden reordenar las instrucciones para obtener una predicción correcta mejor que el 50%). Además, haría que la sincronización fuera [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 línea siguiente. Este predictor de la siguiente línea se encarga de la predicción del objetivo de la bifurcación , así como de la predicción de la dirección de la bifurcación.
Cuando un predictor de la siguiente línea apunta a grupos alineados de 2, 4 u 8 instrucciones, el objetivo de la bifurcación normalmente no será la primera instrucción obtenida, por lo que las instrucciones iniciales obtenidas se desperdician. Suponiendo, para simplificar, una distribución uniforme de los objetivos de bifurcación, se descartan 0,5, 1,5 y 3,5 instrucciones obtenidas, respectivamente.
Dado que la bifurcación en sí no suele ser la última instrucción en un grupo alineado, las instrucciones posteriores a la bifurcación tomada (o su intervalo de retardo ) se descartarán. 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 extraídas.
Las instrucciones descartadas en las líneas de destino y de ramificación suman casi un ciclo de búsqueda completo, incluso para un predictor de siguiente línea de un solo ciclo.
Un contador de saturación de 1 bit (esencialmente un flip-flop ) registra el último resultado de la bifurcación. Esta es la versión más simple posible de un predictor de bifurcación 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 estados correspondiente. Las ramas evaluadas como no tomadas cambian el estado hacia fuertemente no tomadas, y las ramas evaluadas como tomadas cambian el estado hacia fuertemente tomadas. La ventaja del esquema de contador de dos bits sobre un esquema de un bit es que un salto condicional tiene que desviarse dos veces de lo que ha hecho más en el pasado antes de que la predicción cambie. Por ejemplo, un salto condicional de cierre de bucle se predice incorrectamente una vez en lugar de dos.
El procesador Intel Pentium original, no 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 aciertos, una vez que cada rama se asigna a un contador único. [11] : 3
La tabla de predictores 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 que se decodifique la instrucción.
El predictor de bifurcación de dos niveles, también conocido como predictor de bifurcación 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 ifsentencia se ejecuta tres veces, la decisión que se tome en la tercera ejecución podría depender de si se ejecutaron las dos anteriores o no. En tales escenarios, 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 tienen algún otro patrón recurrente de manera regular no son predichos bien por el contador de saturación. Un predictor adaptativo de dos niveles recuerda el historial de las últimas n ocurrencias de la rama y utiliza un contador de saturación para cada uno de los 2 n patrones de historial posibles. Este método se ilustra en la figura 3.
Consideremos el ejemplo de n = 2. Esto significa que las dos últimas ocurrencias de la bifurcación se almacenan en un registro de desplazamiento de dos bits. Este registro de historial de bifurcaciones 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 bifurcación, una para cada una de las 2 2 = 4 posibles historias de bifurcaciones, 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 bifurcación. El registro de historial de bifurcaciones 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 ramificación es 001001001... En este caso, la entrada número 00 en la tabla de historial de patrones pasará al estado "fuertemente realizada", lo que indica que después de dos ceros viene un uno. La entrada número 01 pasará al estado "fuertemente no realizada", 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. [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 su publicación inicial en 1991, este método se ha vuelto muy popular. Las variantes de este método de predicción se utilizan en la mayoría de los microprocesadores modernos. [ cita requerida ]
Se ha propuesto un predictor de rama de dos niveles donde el segundo nivel se reemplaza por una red neuronal . [14]
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 puede ser compartida entre todos los saltos condicionales.
Los procesadores Intel Pentium MMX , Pentium II y Pentium III tienen 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 puntos de referencia SPEC '89, los predictores locales muy grandes se saturan con un 97,1 % de precisión. [11] : 6
Un predictor de bifurcación global no mantiene un registro histórico independiente para cada salto condicional, sino que 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 histórico puede no incluir ningún bit de la misma bifurcación si hay 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 tamaños de tabla grandes, y rara vez es tan bueno como la predicción local. El búfer de historial debe ser más largo para 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 gran tabla de historial de patrones 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 realiza una operación xor del historial global y la rama PC, y "gselect" si los concatena . La predicción de rama 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 aleada [15] combina los principios de predicción local y global mediante la concatenación de historiales de bifurcaciones locales y globales, posiblemente también con algunos bits del contador de 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 combinan entre sí mediante XOR para obtener la predicción final. El propósito es reducir las contenciones en la tabla de historial de patrones donde dos ramas con predicciones opuestas comparten la misma entrada en la tabla de historial de patrones. [16]
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 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, dicho predictor es casi tan bueno como el predictor local. [ cita requerida ]
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 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 múltiples predictores, es beneficioso organizar que cada predictor tenga diferentes patrones de aliasing, de modo que sea más probable que al menos un predictor no tenga aliasing. Los predictores combinados con diferentes funciones de indexación para los diferentes predictores se denominan predictores gskew y son análogos a las cachés asociativas sesgadas que se utilizan 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 repetirá N-1 veces y luego no se repetirá ni una vez. Si el salto condicional se coloca en la parte superior del bucle, no se repetirá N-1 veces y luego se repetirá una vez. Un salto condicional que va muchas veces en un sentido y luego en el otro una vez se detecta como que tiene un comportamiento de bucle. Un salto condicional de este tipo se puede predecir fácilmente con un contador simple. 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 ramificaciones. Algunos procesadores tienen predictores de ramificación indirecta especializados. [17] [18] Los procesadores más nuevos de Intel [19] y AMD [20] pueden predecir ramificaciones indirectas mediante un predictor adaptativo de dos niveles. Este tipo de instrucción contribuye con más de un bit al búfer de historial. Los procesadores zEC12 y posteriores z/Architecture de IBM admiten una instrucción BRANCH PREDICTION PRELOAD que puede precargar la entrada del predictor de ramificación para una instrucción dada con una dirección de destino de ramificación 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 retornará al lugar desde el que fue llamada. La instrucción de retorno es un salto indirecto que lee su dirección de destino desde la pila de llamadas . Muchos microprocesadores tienen un mecanismo de predicción independiente para las instrucciones de retorno. Este mecanismo se basa en un denominado búfer de pila de retorno , que es un espejo local de la pila de llamadas. El tamaño del búfer de pila de retorno es típicamente de 4 a 16 entradas. [8]
El equilibrio entre una predicción rápida de las ramificaciones y una predicción buena de las ramificaciones a veces se soluciona con dos predictores de ramificaciones. El primer predictor de ramificaciones es rápido y simple. El segundo predictor de ramificaciones, que es más lento, más complicado y con tablas más grandes, anulará una predicción posiblemente errónea realizada por el primer predictor.
Los microprocesadores Alpha 21264 y Alpha EV8 utilizaron un predictor de próxima línea de un solo ciclo rápido para manejar la recurrencia del objetivo de la bifurcación y proporcionar una predicción de bifurcación simple y rápida. Debido a que el predictor de próxima línea es tan impreciso y la recurrencia de resolución de bifurcación toma tanto tiempo, ambos núcleos tienen predictores de bifurcación secundarios de dos ciclos que pueden anular la predicción del predictor de próxima línea a costa de perder un solo ciclo de búsqueda.
El Intel Core i7 tiene dos buffers de destino de bifurcación y posiblemente dos o más predictores de bifurcación. [23]
El aprendizaje automático para la predicción de ramas utilizando LVQ y perceptrones multicapa , llamado " predicción de ramas neuronales ", fue propuesto por Lucian Vintan ( Universidad Lucian Blaga de Sibiu ). [24] Un año después desarrolló el predictor de ramas del perceptrón. [25] La investigación del predictor 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 ramas del perceptrón fue en la microarquitectura Piledriver de AMD . [27]
La principal ventaja del predictor neuronal es su capacidad de explotar largas historias mientras que requiere solamente un crecimiento lineal de los 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 de estilo McFarling. [28] También utilizó un gshare/perceptrón que anulaba los predictores híbridos. [28]
La principal desventaja del predictor 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 perceptrón elige sus pesos de acuerdo con 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.). [ cita requerida ]
La mayoría de los predictores de ramificaciones de última generación utilizan un predictor perceptrón (véase el concurso de predicción de ramificaciones de Intel [29] ). Intel ya implementa esta idea en uno de los simuladores de IA-64 (2003). [30]
El 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 los años 1950, preejecuta todas las bifurcaciones incondicionales y todas las bifurcaciones condicionales que dependían de los registros de índice. Para otras bifurcaciones condicionales, los dos primeros modelos de producción implementados predicen que no se tomarán; los modelos posteriores se cambiaron para implementar predicciones basadas en los valores actuales de los bits indicadores (que corresponden a los códigos de condición actuales). [34] Los diseñadores de Stretch habían considerado bits de sugerencia estáticos en las instrucciones de bifurcación 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 de un rendimiento menos que estelar se atribuyó al tiempo requerido para la recuperación de predicciones erróneas. Los diseños posteriores de computadoras grandes de IBM no utilizaron la predicción de bifurcaciones con ejecución especulativa hasta el 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 e independientemente por Jim Smith en 1979 en el CDC. [35]
Los procesadores microprogramados, populares desde la década de 1960 hasta la de 1980 y más allá, necesitaban varios ciclos por instrucción y, por lo general, no requerían predicción de saltos. Sin embargo, además del IBM 3090, existen otros muchos ejemplos de diseños microprogramados que incorporaban predicción de saltos.
El Burroughs B4900 , una máquina COBOL microprogramada lanzada alrededor de 1982, estaba segmentada y utilizaba predicción de saltos. El estado del historial de predicción de saltos del B4900 se almacena nuevamente en las instrucciones en memoria durante la ejecución del programa. El B4900 implementa la predicción de saltos de 4 estados mediante el uso de 4 códigos de operación de salto semánticamente equivalentes para representar cada tipo de operador de salto. El código de operación utilizado indicaba el historial de esa instrucción de salto en particular. Si el hardware determina que el estado de predicción de saltos de un salto en particular necesita ser actualizado, reescribe el código de operación con el código de operación semánticamente equivalente que indicaba el historial adecuado. Este esquema obtiene una tasa de aciertos del 93%. La patente estadounidense 4.435.756 y otras se otorgaron sobre este esquema.
El DEC VAX 9000 , anunciado en 1989, está microprogramado y segmentado y realiza predicciones de bifurcaciones. [36]
Los primeros procesadores RISC comerciales, los MIPS R2000 y R3000 y los procesadores SPARC anteriores , solo hacen predicciones triviales de bifurcaciones "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 último procesador R4000 utiliza la misma predicción trivial de bifurcaciones "no tomadas" y pierde dos ciclos por cada bifurcación tomada porque la recurrencia de resolución de bifurcación tiene una duración de cuatro ciclos.
La predicción de saltos se volvió más importante con la introducción de procesadores superescalares segmentados como Intel Pentium , DEC Alpha 21064 , MIPS R8000 y la serie IBM POWER . Todos estos procesadores se basan en predictores de un bit o bimodales simples.
El DEC Alpha 21264 (EV6) utiliza un predictor de siguiente línea reemplazado por un predictor local y un predictor global combinados, donde la elección de combinación la realiza un predictor bimodal. [37]
El AMD K8 tiene un predictor bimodal y global combinado, donde la elección de combinación es otro predictor bimodal. Este procesador almacena en caché los contadores de predictores bimodales de base y elección en bits de la caché L2 que de otro modo se utilizan para ECC. Como resultado, tiene tablas de predictores de base y elección 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 en una etapa avanzada del diseño) tenía una penalización mínima por predicción errónea de rama de 14 ciclos. Debía utilizar un predictor de siguiente línea complejo pero rápido, reemplazado por un predictor combinado bimodal y de votación por mayoría. La votación por mayoría se realizó entre el predictor bimodal y dos predictores gskew.
En 2018, el Proyecto Zero de Google y otros investigadores hicieron pública una vulnerabilidad de seguridad catastrófica llamada Spectre . La vulnerabilidad, que afecta a prácticamente todas las CPU modernas , implica preparar los predictores de bifurcación para que otro proceso (o el núcleo) prediga incorrectamente una bifurcación y use 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 averiguar cuál es, convirtiendo este estado interno de la CPU (microarquitectónico) en un valor que el atacante puede guardar y que tiene información sobre valores que no pudo leer directamente. [38]