solucionario - ¿Es posible decirle al pronosticador de sucursal qué tan probable es seguir a la sucursal?

estadistica aplicada a los negocios y la economìa 13 edicion descargar gratis (7)

Como dice Drakosha, decirle a gcc qué rama es el caso común, por lo que genera un mejor código para el caso donde el pronosticador de rama es frío, y así la ruta rápida a través de la función es fácil de ejecutar para la CPU, probablemente sea muy útil.

FYI, Pentium 4 tenía sugerencias de predictor de rama como prefijos de las instrucciones de jcc, pero solo la microarquitectura de Netburst hizo algo con ellos. Ver http://ref.x86asm.net/geek32.html . Y la Sección 3.5 de la excelente guía de aceptación de asma de Agner Fog , de http://www.agner.org/optimize/ . También tiene una guía para optimizar en C ++.

Poco se ha publicado oficialmente sobre cómo se comportan exactamente los predictores de bifurcación y los búferes de bifurcación-destino en las CPU Intel y AMD más recientes. Los manuales de optimización (fáciles de encontrar en los sitios web de AMD e Intel) dan algunos consejos, pero no documentan un comportamiento específico. Algunas personas han realizado pruebas para tratar de adivinar la implementación, por ejemplo, cuántas entradas de BTB tiene Core2 ... De todos modos, la idea de insinuar el predictor explícitamente ha sido abandonada (por ahora). Lo que está documentado es, por ejemplo, que Core2 tiene un búfer de historial de sucursal que puede evitar la predicción errónea de la salida de bucle si el bucle siempre ejecuta un número corto constante de iteraciones, <8 o 16 IIRC. Pero no se apresure a desenrollar, porque un bucle que se ajuste a 64bytes (o 19uops en Penryn) no tendrá instrucciones de obtener cuellos de botella porque se reproduce desde un búfer ... vaya a leer los archivos PDF de Agner Fog, son excelentes .

Solo para dejarlo en claro, no busco ningún tipo de portabilidad aquí, por lo que cualquier solución que me ate a una determinada caja está bien.

Básicamente, tengo una sentencia if que el 99% del tiempo evalúa como verdadera, y estoy tratando de alcanzar hasta el último reloj de rendimiento. ¿Puedo emitir algún tipo de comando de compilación (usando GCC 4.1.2 y el ISA x86, si Importa) decirle al pronosticador de bifurcación que debe almacenar en caché para esa rama?

Esto me suena a excesivo: este tipo de optimización ahorrará pequeñas cantidades de tiempo. Por ejemplo, usar una versión más moderna de gcc tendrá una influencia mucho mayor en las optimizaciones. Además, intente habilitar y deshabilitar todas las banderas de optimización diferentes; no todos mejoran el rendimiento.

Básicamente, parece muy poco probable que esto suponga una diferencia significativa en comparación con muchos otros caminos fructíferos.

EDITAR: gracias por los comentarios. Hice esta wiki de la comunidad, pero la dejé para que otros puedan ver los comentarios.

No, porque no hay un comando de ensamblaje que permita saber el pronosticador de la rama. No te preocupes, el pronosticador de ramas es bastante inteligente.

Además, comentario obligatorio sobre optimización prematura y cómo es malo.

EDITAR: Drakosha mencionó algunas macros para GCC. Sin embargo, creo que esto es una optimización de código y en realidad no tiene nada que ver con la predicción de bifurcación.

Sí, pero no tendrá ningún efecto. Las excepciones son arquitecturas antiguas (obsoletas) antes de Netburst, e incluso entonces no hace nada mensurable.

Hay un código de operación "sugerencia de rama" que Intel introdujo con la arquitectura Netburst, y una predicción de bifurcación estática predeterminada para saltos en frío (retrocedido predicho tomado, anticipado previsto no tomado) en algunas arquitecturas anteriores. GCC implementa esto con __builtin_expect (x, prediction) , donde la predicción es típicamente 0 o 1. El opcode emitido por el compilador se ignora en todos los arquitecros de procesador más nuevos (> = Core 2). El pequeño caso de esquina donde esto realmente hace algo es el caso de un salto en frío en la antigua arquitectura de Netburst. Intel recomienda ahora no utilizar las sugerencias de la rama estática, probablemente porque consideran que el aumento del tamaño del código es más perjudicial que la posible velocidad marginal.

Además de la sugerencia de rama inútil para el predictor, __builtin_expect tiene su uso, el compilador puede reordenar el código para mejorar el uso de la memoria caché o guardar la memoria.

Hay varias razones por las que no funciona como se esperaba.

El procesador puede predecir bucles pequeños (n <64) perfectamente.
El procesador puede predecir pequeños patrones de repetición (n ~ 7) perfectamente.
El procesador en sí mismo puede estimar la probabilidad de una rama durante el tiempo de ejecución mejor que el compilador / programador durante el tiempo de compilación.
La predictibilidad (= probabilidad de que una rama se prediga correctamente) de una rama es mucho más importante que la probabilidad de que se tome la rama. Desafortunadamente, esto es altamente dependiente de la arquitectura, y predecir la previsibilidad de la rama es notoriamente difícil.

Lea más sobre los trabajos internos de la predicción de bifurcación en los manuals Agner Fogs. Ver también la lista de correo de gcc.

Sí. http://kerneltrap.org/node/4705

__builtin_expect es un método que ofrecen gcc (versiones> = 2.96) para que los programadores indiquen la información de predicción de bifurcación al compilador. El valor de retorno de __builtin_expect es el primer argumento (que solo podría ser un entero) que se le pasa.

if (__builtin_expect (x, 0)) foo (); [This] would indicate that we do not expect to call `foo'', since we expect `x'' to be zero.

SUN C Studio tiene algunos pragmas definidos para este caso.

#pragma rarely_called ()

Esto funciona si una parte de una expresión condicional es una llamada a función o comienza con una llamada a función.

Pero no hay forma de etiquetar un enunciado if / while genérico

Sugiero en lugar de preocuparme por la predicción de ramas, perfilar el código y optimizar el código para reducir el número de ramas. Un ejemplo es el despliegue de bucles y otro uso de técnicas de programación booleanas en lugar de utilizar sentencias if .

A la mayoría de los procesadores les encanta realizar declaraciones previas. En general, una instrucción de bifurcación generará un error dentro del procesador que hará que vacíe la cola de captación previa. Aquí es donde está la mayor penalización. Para reducir este tiempo de penalización, vuelva a escribir (y diseñe) el código para que haya menos ramas disponibles. Además, algunos procesadores pueden ejecutar instrucciones de manera condicional sin tener que bifurcar.

Optimicé un programa de 1 hora de tiempo de ejecución a 2 minutos mediante el uso de búferes de desenrollado de bucles y E / S de gran tamaño. La predicción de la sucursal no habría ofrecido mucho ahorro de tiempo en esta instancia.