Los procesadores modernos son superescalares, es decir, pueden ejecutar varias instrucciones simultáneamente. Por ejemplo, algunos procesadores pueden procesar de cuatro a seis instrucciones por ciclo. Además, muchos de estos procesadores son capaces de iniciar instrucciones fuera de orden: pueden comenzar a trabajar con comandos ubicados en el código mucho más tarde.
Al mismo tiempo, el código a menudo contiene ramas (
if–then ). Tales ramas a menudo se implementan como "transiciones", en las cuales el procesador procede a ejecutar instrucciones debajo del código o continúa la ruta actual.
Con la ejecución superescalar de comandos fuera de orden, la ramificación es difícil. Para esto, los procesadores tienen bloques de predicción de rama sofisticados. Es decir, el procesador está tratando de predecir el futuro. Cuando ve una rama y, por lo tanto, una transición, trata de adivinar hacia dónde irá el programa.
Muy a menudo esto funciona bastante bien. Por ejemplo, la mayoría de los bucles se implementan como ramas. Al final de cada iteración del bucle, el procesador debe predecir si se realizará la siguiente iteración. A menudo es más seguro para el procesador predecir que el ciclo continuará (para siempre). En este caso, el procesador predice erróneamente solo una rama por ciclo.
Hay otros ejemplos comunes. Si accede al contenido de una matriz, muchos lenguajes de programación agregan "comprobación encuadernada", una comprobación oculta de la corrección del índice antes de acceder al valor de la matriz. Si el índice es incorrecto, se genera un error; de lo contrario, el código continúa ejecutándose de la manera habitual. Los controles fronterizos son predecibles, porque en una situación normal todas las operaciones de acceso deben ser correctas. En consecuencia, la mayoría de los procesadores deberían predecir casi perfectamente el resultado.
¿Qué sucede si la ramificación es difícil de predecir?
Dentro del procesador, todas las instrucciones que se ejecutaron pero que se encuentran en la rama predicha incorrectamente deben cancelarse y los cálculos deben iniciarse nuevamente. Es de esperar que por cada error de predicción de rama paguemos más de 10 ciclos. Debido a esto, el tiempo de ejecución del programa puede aumentar significativamente.
Veamos un código simple en el que escribimos enteros aleatorios en una matriz de salida:
while (howmany != 0) { out[index] = random(); index += 1; howmany--; }
Podemos generar un número aleatorio adecuado en promedio durante 3 ciclos. Es decir, el retraso total del generador de números aleatorios puede ser igual a 10 ciclos. Pero nuestro procesador es superescalar, es decir, podemos realizar varios cálculos de números aleatorios simultáneamente. Por lo tanto, podremos generar un nuevo número aleatorio aproximadamente cada 3 ciclos.
Cambiemos un poco la función para que solo se escriban números impares en la matriz:
while (howmany != 0) { val = random(); if( val is an odd integer ) { out[index] = val; index += 1; } howmany--; }
Puede pensar ingenuamente que esta nueva característica podría ser más rápida. Y de hecho, porque necesitamos registrar en promedio solo uno de dos enteros. Hay una rama en el código, pero para verificar la paridad de un número entero, solo verifique un bit.
Comparé estas dos funciones en C ++ en un procesador Skylake:
¡La segunda función funciona unas cinco veces más!
¿Se puede arreglar algo aquí? Sí, podemos eliminar la ramificación. Un número entero impar se puede caracterizar de tal manera que sea lógico Y bit a bit con un valor de 1 igual a uno. El truco consiste en incrementar el índice de la matriz en uno solo si el valor aleatorio es impar.
while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; }
En esta nueva versión, siempre escribimos un valor aleatorio en la matriz de salida, incluso si no es necesario. A primera vista, esto es un desperdicio de recursos. Sin embargo, nos salva de las ramas erróneamente predichas. En la práctica, el rendimiento es casi el mismo que el código original, y mucho mejor que la versión con ramas:
¿Podría el compilador resolver este problema por sí solo? En general, la respuesta es no. A veces, los compiladores tienen opciones para eliminar por completo la ramificación, incluso si hay una
if-then en el código fuente. Por ejemplo, la ramificación a veces se puede reemplazar con "movimiento condicional" u otros trucos aritméticos. Sin embargo, estos trucos no son seguros para su uso en compiladores.
Una conclusión importante: la ramificación pronosticada erróneamente no es un problema insignificante, tiene una gran influencia.
Mi código fuente está en Github .
Crear puntos de referencia es una tarea difícil: los procesadores aprenden a predecir la ramificación
[Nota traducción: esta parte era un
artículo separado del autor, pero lo combiné con el anterior, porque tienen un tema en común.]
En la parte anterior, mostré que la mayor parte del tiempo de ejecución de un programa puede deberse a una predicción de rama incorrecta. Mi punto de referencia era escribir 64 millones de valores enteros aleatorios en una matriz. Cuando intenté registrar solo números aleatorios impares, el rendimiento debido a predicciones erróneas disminuyó considerablemente.
¿Por qué utilicé 64 millones de enteros, en lugar de, digamos, 2000? Si ejecuta solo una prueba, entonces no importará. Sin embargo, ¿qué sucederá si hacemos muchos intentos? El número de ramas erróneamente pronosticadas caerá rápidamente a cero. El rendimiento del procesador Intel Skylake habla por sí mismo:
Como se puede ver en los gráficos a continuación, el "entrenamiento" continúa más allá. Poco a poco, la proporción de ramas erróneamente predichas se reduce a alrededor del 2%.
Es decir, si continuamos midiendo el tiempo que lleva la misma tarea, entonces se vuelve cada vez menos, porque el procesador aprende a predecir mejor el resultado. La calidad de la "capacitación" depende del modelo de procesador específico, pero se espera que los procesadores más nuevos aprendan mejor.
Los últimos procesadores de servidor AMD aprenden a predecir casi perfectamente la ramificación (dentro del 0.1%) en menos de 10 intentos.
Esta predicción ideal en AMD Roma desaparece cuando el número de valores en el problema aumenta de 2000 a 10,000: la mejor predicción cambia de una fracción de errores de 0.1% a 33%.
Probablemente debería evitar el código de evaluación comparativa con la ramificación para tareas pequeñas.
Mi código githubReconocimiento : valores AMD Roma proporcionados por Vel Erwan.
Lectura adicional :
Un caso para la predicción de rama de longitud de historia geométrica TAgged (Seznec et al.)