Representar saltos de bucle en un registro de historia de saltos con múltiples bits.

Un procedimiento de predicción de saltos, que comprende:

determinar que una instrucción de salto condicional es una instrucción de final de bucle;

contar un número total de iteraciones de un bucle finalizado por la instrucción de final de bucle;

almacenar un valor de múltiples bits en un Registro de Historia de Saltos, BHR, tras la finalización del bucle,el valor indicativo del número total de iteraciones del bucle, y

indexar una Tabla de Predicción de Saltos, BPT, con el BHR, después de la finalización del bucle, paraobtener una predicción de saltos.

Representar saltos de bucle en un registro de historia de saltos con múltiples bits

CAMPO

La presente invención se refiere en general al campo de los procesadores y, en particular a un procedimiento de representación de los saltos de bucle en un registro de historia de saltos con múltiples bits.

ANTECEDENTES

Los microprocesadores realizan tareas de cálculo en una amplia variedad de aplicaciones. Un rendimiento mejorado del procesador es casi siempre deseable, para permitir un funcionamiento más rápido y/o mayor funcionalidad a través de cambios en el software. En aplicaciones empotradas comunes, tales como dispositivos electrónicos portátiles es también deseable ahorrar energía.

Los procesadores modernos comunes utilizan una arquitectura con línea de ejecución, en la que instrucciones secuenciales, cada una con varias etapas de ejecución, se solapan durante la ejecución. Para un máximo rendimiento, las instrucciones deben fluir continuamente a través de la línea de ejecución. Cualquier situación que provoque que las instrucciones se paralicen en la línea de ejecución afecta negativamente al rendimiento. Si las instrucciones deben ser eliminadas de la línea de ejecución y, a continuación, volver a cargarlas, el rendimiento y el consumo de energía pueden verse afectados.

Normalmente todos los programas del mundo real incluyen instrucciones de salto condicional, el comportamiento de salto real de las cuales no se conoce, normalmente, hasta que la instrucción se evalúa dentro de la línea de ejecución. Para evitar una paralización que pueda resultar de esperar por la evaluación real de la instrucción de salto, los procesadores modernos comunes utilizan alguna forma de predicción de saltos, por la cual el comportamiento de salto de las instrucciones de salto condicional se prevé al principio de la línea de ejecución. Sobre la base de la evaluación prevista de salto, el procesador carga de forma especulativa (precarga) y ejecuta las instrucciones de una dirección prevista, ya sea la dirección de destino de salto (si se prevé que se saltará) o la siguiente dirección secuencial después de la instrucción de salto (si se prevé que no se saltará) . Una vez que se determina el comportamiento real del salto, si el salto se predijo incorrectamente, las instrucciones cargadas de forma especulativa deben ser eliminadas de la línea de ejecución, y deben cargarse nuevas instrucciones a partir de la siguiente dirección correcta. Precargar instrucciones en respuesta a una predicción incrorecta de salto impacta de manera negativa el rendimiento del procesador y el consumo de energía. En consecuencia, es deseable mejorar la precisión de predicción de saltos.

Las técnicas conocidas de predicción de salto incluyen tanto predicciones estáticas como dinámicas. El comportamiento probable de algunas instrucciones de salto puede ser previsto de forma estática por un programador y/o compilador. Un ejemplo es una rutina de comprobación de errores. El código común se ejecuta correctamente, y los errores son escasos. Por lo tanto, la instrucción de salto que implementa una función de "salto en caso de error" evaluará "no se saltará" un porcentaje muy alto de las veces. Tal instrucción puede incluir un bit de predicción estática de predicción estática de saltos en el código de operación, fijada por un programador o compilador con conocimiento del resultado común probable de la condición de salto.

La predicción dinámica se basa generalmente en la historia de evaluación de saltos (y en algunos casos, la precisión de la historia de evaluación de saltos) de la instrucción que se está prediciendo y/u otras instrucciones de salto en el mismo código. Un análisis exhaustivo de código real indica que los patrones de evaluación de salto del pasado reciente pueden ser un buen indicador de la evaluación de las futuras instrucciones de salto.

