architecture - ¿Predicción del objetivo de rama junto con la predicción de rama?

x86 branch (2)

BP y BTP están naturalmente estrechamente relacionados, pero obviamente no son lo mismo. Creo que su mayor confusión proviene de la afirmación de que, dado que BTP predice el objetivo de una rama determinada, puede decirle el resultado (es decir, cuál será la siguiente instrucción ejecutada). Ese no es el caso.

Un objetivo de sucursal es la dirección a la que esta sucursal puede enviarle, si se toma. Si la rama se toma o no, es una pregunta completamente diferente y es abordada por el predictor de rama. De hecho, las dos unidades normalmente trabajarían juntas en las primeras etapas de la tubería, y producirían (si fuera necesario) tanto la predicción tomada como la tomada o no tomada y la dirección. Luego viene la lógica complicada que dice básicamente: si se trata de una rama y se predice que se tomó (o es incondicional), salte al objetivo si lo tiene (ya sea conocido o predicho).

Como se citó a sí mismo en la lista de tipos de rama: la cuestión de si una rama debe predecir que se tomará o no (es condicional) y si una rama debe predecir el objetivo (es un objetivo directo / fijo como lo llama) son aplicables y cada uno puede ir en ambos sentidos sin relación con el otro, proporcionándole las 4 opciones que enumeró:

Las ramas directas incondicionales, en teoría, no requieren ninguna predicción: el extremo frontal de la CPU simplemente leería el objetivo y "tomaría" la rama (alimentando el código de canalización desde la nueva dirección). Sin embargo, las CPU modernas aún necesitarían tiempo para descodificar la rama e identificar el destino codificado allí, por lo que para evitar atascos en el predictor de rama (que normalmente está en la cabeza de la tubería), también tendrán que predecir esa dirección. Sin embargo, confirmar la predicción es simple (inmediatamente después de la decodificación), por lo que la penalización por predicción errónea no es muy alta. Todavía podría estar estancado debido a que el código caché / tlb se pierde, pero es el más rápido (pero uno podría decir que el más débil)
condicional directo bifurcado saber su objetivo después de la decodificación (pero, una vez más, debe predecirlo antes de eso), pero no puede saber si la bifurcación se toma o no hasta que se ejecute la condición y se haga la resolución, que puede estar muy lejos tubo. Esto, a su vez, puede depender de instrucciones anteriores y puede detenerse hasta que se conozcan las fuentes de la condición. Entonces, hay dos predicciones: objetivo y dirección (a menos que la dirección sea directa, en cuyo caso no es necesario un objetivo), pero la resolución de la dirección es la más riesgosa. El predictor de rama (en realidad, en las CPU modernas suele haber varias), haría una conjetura educada y continuaría a buscar desde allí. Incluso se han realizado algunos estudios, principalmente en la academia, sobre el intento de obtener y ejecutar ambos caminos (aunque se puede ver de inmediato que esto puede explotar exponencialmente, ya que normalmente tiene una rama cada pocas instrucciones, por lo que generalmente está reservado para predecir unos). Otra opción popular es "predicar" (tenga en cuenta que hay ''a'' allí ...) las dos rutas, es decir, enviar algunos bits por la tubería para marcar qué ruta es, para limpiar fácilmente la ruta incorrecta una vez que se conoce la resolución. Esto es bastante popular en las máquinas de flujo de datos debido a la estructura del lenguaje, pero esa es una pregunta completamente nueva.
Ramas indirectas incondicionales: estas son desagradables ya que ambas son comunes (cada ret por ejemplo,), y más difíciles de predecir. Si bien la resolución de la rama fue simple en el caso anterior (y siempre podría depender de algunas heurísticas o patrones de adivinación), esta debe proporcionar una dirección real, por lo que probablemente tenga que visitar esta rama específica con este objetivo específico varias veces para permitir El BTP aprende el patrón allí.
Ramas indirectas condicionales - bueno, mala suerte para ti, necesitas ambas predicciones ...

