Cómo lidiar con la predicción de rama cuando se usa un caso de conmutador en la emulación de CPU

performance compiler-optimization

Question

Recientemente leí la pregunta aquí ¿Por qué es más rápido procesar una matriz ordenada que una matriz sin clasificar? y encontró que la respuesta era absolutamente fascinante y ha cambiado completamente mi perspectiva sobre la programación al tratar con sucursales que se basan en Datos.

Actualmente tengo un Emulador Intel 8080 interpretado bastante básico, pero que funciona completamente, escrito en C, el corazón de la operación es una tabla de 256 cajas de interruptores para manejar cada código de operación. Mi idea inicial fue que este sería obviamente el método más rápido para trabajar, ya que la codificación de código de operación no es consistente en todo el conjunto de instrucciones 8080 y la descodificación agregaría mucha complejidad, incoherencia y casos únicos. Una tabla de conmutadores llena de macros de preprocesadores es muy limpia y fácil de mantener.

Desafortunadamente, después de leer el post mencionado anteriormente, se me ocurrió que no hay absolutamente ninguna manera de que el predictor de bifurcación en mi computadora pueda predecir el salto para el caso de cambio. Por lo tanto, cada vez que se navega por la caja de conmutación, la tubería debería ser eliminada por completo, lo que resultaría en un retraso de varios ciclos en lo que debería ser un programa increíblemente rápido (no hay más que una multiplicación en mi código).

Estoy seguro de que la mayoría de ustedes está pensando "Oh, la solución aquí es simple, pasar a la recopilación dinámica". Sí, esto parece que cortaría la mayoría de la caja del interruptor y aumentaría la velocidad considerablemente. Desafortunadamente, mi interés principal es emular consolas antiguas de 8 bits y 16 bits (el Intel 8080 aquí es solo un ejemplo, ya que es mi pieza más simple de código emulado) donde el ciclo y la sincronización de acuerdo con la instrucción exacta es importante como Video y Sonido debe ser procesado en base a estos tiempos exactos.

Cuando se trata de este nivel de precisión, el rendimiento se convierte en un problema, incluso para consolas más antiguas (por ejemplo, mire bSnes). ¿Hay algún recurso o es simplemente una cuestión de hecho cuando se trata de procesadores con tuberías largas?

Answer 1

Como las ramas en su instrucción de conmutación de 256 vías están densamente empaquetadas, el compilador implementará esto como una tabla de saltos, por lo que tiene razón en que activará una sola rama mal predicha cada vez que pase por este código (como el salto indirecto no mostrará ningún tipo de comportamiento predecible). La penalización asociada con esto será de alrededor de 15 ciclos de reloj en una CPU moderna (Sandy Bridge), o tal vez hasta 25 en microarquitecturas más antiguas que carecen de un caché micro-op. Una buena referencia para este tipo de cosas es "Recursos de optimización de software" en agner.org. La página 43 en "Optimización de software en C ++" es un buen lugar para comenzar.

http://www.agner.org/optimize/?e=0,34

La única forma de evitar este castigo es asegurándose de que se ejecuten las mismas instrucciones independientemente del valor del código de operación. Esto se puede hacer a menudo usando movimientos condicionales (que agregan una dependencia de datos, por lo que son más lentos que una rama predecible) o buscando simetría en sus rutas de código. Teniendo en cuenta lo que está tratando de hacer, esto probablemente no será posible, y si lo fuera, entonces casi seguramente agregaría una sobrecarga superior a los ciclos de 15-25 de reloj para el error de predicción.

En resumen, en una arquitectura moderna no hay mucho que puedas hacer que sea más eficiente que un conmutador / caja, y el costo de predecir mal una sucursal no es tanto como podrías esperar.

Answer 2

El salto indirecto es probablemente lo mejor que se puede hacer para decodificar instrucciones.

En máquinas más antiguas, como el Intel P6 de 1997, el salto indirecto probablemente obtendría una predicción errónea de la sucursal.

En las máquinas modernas, como por ejemplo Intel Core i7, hay un predictor de salto indirecto que hace un buen trabajo para evitar la predicción errónea de la sucursal.

Pero incluso en las máquinas más antiguas que no tienen un predictor de rama indirecto, puedes jugar una mala pasada. Este truco está (fue), por cierto, documentado en la Guía de optimización de códigos de Intel desde los días de Intel P6:

En lugar de generar algo que se parece

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       jmp loop
    label_instruction_01h_SUB: ...
       jmp loop
    ...

generar el código como

    loop:
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_00h_ADD: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    label_instruction_01h_SUB: ...
       load reg := next_instruction_bits // or byte or word
       load reg2 := instruction_table[reg]
       jmp [reg]
    ...

es decir, reemplace el salto a la parte superior del bucle de obtención / decodificación / ejecución de instrucciones por el código en la parte superior del bucle en cada lugar.

Resulta que esto tiene una predicción de rama mucho mejor, incluso en ausencia de un predictor indirecto. Más precisamente, un BTB indexado por PC, condicional y único será mucho mejor en este último código, con hilos, que en el original con solo una copia del salto indirecto.

La mayoría de los conjuntos de instrucciones tienen patrones especiales; por ejemplo, en Intel x86, una instrucción de comparación casi siempre es seguida por una rama.

¡Buena suerte y diviertete!