Una forma conocida de predicción de salto dinámica, representada en la Figura 1, utiliza un Registro de Historia de Saltos (BHR) 100 para almacenar las n evaluaciones de salto anteriores. En una implementación simple, el BHR 30 comprende un registro de desplazamiento. El resultado común de evaluación de salto reciente se introduce (por ejemplo, un 1 indicando se hizo el salto y un 0 indicando que no se hizo se hizo el salto) , siendo desplazada la evaluación pasada más antigua en el registro. Un procesador puede mantener un BHR local 100 por cada instrucción de salto. Alternativamente (o adicionalmente) , un BHR 100 puede contener las evaluaciones anteriores recientes de todas las instrucciones de salto condicional, a veces conocidos en la técnica como BHR global, o GHR. Tal y como se usa en este documento, BHR denomina tanto a Registros de Historia de Saltos locales como globales.

Tal y como se muestra en la Figura 1, el BHR 100 puede indexar una Tabla de Predicción de Saltos (BPT) 102, que puede ser también local o global. El BHR 100 puede indexar la BPT 102 directamente, o puede combinarse con otra información, como por ejemplo el contador de programa (PC) de la instrucción de salto en la lógica de indexación de

BPT 104. Además, se pueden utilizar otras entradas a la lógica de indexación de BPT 104. La lógica de indexación de BPT 104 puede concatenar las entradas (conocido en la técnica como gselect) , realizar una operación OR-Exclusiva de las entradas (gshare) , lleve a cabo una función hash, o combinar o transformar los datos de una variedad de maneras.

Como un ejemplo, la BPT 102 puede comprender una pluralidad de contadores de saturación, los MSB de los cuales sirven como predictores de salto bimodales. Por ejemplo, cada entrada de la tabla puede comprender un contador de 2 bits que asume uno de cuatro estados, cada uno asignado un valor ponderado de predicción, tales como:

11. Muy esperado se saltará

- Débilmente esperado se saltará

01 - Débilmente esperado no se saltará

00 - Muy esperado no se saltará

El contador se incrementa cada vez que una instrucción de salto correspondiente evalúa "se saltará" y disminuye cada vez que la instrucción se evalúa "no se saltará." El MSB del contador es un predictor de saltos bimodal, predecirá si se saltará o no se saltará, independientemente de la fuerza o el peso de la predicción subyacente. Un contador de saturación reduce el error de predicción de una dirección infrecuente de evaluación de salto. Un salto que se evalúa de forma consistente saturará el contador. Una evaluación infrecuente, por otro lado, alterará el valor del contador (y la fuerza de la predicción) , pero no el valor de predicción bimodal. Por lo tanto, una evaluación infrecuente sólo predecirá incorrectamente una vez, no dos veces. La tabla de contadores de saturación es un ejemplo únicamente ilustrativo, en general, una BHT puede indexar una tabla que contiene una variedad de mecanismos de predicción de salto.

Independientemente del mecanismo de predicción de saltos empleado en la BPT 102, el BHR 100 - ya sea solo o en combinación con otra información tal como el PC de la instrucción de salto - indexa la BPT 102 para obtener predicciones de salto. Almacenando las evaluaciones de salto anteriores en el BHR 100 y utilizando las evaluaciones en la predicción de saltos, la instrucción de salto que está prediciendo se correla con el comportamiento del salto en el pasado - su propio comportamiento en el pasado en el caso de un BHR local 100 y con el comportamiento de otras instrucciones de salto en el caso de un BHR global 100. Esta correlación es la clave para predicciones exactas de saltos, al menos en el caso de código altamente repetitivo.

Nótese que la Figura 1 muestra las evaluaciones de salto almacenándose en el BHR 100 - es decir, la evaluación real de una instrucción de salto condicional, que sólo puede ser conocida una vez la línea de ejecución ha avanzado bastante, tal como en una etapa de ejecución de la línea de ejecución. Mientras que esto es el resultado final, en la práctica, los procesadores comunes de alto rendimiento almacenan la evaluación de salto prevista a partir de la BPT 102 en el BHR 100, y corrigen el BHR 100 más adelante como parte de una operación de recuperación de predicción errónea si la predicción resulta ser errónea. Las figuras de los dibujos no reflejan esta característica de la aplicación, para una mayor claridad.

Una estructura de código común que puede reducir la eficacia de un... [Seguir leyendo]

1. Un procedimiento de predicción de saltos, que comprende: determinar que una instrucción de salto condicional es una instrucción de final de bucle; 5 contar un número total de iteraciones de un bucle finalizado por la instrucción de final de bucle;