Entonces, las decisiones son ortogonales, pero eso no significa que los predictores tengan que ser así. Tenga en cuenta que tiene un solo "flujo" de historial de ramas, por lo que probablemente vale la pena que el predictor esté relacionado de alguna manera, compartiendo algunas tablas o algo de lógica. ¿Cómo es exactamente una decisión de diseño y depende de la implementación real de HW? Probablemente no obtendrá muchos detalles sobre cómo Intel / AMD hace eso, pero hay muchas investigaciones académicas sobre ese tema.

En cuanto a la segunda pregunta, es un poco amplio y, una vez más, no podrá obtener todos los detalles exactos sobre las CPU reales, pero podría obtener sugerencias aquí y allá. Consulte, por ejemplo, el diagrama de esta revisión de Haswell (que puede haber aparecido aquí antes en algún lugar):

Este diagrama no le dice todo , obviamente falta las entradas para el BP / BTP, o incluso la distinción entre ellos (lo que en sí mismo ya le dice que probablemente estén juntos), pero muestra que aparentemente es La primera y más importante parte de la tubería. Debe predecir el siguiente puntero de instrucción antes de poder continuar y introducirlo en la tubería de obtención / decodificación / ... (o en la alternativa uop-cache). Esto probablemente significa que la CPU comienza cada ciclo (bueno, sí, todo se hace en paralelo, pero ayuda a pensar en una tubería como un proceso por etapas), pensando qué instrucción realizar a continuación. Digamos que él sabe dónde estábamos la última vez, así que es una instrucción que no es de bifurcación (ahh, pero ¿qué hay de diferente longitud ... otra complicación que esta unidad necesita resolver), o una bifurcación, en cuyo caso esta unidad debería adivinar cuál de los tipos anteriores a los que pertenece esta rama, y predice la siguiente instrucción en consecuencia.

Tenga en cuenta que escribí "supongo": si el diagrama dice la verdad, la etapa de decodificación está muy lejos, ni siquiera sabe que es una rama en este punto. Entonces, para responder a su pregunta, esta unidad BP / BTP necesita comunicarse con las unidades de ejecución / WB para que pueda conocer el resultado de las ramas condicionales, con la unidad de decodificación para que pueda saber qué instrucción se está decidiendo actualmente es una rama y qué tipo es Es decir, con las diferentes tuberías de captación para alimentar la salida. Supongo que hay otras relaciones con otras unidades (por ejemplo, algunos diseños pueden decidir enviar prefetches de código según las predicciones de destino, etc.).

EDIT: ¿Mi confusión surge porque seguramente al predecir qué rama se toma, también está haciendo efectivamente la predicción del objetivo?

Esta pregunta está intrínsecamente vinculada a mi primera pregunta sobre el tema:

predicción de rama vs predicción de objetivo de rama

Mirando la respuesta aceptada:

Rama incondicional, objetivo fijo
Bucle infinito
goto declaración
break o continue declaración
Fin de la cláusula ''then'' de una sentencia if/else (para saltar más allá de la cláusula else )
Llamada de función no virtual
Rama incondicional, objetivo variable
Volviendo de una función
Función virtual llamada
Función puntero llamada
instrucción de switch (si se compila en una tabla de salto)
Rama condicional, objetivo fijo
if declaración
instrucción switch (si está compilada en una serie de instrucciones if/else )
Pruebas de condición de bucle
El && y || operadores
El ternario ?: Operador
Rama condicional, objetivo variable
Es menos probable que aparezca en condiciones normales, pero el compilador puede sintetizar uno como una optimización, combinando dos de los casos anteriores. Por ejemplo, en x86, el compilador puede optimizar código como if (condition) { obj->VirtualFunctionCall(); } if (condition) { obj->VirtualFunctionCall(); } en un salto condicional indirecto como jne *%eax si aparece al final de una función debido a la optimización de la llamada de cola.

Si tengo el siguiente código:

