Actualmente estoy perfilando una implementación de búsqueda binaria. Utilizando algunas instrucciones especiales para medir esto, noté que el código tiene una tasa de error de aproximación del 20%. Tengo curiosidad si hay alguna manera de verificar cuántos ciclos estoy potencialmente perdiendo debido a esto. Es una arquitectura basada en MIPS.¿Cómo se mide el efecto de la predicción errónea de las ramas?
Búscalo en los documentos de tu CPU. Si no puede encontrar esta información específicamente, la longitud de la tubería de la CPU es una estimación bastante buena.
dado que es MIPS y es un sistema de 300 MHz, voy a suponer que se trata de una tubería bastante corto. Probablemente 4-5 etapas, por lo que un costo de 3-4 ciclos por error de lectura es probablemente una suposición razonable.
mirada a sus especificaciones para que la información y si eso no funciona, ejecutarlo mil millones de veces y el tiempo que externo a su programa (cronómetro de algo.) A continuación, ejecute con sin fallar y comparar.
Estás perdiendo 0.2 * n ciclos por iteración, donde N es el número de ciclos que se necesita para limpiar las tuberías después de una rama mispredicted. Supongamos que N = 10 significa que está perdiendo 2 relojes por iteración en el agregado. A menos que tenga un muy pequeño bucle interno, entonces esto probablemente no será un golpe de rendimiento significativo.
Bueno ... si tienes un 20% de ramas mal definidas por iteración, el tiempo podría comenzar a sumarse;) – Goz
@Goz: sí, buen punto - Supongo que cuando digo * loop * o * iteración * realmente me refiero a bloque con una rama parcialmente predecible, pero podría haber más de un bloque en un bucle. –
Eso es lo que pasa. los ciclos se suman rápidamente y son más valiosos cuando solo tienes 300 millones por segundo. –
en una CPU en el orden que puede ser capaz de calcular el costo mispredict aproximada como un producto del número de mispredicts y el costo mispredict (que es generalmente una función de alguna parte de la tubería)
En una CPU out-of-order moderna, sin embargo, tal cálculo general generalmente no es posible. Puede haber un gran número de instrucciones en el vuelo , y solo algunas de ellas son borradas por una predicción errónea. El código circundante puede estar enlazado por latencia por una o más cadenas de instrucciones dependientes, o puede estar vinculado a recursos como unidades de ejecución, cambio de nombre, etc., o puede estar en algún punto intermedio.
En tal núcleo, la penalización por error de predicción es muy difícil de determinar, incluso con la ayuda de contadores de rendimiento. Puede encontrar entire papers dedicado al tema: aquel encontró un tamaño de penalización de 9 a 35 ciclos promediado en todos los puntos de referencia: si observa un pequeño fragmento de código, el rango será aún mayor: una penalización de cero es fácil de demuestre, y podría crear un escenario donde la penalización se encuentre en los cientos de ciclos.
Cuando eso le deja, simplemente se trata de determinar el costo predicción errónea en su búsqueda binaria? ¡Bien, un enfoque simple es solo controlar la cantidad de errores de predicción y medir la diferencia! Si configura su entrada de referencia tiene un rango de comportamiento, comenzando con seguir siempre el mismo patrón de bifurcación, todo el camino hasta tener un patrón aleatorio, puede graficar el recuento de errores de predicción frente a la degradación del tiempo de ejecución. Si lo haces, comparte tu resultado!
Cientos de instrucciones en vuelo en el caso de grandes núcleos modernos, como los ofrecidos por los x86, ARM y POWER arquitecturas.
Lo curioso es que con una búsqueda binaria que se puede esperar cerca de un 50% de los errores de predicción de si el valor buscado es mayor o menor sea el elemento que se comparan. Supongo que obtener solo un 20% se debe a otras expresiones condicionales (verificar punteros antes de cruzar en un árbol o equilibrar el árbol?). No creo que el 20% sea una gran tasa de error de predicción para una elección básicamente aleatoria. –
Cierto, pero todo ayuda en un sistema de 300 mhz. –