almacenar un valor de múltiples bits en un Registro de Historia de Saltos, BHR, tras la finalización del bucle, el valor indicativo del número total de iteraciones del bucle, y indexar una Tabla de Predicción de Saltos, BPT, con el BHR, después de la finalización del bucle, para

obtener una predicción de saltos.

2. El procedimiento según la reivindicación 1, en el que determinar que una instrucción de salto condicional es una instrucción de salto de final de bucle comprende detectar que el salto condicional es hacia atrás.

3. El procedimiento según la reivindicación 1, en el que determinar que una instrucción de salto condicional es una instrucción de salto de final de bucle comprende detectar que un contador de programa, PC de lainstrucción de salto coincide con el contenido de un PC de Último Salto, LBPC, registro que almacena PCs de

la última pluralidad de instrucciones de salto para actualizar el BHR.

4. El procedimiento según la reivindicación 3 en el que la instrucción de salto es un tipo particular de instrucción de salto utilizada únicamente para saltos de final de bucle y generada por un compilador para finalizar bucles.

5. El procedimiento según la reivindicación 1, en el que almacenar un valor de múltiples bits en el BHR comprende almacenar un número predeterminado de bits en el BHR.

6. El procedimiento según la reivindicación 5 que comprende además determinar el valor del número predeterminado de bits según una asignación entre el número de iteraciones de bucle y el valor de múltiples bits.

7. El procedimiento según la reivindicación 1, en el que almacenar un valor de múltiples bits en el BHR

comprende almacenar un número variable de bits en el BHR, el número de bits variando en respuesta al 25 número total de iteraciones del bucle.

8. El procedimiento según la reivindicación 7 que comprende además almacenar iteraciones de bucle en la pluralidad de bits menos significativa del BHR.

9. El procedimiento según la reivindicación 7 que comprende además contar iteraciones de bucle en un contador de bucle, y transferir el valor del contador de bucle al BHR cuando el bucle finaliza.

10. El procedimiento según la reivindicación 1, en el que la etapa de determinar comprende detectar una primera instrucción de salto de final de bucle asociada con un primer bucle y una segunda instrucción de salto de final de bucle asociada con un segundo bucle, el primer bucle anidado dentro del segundo bucle.

11. Un procesador, que comprende: un predictor de saltos operable para predecir la evaluación de instrucciones de salto condicional;

una línea de ejecución de instrucciones operable para cargar y ejecutar de forma especulativa instrucciones en base a una predicción del predictor de saltos; un Registro de Historia de Saltos, BHR, en el predictor de saltos operable para almacenar la evaluación de

las instrucciones de salto condicional; un Contador de Bucle, LC, en el predictor de saltos operable para contar un número total de iteraciones de un 40 bucle de código; un circuito de control operable para almacenar en el BHR un valor de múltiples bits indicativo del número total de iteraciones de un bucle asociado con una instrucción de salto condicional tras la terminación del bucle, y

una trabla de predicción de saltos, BPT, en el predictor de saltos, indexada por el BHR, tras la terminación del bucle, operable para conseguir una predicción de saltos.

12. El procesador según la reivindicación 11 que comprende además un registro PC de Último Salto, LBPC, operable para almacenar un contador de programa, PC, de una instrucción de salto condicional, y en el que el

circuito de control determina que una instrucción de salto condicional está asociada con un bucle si el PC de la instrucción de salto coincide con el contenido del registro LBPC.

13. El procesador según la reivindicación 12 que comprende además dos o más registros LBPC y dos o más LC correspondientes, un primer LBPC operable para almacenar el PC de una instrucción de salto condicional asociada con un primer bucle y un primer LC operable para mantener una cuenta de iteraciones del primer

bucle, y un segundo LBPC operable para almacenar el PC de una instrucción de salto condicional asociada con un segundo bucle y un segundo LC operable para mantener una cuenta de iteraciones del segundo bucle, en el que el primer bucle está anidado dentro del segundo bucle.

14. El procesador según la reivindicación 11 en el que el BHR es operable para incrementar una pluralidad de

bits en respuesta a cada evaluación tomada de la instrucción de salto condicional asociada con el bucle de 15 forma que mantiene una cuenta de iteraciones del bucle directamente en el BHR.

15. El procesador según la reivindicación 11 comprende además lógica de umbralización operable para asignar una cuenta de iteraciones de bucle a un valor de fijo, de múltiples bits en respuesta a la pluralidad de valores de umbral.

16