if(something){ //a } else{ //b }

(BP = "Predicción de rama" y BTP = "Predicción de objetivo de rama")

Su bastante obvio BP se utiliza para evaluar something condicional. Sin embargo, estoy tratando de entender si BTP también está involucrado en determinar qué sucede en la rama a . ¿Sucede también que BTP determine la dirección del código ubicado en la sucursal a / b , dependiendo del resultado de la BP?

Lo pregunto porque en esta página de Wikipedia ( http://en.wikipedia.org/wiki/Branch_target_predictor ):

En la arquitectura de computadora, un predictor de objetivo de rama es la parte de un procesador que predice el objetivo de una rama condicional tomada o una instrucción de rama incondicional antes de que la unidad de ejecución del procesador calcule el objetivo de la instrucción de rama.

sugiere que se usa BTP para predecir el objetivo después de que se haya predicho el condicional.

1) ¿Alguien podría aclarar lo anterior por favor?

Una segunda pregunta relacionada: ¿en qué se diferencian BP y BTP en la forma en que interactúan con el proceso de búsqueda / decodificación / ejecución / escritura de la CPU? ¿Comienza BP en la etapa de búsqueda o decodificación? Después de la etapa de ejecución del código condicional, podemos verificar si la predicción fue correcta y actualizar el caché de predicción de rama.

2) ¿Cómo funciona BTP con respecto a las etapas de CPU de recuperación / decodificación / ejecución / escritura?

Lea junto con el manual de optimización de Intel, la ubicación de descarga actual está aquí . Cuando esté obsoleto (se mueven cosas todo el tiempo), busque el "Manual de optimización de arquitecturas" en el sitio de Intel. Tenga en cuenta que la información allí es bastante genérica, solo revelan la cantidad necesaria para permitir la escritura de código eficiente. Los detalles de implementación de la predicción de sucursal se consideran un secreto comercial y cambian entre arquitecturas. Busque el manual de "predicción de bifurcación" para encontrar referencias, está bastante extendido entre los capítulos.

Daré un resumen de lo que se encuentra en el manual, agregando detalles cuando sea apropiado:

La predicción de rama es el trabajo de la unidad BPU en el núcleo (Unidad de predicción de rama). Aproximadamente se correlaciona con "BP" en su pregunta. Contiene varias subunidades:

La tabla de la historia de la rama. Esta tabla realiza un seguimiento de las ramas condicionales tomadas anteriormente y es consultada por el predictor para decidir si es probable que se tome una rama. Se alimenta de entradas por la unidad de retiro de instrucciones, la que sabe si la sucursal se tomó realmente. Esta es la subunidad que más ha cambiado a medida que mejoraron las arquitecturas, se hizo más profunda y más inteligente a medida que más propiedades inmobiliarias estaban disponibles.
El BTB, Branch Target Buffer. Este búfer almacena la dirección de destino de un salto o llamada indirecta tomada anteriormente. Esto se relaciona con "BTP" en su pregunta. El manual no indica si el búfer puede almacenar múltiples objetivos por dirección, indexados por la tabla de historial, lo considero probable para arquitecturas posteriores.
El buffer de pila de retorno. Este búfer actúa como una pila "oculta", almacenando la dirección de retorno de las instrucciones CALL, haciendo que el objetivo de una instrucción RET esté disponible con un alto grado de confianza sin que el procesador tenga que confiar en el BTB, es poco probable que sea tan efectivo para las llamadas. Está documentado que tiene 16 niveles de profundidad.

La viñeta 2) en un poco difícil de responder con precisión, el manual solo habla sobre el "Front End" y no desglosa los detalles de la tubería. Bastante apropiado, es muy dependiente de la arquitectura. El diagrama en la sección 2.2.5 es posiblemente ilustrativo. El caché de seguimiento de ejecución desempeña un papel, almacena instrucciones previamente decodificadas, por lo que es la fuente principal de las consultas de BPU. De lo contrario, justo después del traductor de instrucciones (también conocido como decodificador).