¿Cómo funciona la predicción de sucursal, si aún tiene que verificar las condiciones?

Estaba leyendo la respuesta popular sobre predicción de sucursales en https://stackoverflow.com/q/11227809/555690 , y hay algo que me confunde:

• Si acertó, continúa.
• Si adivinaste mal, el capitán se detendrá, retrocederá y te gritará que actives el interruptor. Entonces puede reiniciar por la otra ruta.

Si aciertas siempre, el tren nunca tendrá que detenerse.

Si adivina mal con demasiada frecuencia, el tren pasará mucho tiempo deteniéndose, retrocediendo y reiniciando.

Pero esto es lo que no entiendo: para saber si su suposición fue correcta o incorrecta, debe hacer una verificación de condición de todos modos . Entonces, ¿cómo funciona la predicción de ramificación, si de alguna manera todavía está haciendo la misma verificación condicional?

Lo que estoy tratando de decir es, ¿no es la predicción de rama exactamente lo mismo que no tener predicción de rama en absoluto porque de todos modos estás haciendo las mismas verificaciones condicionales? (obviamente estoy equivocado, pero no lo entiendo)

Por supuesto, la condición se verifica cada vez. Pero para el momento en que se verifica, está muy avanzado en la tubería de la CPU. Mientras tanto, otras instrucciones también han entrado en la tubería, y se encuentran en diversas etapas de ejecución.

Por lo general, una condición es seguida inmediatamente por una instrucción de bifurcación condicional, que se bifurca si la condición se evalúa como VERDADERA o falla si la condición se evalúa como FALSA. Esto significa que hay dos flujos diferentes de instrucciones que pueden cargarse en la tubería después de la instrucción de condición y la instrucción de derivación, dependiendo de si la condición se evalúa como VERDADERA o FALSA. Desafortunadamente, inmediatamente después de cargar la instrucción de condición y la instrucción de bifurcación, la CPU aún no sabe a qué se evaluará la condición, pero aún tiene que seguir cargando cosas en la tubería. Por lo tanto, elige uno de los dos conjuntos de instrucciones basándose en una suposición sobre lo que la condición evaluará.

Más adelante, a medida que la instrucción de condición viaja por la tubería, es hora de ser evaluada. En ese momento, la CPU descubre si su suposición fue correcta o incorrecta.

Si la suposición resulta correcta, entonces la rama fue al lugar correcto y las instrucciones correctas se cargaron en la tubería. Si resulta que la suposición fue incorrecta, entonces todas las instrucciones que se cargaron en la tubería después de la instrucción de ramificación condicional fueron incorrectas, deben descartarse, y la recuperación de instrucciones debe comenzar nuevamente desde el lugar correcto.

Enmienda

En respuesta al comentario de StarWeaver, para dar una idea de lo que la CPU tiene que hacer para ejecutar una sola instrucción:

Considere algo tan simple como MOV AX,[SI+10]lo que los humanos pensamos ingenuamente como "cargar AX con la palabra en SI más 10". Aproximadamente, la CPU tiene que:

1. emitir el contenido de la PC (el "registro del contador del programa") al bus de direcciones;
2. lea el código de operación de instrucciones del bus de datos;
3. PC incremental;
4. decodifica el código de operación para saber qué hacer con él;
5. emitir el contenido de la PC al bus de direcciones;
6. lea el operando de instrucción (en este caso 10) del bus de datos;
7. PC incremental;
8. alimentar el operando y SI al sumador;
9. emitir el resultado del sumador al bus de direcciones;
10. lea AX desde el bus de datos.

Esta es la friolera de 10 pasos. Algunos de estos pasos se optimizarán incluso en CPU no interconectadas, por ejemplo, la CPU casi siempre incrementará la PC en paralelo con el siguiente paso, lo cual es algo fácil de hacer porque la PC es un registro muy, muy especial que es nunca se utiliza para ningún otro trabajo, por lo que no hay posibilidad de disputa entre diferentes partes de la CPU para acceder a este registro en particular. Pero aún así, nos quedan 8 pasos para una instrucción tan simple, y tenga en cuenta que ya estoy asumiendo cierto grado de sofisticación en nombre de la CPU, por ejemplo, supongo que no habrá necesidad de un paso adicional completo para el sumador para llevar a cabo la adición antes de que se pueda leer el resultado,

