Aumentando las Prestaciones en la Predicción de Flujo de Instrucciones

Abstract

Las dependencias en el flujo de control limitan el rendimiento de los procesadores superescalares. La predicción del flujo de control permite superar este límite, pero supone un compromiso entre requerimientos aparentemente incompatibles. Por un lado, la predicción debe ser precisa, para que un elevado número de casos se beneficien del predictor. Por otro lado, la predicción debe ser rápida. El problema es que la precisión se aumenta almacenando mayor cantidad de información y utilizando algoritmos más complejos, que alargan el tiempo para realizar las predicciones.<br/>En esta tesis se presentan diferentes estrategias y se realizan varias propuestas para aumentar el rendimiento global del predictor de flujo de control. Se trata de organizar y codificar la información de forma eficiente, y de dotar al predictor de flexibilidad para adaptarse a los diferentes casos de forma eficaz. Así, las predicciones más frecuentes y sencillas se realizan rápidamente y utilizando recursos mínimos, mientras que predicciones menos comunes o que requieren el uso de más información para alcanzar una alta precisión, pueden realizarse más lentamente. La flexibilidad del diseño combinada con el exceso de ancho de banda permite compensar estos casos complejos y lentos, con el resto de casos, frecuentes y rápidos. El resultado es un aumento del ancho de banda de las predicciones gracias tanto al aumento de la velocidad de predicción como al aumento de la anchura de cada predicción. Todo ello se consigue sin reducir la precisión del predictor, y además con un moderado consumo energético.<br/>En primer lugar, las estrategias de predicción de vía, de jerarquía de dos niveles, y de predicción de índice consiguen aumentar la velocidad de predicción sin disminuir la precisión en la predicción y con un aumento moderado de la memoria del predictor. En segundo lugar se propone un método eficiente de predicción de trazas, que reduce los problemas de otras propuestas anteriores en la literatura, y que consigue aumentar la anchura de las predicciones, sin disminuir su precisión y también con un aumento moderado de los requerimientos de memoria. Finalmente se propone una nueva organización de dos niveles que mejora la gestión de los saltos indirectos para, fijado el tamaño de memoria disponible, aumentar su precisión<br/>Aunque en la tesis no se hace ninguna propuesta dirigida explícitamente a mejorar los algoritmos de predicción para aumentar su precisión, una organización más eficiente del predictor tiene como resultado lateral disponer de más recursos para aumentar la precisión. Por un lado, se dispone de más capacidad para almacenar la historia pasada. Por otro lado, se proporciona mayor tolerancia al aumento de la latencia en las predicciones, lo que permite aplicar algoritmos más complejos para poder aumentar la precisión.

Control flow dependences limit the performance of superscalar processors. Predicting control flow allows surpassing this limit, but involves a compromise among seemingly incompatible goals. On one hand, predictions must be accurate, so that it benefits most of the cases. On the other hand, predictions should be fast. The problem is that accuracy is increased by storing more information and using more complex algorithms, which increases prediction latency.<br/>This thesis presents different strategies and performs several proposals to increase the global performance of a control flow predictor. Prediction data are efficiently arranged and codified to allow the predictor to adapt to the different prediction cases. Frequent and simple predictions are performed very fast and consume little resources, while less frequent predictions or those that use more information to achieve higher accuracies are performed more slowly. A flexible design combined with an excess of prediction bandwidth compensates complex and slow cases with the more frequent simple and fast cases. The overall result is higher prediction bandwidth, both due to an increase in prediction rate and also an increase in prediction width. This is achieved without reducing prediction accuracy and with moderate energy consumption.<br/>The strategies used to augment prediction speed are way prediction, index prediction, and a two-level hierarchy of predictors. Trace prediction is proposed to increase prediction width. An efficient mechanism enhances the previous proposals in the literature. In all cases, prediction accuracy is not reduced and memory requirements are slightly increased. Finally, a new two-level organization is used for predicting indirect jumps, which increases prediction accuracy for a fixed amount of memory.<br/>This thesis does not address new methods to increase prediction accuracy, but a more efficient predictor has a lateral effect of providing more resources to increase accuracy. On the one hand, there is more capability to store past branch history. On the other hand, prediction latency is more easily tolerated, which allows applying more complex algorithms to improve prediction accuracy.