(En caso de que le importe, los decodificadores de instrucciones utilizados por los simuladores de conjuntos de instrucciones en la industria casi siempre hacen un árbol de saltos en la N, o el doble basado en datos, navega por un árbol de tablas en la N, con cada entrada en el árbol apuntando A otros nodos, oa una función para evaluar.

Ah, y tal vez debería mencionar: estas tablas, estas declaraciones de cambio o estructuras de datos, son generadas por herramientas de propósito especial.

Un árbol de saltos N-way, porque hay problemas cuando el número de casos en la tabla de saltos es muy grande: en la herramienta, mkIrecog (reconocimiento de instrucciones) que escribí en la década de 1980, generalmente saltaba tablas hasta 64 K Entradas en tamaño, es decir, saltando sobre 16 bits. Los compiladores de la época se rompieron cuando las tablas de salto superaron los 16M de tamaño (24 bits).

Los datos controlados, es decir, un árbol de nodos que apunta a otros nodos porque (a) en las máquinas más antiguas, los saltos indirectos pueden no predecirse bien, y (b) resulta que la mayor parte del tiempo existe un código común entre las instrucciones, en lugar de tener un ramifique la predicción errónea cuando salte al caso por instrucción, luego ejecute el código común, luego cambie nuevamente y obtenga una segunda predicción errónea, haga el código común, con parámetros ligeramente diferentes (como, cuántos bits del flujo de instrucciones consume, y donde el siguiente conjunto de bits para bifurcarse es (son).

Fui muy agresivo en mkIrecog, ya que digo permitir que se usen hasta 32 bits en un conmutador, aunque las limitaciones prácticas casi siempre me detuvieron en 16-24 bits. Recuerdo que a menudo veía la primera decodificación como un conmutador de 16 o 18 bits (entradas de 64K-256K), y todas las demás decodificaciones eran mucho más pequeñas, no más grandes que 10 bits.

Hmm: Publiqué mkIrecog en Usenet en 1990. ftp://ftp.lf.net/pub/unix/programming/misc/mkIrecog.tar.gz Si lo desea, puede ver las tablas utilizadas. (Sea amable: era joven entonces. No recuerdo si era Pascal o C. Desde entonces lo he reescrito muchas veces, aunque aún no lo he reescrito para usar vectores de bits de C ++).

La mayoría de los otros tipos que conozco que hacen este tipo de cosas hacen las cosas un byte a la vez (es decir, una búsqueda de 8 bits, 256 vías, rama o tabla).

Answer 3

Pensé en agregar algo ya que nadie lo mencionó.

Por supuesto, el salto indirecto es probable que sea la mejor opción.

Sin embargo, si sigues el camino de la N-comparación, hay dos cosas que me vienen a la mente:

Primero, en lugar de hacer comparaciones de igualdad de N, puede hacer comparaciones de desigualdad de registro (N), probando sus instrucciones en función de su código de operación numérico mediante dicotomía (o verifique el número bit a bit si el espacio de valores está casi lleno). poco como una tabla hash, implementas un árbol estático para encontrar el elemento final.

En segundo lugar, puede ejecutar un análisis en el código binario que desea ejecutar. Incluso podría hacer eso por binario, antes de la ejecución, y en tiempo de ejecución-parche su emulador. Este análisis construirá un histograma que representa la frecuencia de las instrucciones, y luego organizará sus pruebas para que las instrucciones más frecuentes se predigan correctamente.

Pero no puedo ver que esto sea más rápido que una penalización media de 15 ciclos, a menos que tenga el 99% de MOV y ponga una igualdad para el código de operación de MOV antes de las otras pruebas.

Answer 4

Por el contrario, es probable que las instrucciones de switch se conviertan en tablas de saltos , lo que significa que posiblemente realicen unos pocos if (para la verificación de rango) y un solo salto. El if s no debería causar un problema con la predicción de ramificación porque es poco probable que tenga un código de operación incorrecto. El salto no es tan amigable con la tubería, pero al final, es solo uno para toda la declaración del switch ...

No creo que pueda convertir una declaración de switch larga de códigos de operación a ninguna otra forma que pueda dar como resultado un mejor rendimiento. Esto es, por supuesto, si su compilador es lo suficientemente inteligente como para convertirlo en una tabla de salto. Si no, puedes hacerlo manualmente.

En caso de duda, implementar otros métodos y medir el rendimiento.

Editar

En primer lugar, asegúrese de no confundir la predicción de rama y la predicción de destino de rama .

La predicción de rama solo funciona en declaraciones de rama. Decide si una condición de rama fallará o tendrá éxito. No tienen nada que ver con la declaración de salto.

La predicción de objetivo de rama, por otro lado, trata de adivinar dónde terminará el salto.

Por lo tanto, su declaración "no hay forma de que el predictor de rama pueda predecir el salto" debe ser "no hay manera de que el predictor de rama pueda predecir el salto".

En tu caso particular, no creo que puedas evitar esto. Si tuviera un conjunto muy pequeño de operaciones, tal vez podría encontrar una fórmula que cubra todas sus operaciones, como las realizadas en circuitos lógicos. Sin embargo, con una instrucción establecida tan grande como una CPU, incluso si fuera RIESGO, el costo de ese cálculo es mucho mayor que la penalización de un solo salto.