Ahora, considere que existen modos de direccionamiento más complicados, como MOV AX, [DX+SI*4+10], e incluso instrucciones mucho más complicadas, como las MUL AX, operandque realmente realizan bucles dentro de la CPU para calcular su resultado.

Entonces, mi punto aquí es que la metáfora del "nivel atómico" está lejos de ser adecuada para el nivel de instrucción de la CPU. Puede ser adecuado para el nivel de paso de la tubería, si no desea ir demasiado lejos al nivel real de la puerta lógica.

Piense en ello como un viaje por carretera sin GPS. Llegas a una intersección y crees que debes girar, pero no estás completamente seguro. Entonces tome el turno, pero pídale a su pasajero que revise el mapa. Tal vez estés tres millas más adelante cuando termines de discutir dónde estás. Si tuviera razón, está tres millas más lejos de lo que hubiera estado si se hubiera detenido y discutido antes de girar. Si te equivocaste, tienes que darte la vuelta.

Las tuberías de CPU funcionan de la misma manera. Para el momento en que pueden verificar la condición, ya están en el camino. La diferencia es que no tienen que conducir las tres millas hacia atrás, solo pierden la ventaja. Eso significa que no hay daño en intentarlo.

Según tengo entendido, la predicción de ramas es más útil cuando la condición que necesita verificar requiere el resultado de algo que es costoso o que aún está en progreso, y de lo contrario estaría haciendo girar los pulgares esperando el valor para evaluar la condición.

Con cosas como la ejecución fuera de orden, puede usar la predicción de bifurcación para comenzar a llenar los espacios vacíos en la tubería que la CPU no podría usar de otra manera. En una situación donde no hay, por alguna razón, ningún ciclo inactivo en la tubería, entonces sí, no hay una ganancia en la predicción de rama.

Pero la clave aquí es que la CPU está comenzando el trabajo para una de las ramas predichas porque todavía no puede evaluar la condición.

Forma corta:

Algunas CPU pueden comenzar a trabajar en una nueva instrucción antes de terminar la anterior. Estas son las CPU que usan predicción de rama.

Un ejemplo de pseudocódigo:

int globalVariable;
int Read(int* readThis, int* readThat)
{
    if ((globalVariable*globalVariable % 17) < 5)
       return *readThis;
    else
       return *readThat;
}

El código anterior verifica una condición y, en función del resultado, necesita devolver el valor almacenado en la ubicación de la memoria addThiso el valor almacenado en readThat. Si la predicción de bifurcación predice la condición true, la CPU ya leerá el valor almacenado en la ubicación de la memoria addThismientras realiza el cálculo necesario para evaluar la ifdeclaración. Este es un ejemplo simplificado.

Sí, la condición se verifica en ambos sentidos. Pero la ventaja de la predicción de rama es que puede hacer el trabajo en lugar de esperar el resultado de la verificación de condición.

Digamos que tiene que escribir un ensayo y puede ser sobre el tema A o el tema B. Usted sabe por ensayos anteriores que a su maestro le gusta el tema A mejor que B y lo elige con más frecuencia. En lugar de esperar su decisión, puede comenzar a escribir el ensayo sobre el primer tema. Ahora hay dos resultados posibles:

1. Comenzaste tu ensayo sobre el tema equivocado y tienes que dejar lo que has escrito hasta ahora. Debe comenzar a escribir sobre el otro tema y es el mismo esfuerzo de tiempo que si hubiera esperado.
2. Has acertado y ya has trabajado.

Las CPU modernas están inactivas la mayor parte del tiempo porque esperan respuestas de E / S o el resultado de otros cálculos. Este tiempo se puede usar para hacer un trabajo futuro.

Incluso si tiene que descartar lo que está haciendo en este tiempo de inactividad, es más probable que sea más efectivo si tiene la capacidad de adivinar qué camino elegirá el programa. Y las CPU modernas tienen esta capacidad.