Speculative multithreaded processors

Resumen

En esta tesis se estudia el modelo de ejecución de los procesadores multithreaded especulativos así como los requisitos necesarios para su implementación. El modelo de ejecución se basa en la inserción de instrucciones de spawn dentro del código secuencial. De esta manera, la ejecución de un programa en estos procesadores es similar a cualquier otro hasta que se encuentra con un punto de spawn. Entonces, se crea un nuevo thread especulativo en el punto indicado por la instrucción de spawn y ambos threads se ejecutan en paralelo. Cuanto el thread creador llega al punto inicial del thread especulativo, se ha de verificar si la especulación ha sido correcta. En ese caso, el contexto del thread no especulativo se gradúa y se libera para uso futuro de más threads especulativos. En caso de que la verificación no haya sido correcta, se recupera el estado correcto. En este modelo de ejecución siempre hay un thread no especulativo y puede haber múltiples threads especulativos. Para soportar este modelo de ejecución, se necesita: i) hardware capaz de crear y gestionar threads especulativo y ii) un mecanismo de particionado para dividir los programas en threads especulativos. Se han estudiado varias plataformas para gestionar threads de forma concurrente. Por un lado, los procesadores clustered se benefician de menores retardos, menor potencia consumida y una menor complejidad aunque las latencias de comunicación sean mayores. Por otro lado, las arquitecturas centralizadas se benefician del hecho de compartir recursos y menor latencia de comunicación, pero la complejidad del hardware es mucho mayor. En cualquier caso, el hardware ha de ser capaz de ejecutar múltiples threads simultáneamente con el inconveniente de que algunos valores van a tener que compartirse mientras que otros son copias privadas. Es decir, el procesador deberá ser capaz de gestionar múltiples versiones de un mismo registro o posición de memoria para cada uno de los threads que se estén ejecutando. Además, se ha puesto especial énfasis en la gestión de las dependencias de datos entre los threads especulativos ya que tienen un impacto muy importante en el rendimiento del procesador. Encontrar threads independientes es casi imposible en aplicaciones irregulares, por tanto los threads especulativos necesitarán de valores producidos por otros threads especulativos. Se han estudiado dos mecanismos: sincronizar el thread productor y el thread consumidor y predecir los valores dependientes. En el primer caso, se han propuesto mecanismos para pasar el valor tan pronto como ha sido producido del productor al consumidor, especialmente en el caso de valores de memoria. Por otro lado, el segundo modelo es mucho más atrayente ya que si todos los valores dependientes fueran predichos de forma correcta, los threads pasarían a ejecutarse de forma independiente. Se han evaluado múltiples predictores de valores propuestos en la literatura y se ha presentado un nuevo predictor especialmente pensado para este tipo de arquitecturas que es el predictor de incremento. Este predictor usa la información de control de los threads especulativos para predecir los valores y los resultados obtenidos son muy prometedores aún con tamaños muy reducidos del predictor. Finalmente, el particionado de las aplicaciones afecta al rendimiento de este tipo de procesadores. Se han propuesto y evaluado varios esquemas de particionado. Una familia de estos esquemas asigna threads especulativos a construcciones de programa que por si solas proporcionan cierta independencia de control. Políticas de esta familia son aquellas que crean threads especulativos en iteraciones de bucles, continuaciones de bucles y continuaciones de subrutinas. La segunda familia de esquemas de particionado se ayuda de un análisis basado en profiling para encontrar las parejas de spawn más idóneas para cada uno de los códigos. De esta manera, aquellas partes del programa que cumplan las mejores características se seleccionan para crear threads especulativos. Algunos criterios de selección que han sido considerados en esta tesis han sido: la independencia de control, el tamaño mínimo de los threads, la independencia de datos y su predictabilidad. Los resultados obtenidos por ambas familias han sido muy significativos, aunque el esquema basado en técnicas de profile mejora los resultados obtenidos por la otra familia.