¿Qué tipo de predicción de rama es más importante?

11

He observado que hay dos tipos diferentes de estados en la predicción de ramas.

  1. En la ejecución superescalar, donde la predicción de ramificación es muy importante, y se debe principalmente a la demora de ejecución en lugar de la demora de recuperación.

  2. En la canalización de instrucciones, donde la recuperación es más problemática ya que las instrucciones no se ejecutan hasta más tarde.

¿Cuál de estos es muy importante (como en cuál de estos realmente importa en la CPU hoy en día)? Si ambos son igualmente importantes o si el segundo es más importante, ¿por qué no tenemos dos canales de instrucciones (probablemente de la mitad de la longitud) y luego, dependiendo de las ramas, simplemente elija uno de ellos y luego comience nuevamente la población desde ¿comenzando?

Kaveh
fuente
1
¿Quizás ambos son importantes, dependiendo de las circunstancias?
Raphael

Respuestas:

6

No sé qué caso prevalece, pero me gustaría ofrecer algunas ideas sobre su propuesta de doble canalización.

En primer lugar, necesitaría el doble de cable que consumiría el doble de energía y produciría el doble de calor mientras está activo. Si bien no es necesario, por otro lado, sería completamente inútil. Entonces uno podría argumentar que no es un buen uso de los recursos que son raros en los procesadores modernos.

Más fundamentalmente, a menos que prefiera una rama basada en la probabilidad, ¿cómo sabe qué versión escribir? Si no hay ninguno, es posible que no guarde nada porque de todos modos otros procesadores tendrán que esperar su decisión. Si te quedas con uno de ellos, tienes esencialmente la misma probabilidad y costo de reversión que tienes ahora.

Hagamos un cálculo aproximado. En aras de la simplicidad, supongamos que manejar dos canales en lugar de uno no causa una sobrecarga de administración adicional. El costo esperado (por ejemplo, energía, calor) es con una tubería ( el costo de ejecutar cualquiera de las alternativas, la probabilidad de reversión y el costo de reversión sin el costo de ejecutar la otra alternativa), pero o incluso : cualquiera es mucho más grande que si y son relativamente pequeñas, yC=c+p(cr+c)cpcr2c2c+pcrCpcrpciertamente lo es (hasta donde yo sé, las predicciones de rama modernas tienen precisiones superiores al 90%). ¡Y no obtenemos mucho por este costo! Los tiempos de ejecución esperados son con una tubería y resp. con dos; Como es pequeño, el ahorro de tiempo es insignificante.t+p(tr+t)tt+ptrp

Rafael
fuente
Hasta donde yo sé, Intel ha intentado las "instrucciones de lectura para ambos lados de la rama" e incluso "ejecutar instrucciones para ambos lados de la rama", y dejó de hacerlo. Ya sea porque no ganó nada, o porque el costo y la complejidad eran tan altos que podrían obtener más ganancias de diferentes maneras por el mismo costo.
gnasher729
@ gnasher729 ¿Y eso fue probablemente antes de que supiéramos sobre fallas de seguridad vinculadas a características como esta?
Raphael
2

En cierto sentido, el efecto de la predicción de bifurcación es más crítico en la obtención de instrucciones, ya que una instrucción que no se obtiene no se puede ejecutar.

Con respecto a la ejecución de ambas rutas de una rama, esto se llama ejecución ansiosa y se ha investigado de manera sustancial. Augustus K. Uht y Vijay Sindagi "Ejecución ansiosa disjunta: una forma óptima de ejecución especulativa" (1995) podría valer la pena.

La ejecución ansiosa tiene varios problemas. Para una especulación profunda, el número de rutas que deben rastrearse puede crecer exponencialmente (cada ruta bifurcada puede encontrarse con una rama). La predicción de rama también es a menudo muy precisa (> 90% correcta), por lo que siempre sería un desperdicio ejecutar ambas rutas. La ejecución ansiosa también puede "contaminar" los cachés con contenido inútil. (El documento mencionado anteriormente propuso una ejecución ansiosamente limitada e inteligente para evitar algunos de estos problemas). La búsqueda ansiosa limitada de la ruta alternativa tiene menos problemas y puede ser algo atractiva para reducir el retraso de recuperación de predicciones erróneas en tuberías más cortas.

Otro enfoque que se ha propuesto es predicar dinámicamente ramas de "hamaca" (ramas cortas hacia adelante que se unen de nuevo a la ruta principal del flujo de instrucciones). La "Predicción dinámica de hamacas para arquitecturas de conjuntos de instrucciones no predicadas" de Artur Klauser et al. (1998) podría valer la pena leer para esa idea. (Hyesoon Kim et al., "Wish Branches: Combination Conditional Branching and Predication for Adaptive Predicated Execution" propone agregar a un ISA ramas que facilitan la predicción de hamacas y extiende este método de predicción a ramas de bucle difíciles de predecir).

Paul A. Clayton
fuente
Esa es una muy buena respuesta! Gracias. :-)