ES2351163T3 - Supresión de la actualización de un registro del histórico de ramificaciones por ramificaciones de fin de bucle. - Google Patents

Supresión de la actualización de un registro del histórico de ramificaciones por ramificaciones de fin de bucle. Download PDF

Info

Publication number
ES2351163T3
ES2351163T3 ES06735979T ES06735979T ES2351163T3 ES 2351163 T3 ES2351163 T3 ES 2351163T3 ES 06735979 T ES06735979 T ES 06735979T ES 06735979 T ES06735979 T ES 06735979T ES 2351163 T3 ES2351163 T3 ES 2351163T3
Authority
ES
Spain
Prior art keywords
branching
instruction
branch
loop
bhr
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
ES06735979T
Other languages
English (en)
Inventor
Bohuslav Rychlik
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Qualcomm Inc
Original Assignee
Qualcomm Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Qualcomm Inc filed Critical Qualcomm Inc
Application granted granted Critical
Publication of ES2351163T3 publication Critical patent/ES2351163T3/es
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/32—Address formation of the next instruction, e.g. by incrementing the instruction counter
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3802—Instruction prefetching
    • G06F9/3804—Instruction prefetching for branches, e.g. hedging, branch folding
    • G06F9/3806—Instruction prefetching for branches, e.g. hedging, branch folding using address prediction, e.g. return stack, branch history buffer
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/32—Address formation of the next instruction, e.g. by incrementing the instruction counter
    • G06F9/322—Address formation of the next instruction, e.g. by incrementing the instruction counter for non-sequential address
    • G06F9/325—Address formation of the next instruction, e.g. by incrementing the instruction counter for non-sequential address for loops, e.g. loop detection or loop counter
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G06F9/3842—Speculative instruction execution
    • G06F9/3844—Speculative instruction execution using dynamic branch prediction, e.g. using branch history tables

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Advance Control (AREA)
  • Devices For Executing Special Programs (AREA)
  • Executing Machine-Instructions (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Debugging And Monitoring (AREA)
  • Radar Systems Or Details Thereof (AREA)
  • Molds, Cores, And Manufacturing Methods Thereof (AREA)
  • Transition And Organic Metals Composition Catalysts For Addition Polymerization (AREA)

Abstract

Procedimiento de predicción de ramificación, caracterizado porque comprende la supresión de una actualización de un Registro de Histórico de Ramificación (BHR) durante la ejecución de una instrucción de ramificación, en respuesta a la determinación de que la instrucción de ramificación es una instrucción de ramificación de fin de bucle.

Description

Antecedentes
La presente invención se refiere generalmente al campo de los procesadores y en particular a un procedimiento para mejorar la predicción de ramificaciones suprimiendo la actualización de un registro del histórico de ramificaciones por una instrucción de ramificaciones de fin de bucle.
Los microprocesadores llevan a cabo tareas computacionales en una amplia variedad de aplicaciones. La prestación mejorada de los procesadores es casi siempre deseable, para permitir un funcionamiento más rápido y/o una mayor funcionalidad a través de los cambios de software. En muchas aplicaciones integradas, tales como dispositivos electrónicos portátiles, conservar la energía es también un objetivo den la implementación y diseño de los procesadores.
Muchos procesadores de módem emplean arquitectura canalizada donde se ejecutan instrucciones secuencias, teniendo cada una múltiples etapas de ejecución. Para un rendimiento mejorado, las instrucciones deberían fluir continuamente a través de la línea de ensamble. Cualquier situación que hace que las instrucciones pierdan velocidad en la línea de ensamble puede influir negativamente sobre el rendimiento. Si las instrucciones se descartan de la línea de ensamble y a continuación se vuelven a extraer, sufren tanto el rendimiento como el consumo de energía.
La mayoría de los programas incluyen instrucciones de ramificación condicional, cuyo propio comportamiento de ramificación es desconocido hasta que se evalúa la instrucción tarde en la línea de ensamble. Para evitar la pérdida de velocidad que se produciría de la espera de la propia evaluación de la instrucción de ramificación, los procesadores módem pueden emplear alguna forma de predicción de ramificación, con lo cual el comportamiento de ramificación de las instrucciones de ramificación condicional se predice pronto en la línea de ensamble. Basado en la evaluación de ramificación predicha, el procesador extrae especulativamente (preextrae) y ejecuta instrucciones de una dirección predicha – bien la dirección diana de ramificación (si se predice que se ha de tomar la ramificación) o la siguiente dirección secuencia después de la instrucción de ramificación (si se predice que la ramificación no se ha de tomar). Cuando se determina el propio comportamiento de ramificación, si la ramificación se ha predicho erróneamente, las instrucciones extraídas de manera especulativa se deben descartar de la línea de ensamble, y se extraen nuevas instrucciones de la siguiente dirección correcta. Preextraer instrucciones en respuesta a una predicción de ramificación errónea puede incidir negativamente sobre el rendimiento y el consumo de energía del procesador. En consecuencia, mejorar la precisión de la predicción de ramificación es un objetivo importante de diseño.
Las técnicas conocidas de predicción de ramificación incluyen tanto predicciones estáticas como dinámicas. El probable comportamiento de algunas instrucciones de ramificación se puede predecir estáticamente mediante un programador y/o un compilador. Un ejemplo de predicción de ramificación es una rutina de verificación de errores. Comúnmente el código ejecuta apropiadamente, y los errores son raros. De este modo, la instrucción de ramificación que ejecuta una función “ramificación en error” evaluará “no tomada” un porcentaje muy elevado del tiempo. Tal instrucción puede incluir un bit de predicción de ramificación estática en el código operacional, establecido por un programador o compilador con conocimiento del resultado más probable de la condición de ramificación.
La predicción dinámica se basa generalmente en el histórico de evaluación de ramificación (y en algunos casos el histórico de precisión de predicción de ramificación) de la instrucción de ramificación que se está prediciendo y/o otras instrucciones de ramificación en el mismo código. El análisis exhaustivo del propio código indica que modelos de evaluación de ramificaciones en un pasado reciente pueden ser un buen indicador de la evaluación de futuras instrucciones de ramificación.
Una forma conocida de predicción de ramificación dinámica, representada en la figura 1 utiliza un Registro de Histórico de Ramificaciones (BHR) 100 para poner en memoria las n pasadas evaluaciones de ramificación. En una ejecución sencilla, el BHR 30 comprende un registro de desplazamiento. El resultado de evaluación de ramificación más reciente se desplaza en (por ejemplo, un 1 que indica una ramificación tomada y un 0 que indica una ramificación no tomada), con la evaluación más antigua en el registro desplazada. Un procesador puede mantener un BHR local 100 para cada instrucción de ramificación. Alternativamente (o adicionalmente), un BHR 100 puede contener las evaluaciones de pasado reciente de todas las instrucciones de ramificación condicional, a veces conocidas en la técnica como BHR global, o GHR. Tal como se usa en la presente memoria descriptiva, BHR se refiere tanto a registros del histórico de ramificaciones locales como globales.
Tal como se representa en la figura 1, el BHR 100 puede indexar una Tabla de Predictor de Ramificación (BPT), que de nuevo puede ser local o global. El BHR puede indexar la BPT 102 directamente, o se puede combinar con otra información, tal como el Contador de Programa (PC) de la instrucción de ramificación en la lógica de índice BPT 104. Se pueden utilizar adicionalmente otras entradas en la lógica de índice BPT 102. La lógica de índice BPT 104 puede concatenar las entradas (comúnmente conocidas en la técnica como gselect), aplicar la función XOR a las entradas (gshare), llevar a cabo una función hash o combinar o transformar las entradas de varias maneras.
A modo de ejemplo, la BPT 102 puede comprender una pluralidad de contadores de saturación, cuyos MSBs sirven de predictores de tramificaciones bimodales. Por ejemplo, cada entrada de tabla puede comprender un contador de 2 bits que asume uno de cuatro estados, cada uno asignado a un valor de predicción ponderado, tal como
11 –predicho fuertemente tomado
10.-predicho débilmente tomado
01.-predicho débilmente no tomado
00 –predicho fuertemente no tomado
El contador se incrementa cada vez que una instrucción correspondiente de ramificación evalúa “tomado” y se reduce cada vez que la instrucción evalúa “no tomado”. El MSB del contador es un predicor de ramificación bimodal; predecirá que una rama sea tomada o no tomada, sin tener en cuenta la fuerza o el peso de la predicción subyacente. Un contador de saturación reduce el error de predicción de una evaluación de ramificación infrecuente. Una ramificación que evalúa consistentemente de una manera saturará el contador. Una evaluación infrecuente de la otra manera alterará el valor de contador (y la fuerza, de la predicción) pero no el valor de predicción bimodal. De este modo una evaluación infrecuente solamente predecirá erróneamente una vez, no dos. La tabla de contadores de saturación es un ejemplo ilustrativo solamente; en general, una BHT puede indexar una tabla que contiene varios mecanismos de predicción de ramificaciones.
Con independencia del mecanismo empleado de predicción de ramificación en la BPT 102, el BHR 100, bien solo o en combinación con otra información tal como el PC de instrucción de ramificación – indexa la BPT 102 para obtener predicciones de ramificación. Poniendo en memoria las evaluaciones de ramificación anteriores en el BHR 100 y usando las evaluaciones en la predicción de ramificación, la instrucción de ramificación predica se correlaciona con el comportamiento pasado de ramificaciones – su propio comportamiento pasado en el caso de un BHR local 100 y el comportamiento de otras instrucciones de ramificación en el caso de un BHR global 100. Esta correlación puede ser la clave para precisar predicciones de ramificación, al menos en el caso de un código altamente repetitivo.
Obsérvese que la figura 1 representa evaluaciones de ramificaciones puestas en memoria en el BHR 100, es decir, la propia evaluación de una instrucción de ramificación condicional, que solamente se puede conocer tarde en la línea de ensamble, tal como en una etapa de línea de ejecución. Mientras este es el resultado final, en la práctica, muchos procesadores de alto rendimiento memorizan la evaluación de ramificación predicha a partir de la BPT 102 en el BHR 100, y corrigen el BHR 100 más tarde como parte de una operación de recuperación de predicción incorrecta si la predicción resulta ser errónea. Por motivos de claridad, las figuras de los dibujos no reflejan esta característica de implementación.
Una estructura de código común que puede reducir la eficacia de un predictor de ramificación que emplea un BHR 100 es el bucle. Un bucle termina con una instrucción de ramificación condicional que ensaya una condición de fin de bucle, tal como una variable de índice que se incrementa cada vez que a través del bucle se alcanza un valor de fin de bucle. En caso contrario, las ramificaciones de ejecución vuelven al principio del bucle para otra iteración, y otra evaluación de rama condición de fin de bucle. Respecto de un BHR de n bits 100 hay tres casos de interés relativos a bucles: el bucle no se ejecuta; el bucle se ejecuta a través m iteraciones, donde m < n; y el bucle se ejecuta m veces, donde m >=n.
Si el bucle no se ejecuta, una ramificación hacia delante en la ramificación de inicio de bucle sobre el cuerpo de bucle, dando como resultado una evaluación de ramificación tomada. Esto tiene un mínimo efecto sobre el BHR 100, ya que el histórico de evaluaciones de ramificaciones en el BHR 100 se desplaza solamente en una evaluación de ramificación (de hecho, la precisión de predicción se puede mejorar por correlación con esta evaluación de ramificación).
Si el bucle se ejecuta a través de m iteraciones donde m >= n, las ramificaciones “tomadas” hacia atrás de la instrucción de ramificación de fin de bucle saturan el BHR 100. Es decir, al final del bucle, un BHR de n bits siempre contendrá precisamente n-1 bits seguido de un simple cero, lo cual corresponde a una larga serie de evaluaciones tomadas resultantes de las iteraciones de bucle, y que terminan con una simple evaluación no tomada cuando se termina el bucle. Esto destruye efectivamente la eficacia del BHR 100, ya que se pierden todas las correlaciones con evaluaciones de ramificaciones anteriores (tanto para BHR local como global 100). En este caso, el BHR 100 se cartografiará probablemente en la misma entrada de BPT 102 para una instrucción de ramificación dada (dependiendo de las otras entradas a la lógica 104 de índice de BPT), en lugar de en una entrada que contiene una predicción de ramificación que refleja la correlación de la instrucción de ramificación con las evaluaciones de ramificación anteriores.
Asimismo, le BHR saturado 100 puede aumentar el solapamiento en el BPT 102, Es decir, todas las instrucciones de ramificaciones que siguen bucles son muchas iteraciones se cartografiarán en la misma entrada de BPT 102, si el BHR 100 indexa directamente la BPT 102. Incluso allí donde el BHR 100 se combina con otra información, se incrementa la posibilidad de solapamiento. Eso afecta negativamente la precisión de predicción no solamente para la
instrucción de ramificación que sigue al bucle, sino también todas las instrucciones de ramificaciones que se solapan en su entrada en la BPT 102. Si el bucle se ejecuta n iteraciones, donde m < n, el BHR 100 no se satura y se retiene el histórico de evaluaciones de ramificaciones anteriores. Sin embargo, los bits que
5 representan el histórico de evaluaciones de ramificaciones anteriores se desplazan en posiciones de m bits. Particularmente, donde m varía, este tiene dos efectos deletéreos en la predicción de ramificaciones. En primer lugar, la instrucción de ramificación se cartografiará en un número mucho mayor de entradas en la BPT 102 para capturar la misma correlación con evaluaciones de ramificaciones anteriores, lo cual requiere una mayor BPT 102 para soportar la
10 misma precisión para el mismo número de instrucciones de ramificaciones que las requeridas sin que la ramificación de fin de bucle afecte al BHR 30. En segundo lugar, los predictores de ramificaciones en la BPT 102 llevará más tiempo para “formarse” aumentando la cantidad de código que se debe ejecutar antes de que la BPT 102 empiece a proporcionar preediciones de ramificación precisas.
15 A modo de ejemplo, se considera un BHR de 8 bits 100 y un segmento de código con instrucciones de ramificaciones A-H, seguidas de un bucle, y a continuación la instrucción de ramificación X. La ramificación X se correlaciona fuertemente con el histórico de evaluaciones de ramificaciones G y H. Varias iteraciones del bucle de intervención generará los resultados de BHR presentados en la siguiente Tabla 1, en el momento de predecir X.
20
BHR
Comentarios
A
B C D E F G H bucle ejecutado una vez (sin ramificación hacia atrás de fin de bucle o hacia delante inicial tomada)
B
C D E F G H 1 bucle saltado (una ramificación hacia delante inicial tomada)
C
D E F G H 1 0 iteraciones (ramificación hacia atrás de fin de bucle tomada una vez, a continuación no tomada)
D
E F G H 1 1 0 3 iteraciones
E
F G H 1 1 1 0 4 iteraciones
F
G H 1 1 1 1 0 5 iteraciones
G
G
1 1 1 1 1 0 6 iteraciones
Tabla 1: BHR 100 Contenido según varios números de iteraciones de bucle
En este ejemplo, la correlación deseada entre la instrucción de ramificación X predicha y la evaluación anterior de ramificaciones G y H está presente en el BHR 100 en cada caso. Sin embargo, está en un lugar diferente en el BHR 100, y en consecuencia cada caso se cartografiará en una entrada de BPT 102 diferente. Estos desperdician espacio de la BPT 102, aumenta el tiempo de formación de predicción de ramificaciones, y aumenta las posibilidades de solapamiento en la BPT 102, todo lo cual reduce la precisión de predicción.
Po-Yung Chang et al.: “Improving branch prediction accuracy by reducing pattern history table interference” Parallel Architectures and Compilation Techniques, 1996., Proceedings of the 1996 Conference on Boston, MA, EEUU, 20-23 octubre 1996. Los Alamitos, CA UU.UU, IEEE Comput. Soc. US, 20 de octubre 1996 (20-10-1996), páginas 48-57, XP010199404 ISBN 0-8 186-7632-9 ilustra la supresión de una actualización de la BHT (PHT) para evitar la interferencia en la BHT.
SUMARIO
En una o más realizaciones de la presente invención como se establece en las reivindicaciones anexas, los efectos deletéreos de la puesta en memoria de evaluaciones de instrucciones de ramificaciones de fin de bucle en una BHR se mejoran identificando las instrucciones de ramificaciones de fin de bucle, y suprimiendo la actualización del BHR en respuesta a las instrucciones de fin de bucle. Las instrucciones de fin de bucle se identifican de varias maneras.
En una realización, un procedimiento de predicción de ramificación, comprende opcionalmente suprimir una actualización de un BHR durante la ejecución de una instrucción de ramificación, en respuesta a una propiedad de la instrucción de ramificación.
En otra realización, un procesador incluye un predictor de ramificación operativo para predecir la evaluación de instrucciones de ramificación condicional, y una línea de ensamble de ejecución de instrucciones (12) operativa para extraer y ejecutar de manera especulativa instrucciones basadas en una predicción procedente del predictor de ramificación. El procesador también incluye un BHR operativo para poner en memoria la evaluación de instrucciones de ramificación condicional, y un circuito de control operativo para suprimir la puesta en memoria de la evaluación de una instrucción de ramificación condicional en respuesta a una propiedad de la instrucción de ramificación.
En otra realización, un compilador o ensamblador operativo para generar instrucciones en respuesta al código de programa incluye una función de marcado de instrucción de ramificación de fin de bucle operativa para indicar instrucciones de ramificaciones de fin que terminan los bucles de código.
BREVE DESCRIPCIÓN DE LOS DIBUJOS
La figura 2 representa un diagrama funcional de bloques de un procesador 10. El procesador 10 ejecuta instrucciones en una línea de ensamble 12 de ejecución de instrucciones según la lógica de control 14. en algunas realizaciones, la línea de ensamble 12 puede ser un diseño superescalar, con múltiples líneas de ensamble paralelas. La línea de ensamble 12 incluye varios registros o cerrojos 16, organizados en etapas de líneas canalizadas y una o más Unidades lógicas aritméticas (ALU) 18. Un fichero de Registro Universal (GPR) 20 proporciona registros que comprenden la parte superior de la jerarquía de memoria.
La línea de ensamble 12 extrae instrucciones procedentes de una memoria caché (caché I) 22 con conversión y permiso de dirección de memoria gestionados por una memoria intermedia de conversión del lado de las instrucciones (ITLB) 24. Cuando las instrucciones de ramificación condicional se descodifican pronto en la línea de ensamble 12, un predictor de ramificación 26 predice el comportamiento de ramificaciones, y proporciona la predicción a una unidad de preextracción de instrucción 28. La unidad de preextracción de instrucción 28 extrae especulativamente instrucciones procedentes de la memoria caché 22, en una dirección diana de ramificación calculada en la línea de ensamble 12 para predicción de ramificación “tomada”,
o en la siguiente dirección secuencia para ramificaciones predichas “no tomadas”. En cualquier caso, las instrucciones preextraídas se cargan en la línea de ensamble 12 para ejecución especulativa.
El predictor de ramificación 26 incluye un Registro de Histórico de Ramificaciones (BHR), una Tabla de Predictor de Ramificación (BPT) 32, una lógica de índice BPT 34, y una lógica de actualización BHR 36. El predictor de ramificación 26 puede incluir, adicionalmente, uno o más registros de PC de última ramificación 38, descritos más en detalle más adelante en la presente memoria descriptiva.
Se accede a los datos desde una memoria caché de datos (caché D) 40, con conversión y permisos de dirección de memoria gestionados por una Memoria Intermedia de conversión (TLB) 42. En varias realizaciones, la ITLB 24 puede comprender una copia de parte de la TLB
42. Alternativamente, se pueden integrar la ILTB 24 y la TLB 42. Asimismo, en varias realizaciones del procesador 10, se pueden integrar o unificar la memoria caché I 22 y la memoria caché D 40. Los fallos en la memoria caché I 22 y la memoria caché D 40 causa un acceso a la memoria principal (fuera de chip) 44, bajo el control de una interfaz de memoria 46.
El procesador 10 puede incluir una interfaz 46 de entrada/salida (E/S), que controla el acceso a varios dispositivos periféricos 50. El experto en la técnica reconoce que son posibles numerosas variaciones del procesador 10. Por ejemplo, el procesador 10 puede incluir una memoria caché de segundo nivel (L2) para uno de las dos o ambas memorias caché I y D 22,
40. Además, uno o más de los bloques funcionales representados en el procesador 10 se puede omitir de una realización particular.
Según una o más realizaciones, se mejora la precisión de predicción de ramificación evitando que las ramificaciones de fin de bucle corrompan uno o más BHR 30 en el predictor de ramificación 36. Este proceso se representa como un diagrama de flujo en la figura 3. Se descodifica (boque 52) una instrucción de ramificación condicional. Se realiza una determinación si la ramificación es una ramificación de fin de bucle (bloque 54). En caso contrario, el BHR 30 se actualiza para registrar la evaluación de ramificación (bloque 56), es decir, si se evalúa la instrucción de ramificación como “tomada” o “no tomada”. A continuación, la ejecución sigue (bloque 58), en la dirección diana de ramificación o la siguiente dirección secuencial, respectivamente. Si la ramificación no es una ramificación de fin de bucle, la actualización del BHR 30 para registrar la evaluación de ramificación de la instrucción de ramificación de fin de bucle se suprime (como se indica mediante la trayectoria del bloque 54 al bloque 58). De esta manera, las ramificaciones de iteración de bucle no corrompen el contenido del BHR 30 desplazando el histórico de evaluaciones de ramificaciones relevantes. La petición (bloque 54), que identifica una instrucción de ramificación como instrucción de ramificación de fin de bucle-se puede conseguir de varias maneras.
Los bucles se iteran por ramificación hacia atrás desde el final del bucle hasta el inicio del bucle. Según una realización, se asume que cada instrucción de ramificación condicional con una dirección diana de ramificación inferior a la dirección de instrucción de ramificación o PC, es decir, una ramificación hacia atrás, para que sea una instrucción de ramificación de fin de bucle, y se evita la actualización del BHR 30. Esta realización ofrece la ventaja de la simplicidad. El PC de instrucción de ramificación se compara con la dirección diana de ramificación (BTA) cuando la instrucción de ramificación se evalúa efectivamente en la línea de ensamble, en el momento de actualización de BHR 30. Si BTA < PC, no se actualiza el BHR
30. Esta realización tiene la desventaja de requerir una comparación de direcciones cuando se determina la dirección diana de ramificación, y también de que algunas ramificaciones hacia atrás que no son ramificaciones de fin de bucle no tendrán sus evaluaciones registradas en el BHR 30.
Otra manera de detectar una ramificación de fin de bucle es reconocer la ejecución repetida de la misma instrucción de ramificación. En una realización, representada en la figura 4, un registro de PC de última ramificación (LBPC) 38 memoriza el PC de la instrucción de última ramificación cuya evaluación se memoriza en el BHR 30. En el caso de un simple bucle, si el PC de una instrucción de ramificación coincide con el LBPC 38, es decir, la instrucción de ramificación fue la instrucción de última ramificación evaluada, se asume la instrucción de ramificación ha de ser una instrucción de ramificación de fin de bucle, y se suprime una actualización adicional del BHR 30. Como se ha mencionado anteriormente respecto de la figura 1, mientras la figura 4 representa el contenido del LBPC 38 que se compara con la propia evaluación de ramificación en la lógica de actualización de BHR 36, en cualquier implementación dada, el LBPC 38 se puede comparar con una evaluación de ramificación predicha, con la BHR 30 corregida en el caso de una predicción incorrecta. Esta realización memoriza solamente la primera iteración del bucle, desplazando solamente una evaluación de ramificación anterior del BHR 30. Esta realización no requiere soporte del compilador, y no se necesita determinar la dirección de la ramificación en el momento de la actualización de BHR
30.
Un bucle puede contener uno o más bucles anidados, o puede incluir otras ramificaciones dentro del bucle. En este caso, la saturación del BHR 30 por un bucle interior se puede suprimir por el enfoque de LBPC; sin embargo, las ramificaciones de fin de bucle seguirán memorizadas en el BHR 30. En una realización, se puede proporcionar dos o más registros LBPC 38, con los PC de instrucciones de ramificación sucesivamente evaluadas memorizadas en registros LBPC correspondientes (LBPC0, LBPC1,....LBPCM) 38. La actualización del BHR 30 se puede suprimir si el PC de una instrucción de ramificación coincide con cualquiera de los registros de LBPCN 38.
Las instrucciones de ramificación de fin de bucle se pueden también marcar estáticamente mediante un compilador o ensamblador. En una realización, un compilador genera un tipo particular de instrucción de ramificación que se usa solamente para ramificaciones de fin de bucle, por ejemplo, “BRLP”. Se reconoce la instrucción BRLP, y el BHR 30 nunca se actualiza cuando se evalúa la instrucción BRPE en una etapa de línea de ensamble de ejecución. En otra realización, un compilador o ensamblador puede integrar una indicación de ramificación de fin de bucle en una instrucción de ramificación, como por ejemplo estableciendo uno o más bits predefinidos en el código de operación. Los bits de ramificación de fin de bucle se detectan y se suprime la actualización del BHR cuando se evalúa esa instrucción de ramificación en una etapa de línea de ensamble ejecutada. La identificación estática de ramificaciones de fin de bucle reduce la complejidad de hardware y computacional moviendo la función de identificación de fin de bucle dentro del compilador o ensamblador.
Una instrucción de ramificación condicional tiene muchas propiedades, incluyendo por ejemplo, la dirección de instrucción de ramificación o PC, el tipo de instrucción, y la presencia o no de bits indicadores en el código de operación. Como se usa en la presente memoria descriptiva, las propiedades de la operación de ramificación, y/o las propiedades del programa
5 que se refieren a la ramificación, se consideran propiedades de la instrucción de ramificación. Por ejemplo, si el PC de instrucción de ramificación coincide con el contenido de uno o más registros LBPC 38 y si la dirección diana de ramificación se realizan hacia delante o hacia atrás respecto del PC de instrucción de ramificación, son propiedades de la instrucción de ramificación.
10 Aunque la presente invención se ha descrito en la presente memoria descriptiva respecto de características, aspecto y realizaciones particulares de la misma, es evidente que se pueden realizar numerosas variaciones, modificaciones y otras realizaciones dentro del amplio alcance de la presente invención, y en consecuencia, todas las variaciones, modificaciones y realizaciones se han de considerar que se encuentran dentro del alcance de
15 la invención. Las presentes realizaciones se han, por lo tanto, de interpretar en todos los aspectos como ilustrativos y no limitativos y todos los cambios que entran dentro del intervalo de significados y equivalencias de las reivindicaciones anexas se destinan a estar comprendidos en su interior.

Claims (11)

  1. Reivindicaciones
    1.-Procedimiento de predicción de ramificación, caracterizado porque comprende la supresión de una actualización de un Registro de Histórico de Ramificación (BHR) durante la ejecución de una instrucción de ramificación, en respuesta a la determinación de que la instrucción de ramificación es una instrucción de ramificación de fin de bucle.
  2. 2.-Procedimiento según la reivindicación 1, en el cual la etapa de determinación comprende asumir que una ramificación hacia atrás es una ramificación de fin de bucle.
  3. 3.-Procedimiento según la reivindicación 1, en el cual el PC de la instrucción de ramificación coincide con el contenido de un registro de PC de Última Ramificación (LBPC) que pone en memoria el PC de la última instrucción de instrucciones de ramificación para actualizar el BHR (30).
  4. 4.-Procedimiento según la reivindicación 3, en el cual el PC de la instrucción de ramificación coincide con el contenido de cualquiera de una pluralidad de registros LBPC (38) que pone en memoria los PC de la última pluralidad de instrucciones de ramificación para actualizar el BHR (30).
  5. 5.-Procedimiento según la reivindicación 1, en el cual la etapa de determinación comprende la determinación de que la instrucción de ramificación es una instrucción de ramificación única generada por una compilador para terminar ramificaciones o que la instrucción de ramificación incluye uno o más bits que indican que es una instrucción de ramificación de fin de bucle.
  6. 6.-Procedimiento según cualquier reivindicación que comprende, además, la determinación de una ramificación de fin de bucle.
  7. 7.-Procesador (10) que comprende:
    un predictor de ramificación (26) operativo para predecir la evaluación de instrucciones de ramificación coadicional;
    una línea de ensamble (12) de ejecución de instrucciones operativa para extraer y ejecutar de manera especulativa instrucciones basadas en una predicción procedente del predictor de ramificación; un Registro de Histórico de Ramificación (BHR) operativo para poner en memoria la evaluación de instrucciones de ramificación condicional; y caracterizado por:
    un circuito de control operativo para suprimir la puesta en memoriza de la evaluación de una instrucción de ramificación condicional en respuesta a la determinación de que la instrucción de ramificación es una instrucción de ramificación de fin de bucle.
  8. 8.-Procesador según la reivindicación 7 que comprende, además, un registro de Última Ramificación (LBPC) (38) operativo para poner en memoria el PC de una instrucción de ramificación que actualiza el BHR (30), y en el cual el circuito de control es operativo para suprimir la puesta en memoria de la evaluación de una instrucción de ramificación condicional si el PC de la instrucción de ramificación coincide con el contenido del registro LBPC (38).
  9. 9.-Procesador según la reivindicación 8, que comprende, además, una pluralidad de registros LBPC (38) operativos para poner en memoria los PC de una pluralidad de instrucciones de ramificación que actualizan el BHR (30), y en el cual el circuito de control es operativo para suprimir la puesta en memoria de la evaluación de una instrucción de ramificación condicional si el PC de la instrucción de ramificación coincide con el contenido de cualquier registro LBPC (38)
  10. 10.-Procesador según la reivindicación 7, en el cual el circuito de control es operativo para suprimir la puesta en memoria de la evaluación de una instrucción de ramificación condicional si la instrucción de ramificación comprende una indicación de que es una instrucción de fin de bucle u operativo para suprimir la puesta en memoria de la evaluación de una instrucción de ramificación condicional si la dirección diana de la instrucción de ramificación es inferior al PC de la instrucción de ramificación.
  11. 11.-El procesador según la reivindicación 10 en el cual la indicación de que la instrucción de ramificación es una instrucción de fin de bucle es el tipo de instrucción.
ES06735979T 2005-02-24 2006-02-24 Supresión de la actualización de un registro del histórico de ramificaciones por ramificaciones de fin de bucle. Expired - Lifetime ES2351163T3 (es)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US66508 2005-02-24
US11/066,508 US20060190710A1 (en) 2005-02-24 2005-02-24 Suppressing update of a branch history register by loop-ending branches

Publications (1)

Publication Number Publication Date
ES2351163T3 true ES2351163T3 (es) 2011-02-01

Family

ID=36577533

Family Applications (1)

Application Number Title Priority Date Filing Date
ES06735979T Expired - Lifetime ES2351163T3 (es) 2005-02-24 2006-02-24 Supresión de la actualización de un registro del histórico de ramificaciones por ramificaciones de fin de bucle.

Country Status (11)

Country Link
US (1) US20060190710A1 (es)
EP (2) EP2270651A1 (es)
JP (3) JP5198879B2 (es)
KR (1) KR100930199B1 (es)
CN (2) CN103488463B (es)
AT (1) ATE483198T1 (es)
DE (1) DE602006017174D1 (es)
ES (1) ES2351163T3 (es)
IL (1) IL185362A0 (es)
MX (1) MX2007010386A (es)
WO (1) WO2006091778A2 (es)

Families Citing this family (41)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8607209B2 (en) * 2004-02-04 2013-12-10 Bluerisc Inc. Energy-focused compiler-assisted branch prediction
JP4393317B2 (ja) * 2004-09-06 2010-01-06 富士通マイクロエレクトロニクス株式会社 メモリ制御回路
US20060190710A1 (en) * 2005-02-24 2006-08-24 Bohuslav Rychlik Suppressing update of a branch history register by loop-ending branches
US8904155B2 (en) * 2006-03-17 2014-12-02 Qualcomm Incorporated Representing loop branches in a branch history register with multiple bits
US7962724B1 (en) * 2007-09-28 2011-06-14 Oracle America, Inc. Branch loop performance enhancement
US7956552B2 (en) * 2008-03-18 2011-06-07 International Business Machiness Corporation Apparatus, system, and method for device group identification
US20090327674A1 (en) * 2008-06-27 2009-12-31 Qualcomm Incorporated Loop Control System and Method
JP5423156B2 (ja) * 2009-06-01 2014-02-19 富士通株式会社 情報処理装置及び分岐予測方法
US20110047357A1 (en) * 2009-08-19 2011-02-24 Qualcomm Incorporated Methods and Apparatus to Predict Non-Execution of Conditional Non-branching Instructions
CN101807145B (zh) * 2010-04-16 2012-12-26 浙江大学 栈式分支预测器的硬件实现方法
US8756591B2 (en) 2011-10-03 2014-06-17 International Business Machines Corporation Generating compiled code that indicates register liveness
US9354874B2 (en) 2011-10-03 2016-05-31 International Business Machines Corporation Scalable decode-time instruction sequence optimization of dependent instructions
US10078515B2 (en) 2011-10-03 2018-09-18 International Business Machines Corporation Tracking operand liveness information in a computer system and performing function based on the liveness information
US9329869B2 (en) 2011-10-03 2016-05-03 International Business Machines Corporation Prefix computer instruction for compatibily extending instruction functionality
US9286072B2 (en) 2011-10-03 2016-03-15 International Business Machines Corporation Using register last use infomation to perform decode-time computer instruction optimization
US8615745B2 (en) 2011-10-03 2013-12-24 International Business Machines Corporation Compiling code for an enhanced application binary interface (ABI) with decode time instruction optimization
US9697002B2 (en) 2011-10-03 2017-07-04 International Business Machines Corporation Computer instructions for activating and deactivating operands
US8612959B2 (en) 2011-10-03 2013-12-17 International Business Machines Corporation Linking code for an enhanced application binary interface (ABI) with decode time instruction optimization
US9690583B2 (en) 2011-10-03 2017-06-27 International Business Machines Corporation Exploiting an architected list-use operand indication in a computer system operand resource pool
US8959320B2 (en) 2011-12-07 2015-02-17 Apple Inc. Preventing update training of first predictor with mismatching second predictor for branch instructions with alternating pattern hysteresis
US9304776B2 (en) * 2012-01-31 2016-04-05 Oracle International Corporation System and method for mitigating the impact of branch misprediction when exiting spin loops
US9268569B2 (en) * 2012-02-24 2016-02-23 Apple Inc. Branch misprediction behavior suppression on zero predicate branch mispredict
US9858077B2 (en) * 2012-06-05 2018-01-02 Qualcomm Incorporated Issuing instructions to execution pipelines based on register-associated preferences, and related instruction processing circuits, processor systems, methods, and computer-readable media
US20140156978A1 (en) * 2012-11-30 2014-06-05 Muawya M. Al-Otoom Detecting and Filtering Biased Branches in Global Branch History
US10503538B2 (en) 2014-06-02 2019-12-10 International Business Machines Corporation Delaying branch prediction updates specified by a suspend branch prediction instruction until after a transaction is completed
US10289414B2 (en) 2014-06-02 2019-05-14 International Business Machines Corporation Suppressing branch prediction on a repeated execution of an aborted transaction
US10235172B2 (en) 2014-06-02 2019-03-19 International Business Machines Corporation Branch predictor performing distinct non-transaction branch prediction functions and transaction branch prediction functions
US10261826B2 (en) * 2014-06-02 2019-04-16 International Business Machines Corporation Suppressing branch prediction updates upon repeated execution of an aborted transaction until forward progress is made
US10635446B2 (en) * 2015-09-24 2020-04-28 Qualcomm Incorporated Reconfiguring execution pipelines of out-of-order (OOO) computer processors based on phase training and prediction
US9639370B1 (en) * 2015-12-15 2017-05-02 International Business Machines Corporation Software instructed dynamic branch history pattern adjustment
GB2548603B (en) * 2016-03-23 2018-09-26 Advanced Risc Mach Ltd Program loop control
US20180349144A1 (en) * 2017-06-06 2018-12-06 Intel Corporation Method and apparatus for branch prediction utilizing primary and secondary branch predictors
US10613867B1 (en) 2017-07-19 2020-04-07 Apple Inc. Suppressing pipeline redirection indications
CN111177663B (zh) * 2019-12-20 2023-03-14 青岛海尔科技有限公司 编译器的代码混淆改进方法及装置、存储介质、电子装置
US11941403B2 (en) * 2020-06-19 2024-03-26 Arm Limited Selective prediction based on correlation between a given instruction and a subset of a set of monitored instructions ordinarily used to generate predictions for that given instruction
US11113067B1 (en) * 2020-11-17 2021-09-07 Centaur Technology, Inc. Speculative branch pattern update
CN112988234A (zh) * 2021-02-06 2021-06-18 江南大学 一种面向不稳定控制流循环体的分支指令辅助预测器
US11868779B2 (en) * 2021-09-09 2024-01-09 International Business Machines Corporation Updating metadata prediction tables using a reprediction pipeline
CN114035848B (zh) * 2021-11-12 2025-05-27 深圳优矽科技有限公司 一种分支预测的方法、装置及处理器
US11928474B2 (en) * 2022-06-03 2024-03-12 Microsoft Technology Licensing, Llc Selectively updating branch predictors for loops executed from loop buffers in a processor
CN119938143B (zh) * 2025-04-03 2025-07-29 北京微核芯科技有限公司 数据预取方法、装置及处理器

Family Cites Families (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS635442A (ja) * 1986-06-26 1988-01-11 Matsushita Electric Ind Co Ltd プログラムル−プ検出記憶装置
JP2555664B2 (ja) * 1987-01-22 1996-11-20 日本電気株式会社 分岐ヒストリテーブル書込制御方式
US5175827A (en) * 1987-01-22 1992-12-29 Nec Corporation Branch history table write control system to prevent looping branch instructions from writing more than once into a branch history table
JPH0715662B2 (ja) * 1987-07-14 1995-02-22 日本電気株式会社 命令の先取りを行なう情報処理装置
JPH06243036A (ja) * 1993-02-12 1994-09-02 Hitachi Ltd キャッシュ制御システム
EP0623874A1 (en) * 1993-05-03 1994-11-09 International Business Machines Corporation Method for improving the performance of processors executing instructions in a loop
US5404473A (en) * 1994-03-01 1995-04-04 Intel Corporation Apparatus and method for handling string operations in a pipelined processor
JP3494484B2 (ja) * 1994-10-12 2004-02-09 株式会社ルネサステクノロジ 命令処理装置
US5752014A (en) * 1996-04-29 1998-05-12 International Business Machines Corporation Automatic selection of branch prediction methodology for subsequent branch instruction based on outcome of previous branch prediction
US5893142A (en) * 1996-11-14 1999-04-06 Motorola Inc. Data processing system having a cache and method therefor
US6253373B1 (en) * 1997-10-07 2001-06-26 Hewlett-Packard Company Tracking loop entry and exit points in a compiler
US6427206B1 (en) * 1999-05-03 2002-07-30 Intel Corporation Optimized branch predictions for strongly predicted compiler branches
JP2001166948A (ja) * 1999-12-07 2001-06-22 Nec Corp プログラム変換方法、プログラム変換装置及びプログラム変換プログラムを記憶した記憶媒体
US7017030B2 (en) * 2002-02-20 2006-03-21 Arm Limited Prediction of instructions in a data processing apparatus
JP3798998B2 (ja) * 2002-06-28 2006-07-19 富士通株式会社 分岐予測装置および分岐予測方法
JP4243463B2 (ja) * 2002-08-19 2009-03-25 株式会社半導体理工学研究センター 命令スケジューリングのシミュレーション方法とシミュレーションシステム
US7290089B2 (en) * 2002-10-15 2007-10-30 Stmicroelectronics, Inc. Executing cache instructions in an increased latency mode
JP3893463B2 (ja) * 2003-04-23 2007-03-14 国立大学法人九州工業大学 キャッシュメモリ、及びキャッシュメモリの電力削減方法
US20050102659A1 (en) * 2003-11-06 2005-05-12 Singh Ravi P. Methods and apparatus for setting up hardware loops in a deeply pipelined processor
US20060190710A1 (en) * 2005-02-24 2006-08-24 Bohuslav Rychlik Suppressing update of a branch history register by loop-ending branches

Also Published As

Publication number Publication date
EP1851620A2 (en) 2007-11-07
DE602006017174D1 (de) 2010-11-11
JP5198879B2 (ja) 2013-05-15
JP2015007995A (ja) 2015-01-15
EP1851620B1 (en) 2010-09-29
IL185362A0 (en) 2008-02-09
JP2008532142A (ja) 2008-08-14
US20060190710A1 (en) 2006-08-24
CN103488463B (zh) 2016-11-09
WO2006091778A3 (en) 2007-07-05
WO2006091778A2 (en) 2006-08-31
JP2011100466A (ja) 2011-05-19
EP2270651A1 (en) 2011-01-05
CN103488463A (zh) 2014-01-01
KR100930199B1 (ko) 2009-12-07
ATE483198T1 (de) 2010-10-15
CN101160561B (zh) 2013-10-16
CN101160561A (zh) 2008-04-09
KR20070105365A (ko) 2007-10-30
MX2007010386A (es) 2007-10-18

Similar Documents

Publication Publication Date Title
ES2351163T3 (es) Supresión de la actualización de un registro del histórico de ramificaciones por ramificaciones de fin de bucle.
ES2388309T3 (es) Representar saltos de bucle en un registro de historia de saltos con múltiples bits
US7814469B2 (en) Speculative multi-threading for instruction prefetch and/or trace pre-build
US8566569B2 (en) State machine-based filtering of pattern history tables based on distinguishable pattern detection
JP2011100466A5 (es)
US7962733B2 (en) Branch prediction mechanisms using multiple hash functions
JP2008532142A5 (es)
US20130152048A1 (en) Test method, processing device, test program generation method and test program generator
JP2009536770A (ja) ブロックに基づく分岐先アドレスキャッシュ
BRPI0614013A2 (pt) cache de endereços alvo de ramificação que armazena dois ou mais endereços alvo de ramificação por ìndice
JP7510253B2 (ja) 分岐予測器
US10007524B2 (en) Managing history information for branch prediction
US9311100B2 (en) Usefulness indication for indirect branch prediction training
CN116069602B (zh) 一种最坏情况执行时间分析方法和装置
HK1112984A (en) Suppressing update of a branch history register by loop-ending branches