2.9. PREDICCIÓN DINÁMICA DE SALTOS ÍNDICE 1. 2. 3. 4. 5. 6. 7.

INTRODUCCIÓN: PREDICCIÓN ESTÁTICA VS. DINÁMICA. CACHÉS DE PREDICCIÓN DINÁMICA DE SALTOS: BPB TIPOS DE MÁQUINAS PREDICTIVAS. BTB: BRANCH TARGET BUFFER. IMPLEMENTACIÓN DE BTB EN DLX. PRESTACIONES: CPICONTROL. OTRAS MEJORAS EN LA PREDICCIÓN DE SALTOS.

2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

1

1. PREDICCIÓN ESTÁTICA VS. DINÁMICA

• Predicción Estática. ! Predicción global: Caso Tomado es el más común. Pero saltos muy polarizados: ! Predicción estática del compilador con ejecuciones previas: Efectividad entre el 75 y 94%. Pero esto se puede hacer también dinámicamente (en tiempo de ejec.): • Predicción Dinámica: o Guardar la información de cada salto en la CPU. o Generalmente la historia de un salto (lo que hizo las últimas veces) asegura una efectividad en la predicción muy alta (en general, más del 90%). o A cada salto se le asocia una máquina de estado predictiva (hay varios tipos). o Se implementa en un caché especial: BPB o BTB. • Implementación en Proc. encadenados ! El encadenamiento normal se comportaría como un sistema de predicción dinámica, el cual siempre predice NO TOMADO. ! Implementar predicho TOMADO ⇒ Calcular cuanto antes la dirección destino. ! Implementación mixta: en opcode de la instrucción se especifica predicho T/NT. ! Saltos retardados: evitar ciclos de bloqueo inherentes a la resolución de un salto (código más complejo y complicaciones en la implementación). ! Implementación basada en caché predictivo: BPB, BTB 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

2

2. CACHÉS DE PREDICCIÓN DE SALTOS BPB: Branch Prediction Buffer (Tabla de predicción de saltos)

• Por cada salto, se guarda su historia de una forma condensada en una máquina de estado predictiva. Se implementa en un caché especial. • Almacenar la historia completa de cada salto no es viable en hardware (muchos bits, mucho tacc, etc.). Tampoco almacenar todos los saltos. • Por tanto: una máquina de M bits para cada salto (llamados de historia, aunque no guardan exactamente la historia). Y para un número fijo de saltos en la implem. hardware más simple y efectiva que aprovecha ppio. de localidad temporal (el espacial, aquí no): caché. • Dicha caché es accedida por medio de la dirección de la instrucción. En la línea de caché estará la información del salto (máq estados). Se obtiene así una predicción para dicho salto. Las líneas de la BPB se asignan según los mapeados normales de cachés: mapeado directo, asociativo por conjuntos o completamente asociativo. Recordar (funcionamiento de un caché): la parte PC (dirección de la instrucción de salto) 2 menos significativa de la dirección de la MSB (buscado) LSB (mod) instrucción (salto) que está haciendo IF, sirve de índice para seleccionar una línea de la caché. La BPB parte más significativa de la dirección, sirve para Predicción distinguir si la línea almacenada en la caché (máq. estados de Etiqueta(MSB) LSB (mod) contiene la dirección buscada o no. Una un salto) coincidencia de los MSB implica acierto en el acceso a caché, Hit (si no, fallo Miss). 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

3

3. TIPOS DE MÁQUINAS PREDICTIVAS. Máquinas de predicción de n bits (de historia). Son máquinas de estados que memorizan de alguna forma la historia de los últimos comportamientos de un salto concreto (en forma de cambios de estado) y generan una salida (la predicción) según esa historia. Pueden ser de un único bit (evidentemente sólo almacenaría el último comportamiento, que daría la predicción), o de varios, en cuyo caso la predicción ha de elegirse en función de programas reales para que el %acierto sea máximo.

Implementación: Estado/Predicción . Transición en azul T T NT A/T

NT D/NT

T

B/NT

T Máquina de 1 bit.

NT

C/NT

NT

A/T

B/T

T T

NT

0 NT

T:increm

2n-1

Valoresgrand/NT gr/NT Valores

Valores peq./T n-1

2 -1 NT:decrem

Máquina de 2 bits (A, D estados polarizados). 2.9. Predicción de Saltos.

Sol. genérica: Contador n bits con saturación Arquitectura de Sistemas Paralelos 1.

4

T

NT A/T

B/T

T T C/NT

NT NT T

D/NT

NT

Variante de máquina de 2 bits (al segundo error de predicción, se salta al estado de predicción contraria, pero menos polarizado). En rojo las nuevas transiciones. Ej: Evolución del salto de un bucle. Evolución de los saltos de dos bucles anidados. Ej: Número de bits que ocupa una caché BTB. Datos: PC de 32 bits, 512=29 líneas, n bits de predicción. Tamaño de campo LSB: 9. Tamaño de etiqueta (MSB): 32-9-2=21 (2 por que PC se incrementa de 4 en 4 siempre; la dirección de un salto es múltiplo de 4) Tamaño de línea: etiq + bits historia: 21+n Tamaño de caché: 512 líneas * (21+n) (faltaría un bit por línea de Válido/Inv) 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

5

Predicción usando Bits de correlación. Correlación estadística: una variable aleatoria depende de otra. Correlación de saltos: el comportamiento de un salto depende del de otros (los últimos generalmente): típico en variables tipo “flag” y en cond de salida de bucles. Por tanto, también se suele almacenar esta dependencia en una BPB. ¿Cómo? Se guarda en un registro de desplazamiento, (llamado registro de correlación, no incluido en la BPB sino genérico de la máquina) el comportamiento de los últimos m saltos ejecutados. P. ej, entra por la izquierda 1 si el salto se tomó y 0 si no se tomó y se expulsa el bit de la derecha. El valor de estos m bits debe influir en la predicción. Por cada salto, se tiene una máquina de n bits de historia para cada valor del registro de correlación (en total 2m máq). Sólo una de ellas va a usarse para la predicción. La selección de la máquina viene dada por el valor del registro de desplazamiento. • Se suelen denotar como BPB(m,n), m = número de bits de correlación. n = nº bits predicción o historia. • La BPB (0,1) se dejó pronto de usar porque su porcentaje de error es bastante mayor que la BPB(0,2). Esto se nota claramente en bucles anidados (la BPB(0,1) falla dos veces porcada iteración del bucle interno). • Las más usuales son las BPB(0,2), (2,2) y hoy ya las (2,3) y algunas otras variantes (se ven al final de este apartado). 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

6

Esquema con 1 bit de correlación 0 1

Con 2 bits correlación, 1 bit historia. Reg de Penúlt. Último salto salto Corr.

Línea 0 Línea 1

0 si NT 1 si T

0=NT,NT

3=T,T

1=NT,T

Línea 2m-1

T

Reg de Corr. MUX

T A/T

Último salto

T

T

B/NT

Predicción

T A/T

NT

2=T,NT

A/T

NT

B/NT

NT

T

T

A/T

NT

B/NT

NT

T

NT

B/NT

NT

NT

Replicado 2m veces

NOTA: el registro de desplazamiento puede estar cargado con el comportamiento de un mismo salto (ejecutado en dos ocasiones distintas)

2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

7

Esquema de BPB(m, n) Reg. Corr. (m bits)

PC (dirección instrucción) LSB

BPB k

2 líneas

Etiquetas

Predicciones (máq de n bits)

M0

M1

M2

M2m-1

Total de bits : 2k líneas * n bits por máq * 2m columnas + 2k * bits etiquetas

2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

8

Ejerc: Para una BTB(2,2) inicializadas todas las máq al estado polarizado NT, y el reg. correlación inicializado a 00(2, observar la evolución de @: o Un bucle. o Dos bucles anidados. o Un bucle con una sentencias if {…} dentro. o Un bucle con 2 sentencias if {…} dentro sin correlación entre ellos. o Un bucle con 2 sentencias if {…} dentro con correlación entre ellos, etc. Porcentaje medio de Fallos de predicción • Se suele dar porcentaje fallos porque veremos que CPIcontrol es proporcional al mismo • BTB(0,2) con 4096 líneas: o SPEC89 INT: 11% (del 5 al 18%) o SPEC89 FP: 4% (del 0.1 al 9%) o IMPORTANTE: El número de fallos prácticamente no decrece con más líneas: gran localidad de los saltos. • BTB(2,2) con 1024 líneas: o SPEC89 INT: 6% (del 4 al 11%). Se reduce más en INT porque son más algorítmicos y menos vectoriales. Es evidente que hay correlación entre los saltos de tales programas. o SPEC89 FP: 3% (del 0.1 al 5%) 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

9

4. BTB: Branch Target Buffer.

• Las BPB en realidad no se implementan nunca sola, porque si la predicción de un salto es T, entonces hasta que no se calcule la dirección de destino del salto (en el DLX, en el ciclo siguiente, fase ID) no se puede hacer fetch de la instrucción destino (predicha). • La BTB es una caché de direcciones destino, indexada igual que la BPB. • La BTB sólo necesita tener indexados los saltos con predicción de T (los NT se comportan como NOP). La única información guardada son las direcciones de destino de saltos pred. T. • Luego estamos saltando a una instr predicha en IF (¡sin haber decodificado aún el salto!) Miss: La instrucción no tiene predicción de tomado. Tanto si se no es salto como si es un salto que no se toma, se opera de la misma forma (predice NT). Si tras la ejecución la máq de estados de la BPB, decide que la nueva pred es T, (error pred.), se añade una línea a la BTB con la dir dest.

PC (dirección instrucción)

BTB Etiquetas

PC destino

NO SI =

2.9. Predicción de Saltos.

Hit: La instrucción es un salto y con predicción de T. En el siguiente ciclo se hace IF de la instrucción destino. Si tras la ejecución, la máq de estados de la BPB, decide que la nueva pred es NT, (error pred.), se invalida esta línea de la BTB.

Arquitectura de Sistemas Paralelos 1.

10

• Los cambios de predicción de la BPB deben afectar a la BTB. Pero si un cambio de estado en la máquina de la BPB, no modifica la predicción, la BTB seguiría igual. • La BTB se puede fusionar con la BPB, implica tener en cada línea o entrada, la información del estado de las máquinas (con la correlación, etc.) y el destino del salto. En este caso, el PCdestino sólo se empleará cuando la predicción de la máquina sea T. En este caso la estructura de una BTB fusionada con una BPB(m,n), de k líneas será: BTB

1 2

Etiqueta del salto

. . .

Dirección Destino

. . .

BPB

Bit Válido

. . .

Estado maq. 0 . .. Estado maq. 2m-1

. . .

. . .

. . .

k

• NOTA: Una BPB (0,1) no hace falta implementarla si existe una BTB: basta con sólo una BTB que almacenara las direcciones de destino de los saltos predichos T, y no almacenara nada si el salto es pred NT (un bit de predicción no da para más). 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

11

5. IMPLEMENTACIÓN DE BTB EN DLX: Casos de acceso Todas las instrucciones acceden en su fase IF a la caché BTB. 1. Si el acceso a BTB falla (Miss), sólo queda buscar la instrucción siguiente (PC+4), es decir, se predice NT. En la fase ID puede ocurrir: o La instrucción no es un salto (tales instrucciones nunca estarán en caché). o Es un salto pero no está almacenada su información en la línea de la caché BTB. La pred. era NT, o bien es un fallo de caché: porque tal línea estaba vacía (forzoso) o porque estaría otro salto (conflicto, dos saltos pueden tener la misma parte baja de la dirección, pugnando por la misma línea de caché). Además, en el DLX, se resuelve el salto: a) Si es NT, no se accede ni se almacena nada en la BTB (los saltos NT se comportan idem que NOP). b) Si es T. Si la BPB indica que la predicción cambia a T, hay que añadir la línea a la BTB. Como se predijo NT ==> fallo de predicción. Si la pred sigue siendo NT, la BPB cambia a otro estado con la misma predicción y no se toca la BTB. Dos posibilidades en la BPB: • Si el salto estaba registrado ya, se modifica el estado de la máq. de tal salto • Si no, se añade una línea a la BPB, inicializando la máquina (lo que supone echar la información de un salto anterior). 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

12

2. Si el acceso a BTB acierta (Hit), se buscaría la instrucción de destino. Tal salto debe estar registrado en la BPB, luego hay que actualizar su máquina de estados. En la fase ID, puede ocurrir: o Acierta en la predicción: 0 c.bq. y se siguen buscando instrucciones (fase IF). o Falla en la predicción: Habrá que abortar las instrucciones predichas y buscar la otra rama NT. Dos posibilidades en la BPB: a) La BPB indica que la pred. ha cambiado: hay que invalidar de la BTB tal línea. b) La BPB podría cambiar a otro estado pero con la misma predicción. NOTA: Si hay que modificar la BTB, entonces seguro que fue una predicción incorrecta, (o no la hubo). Como hay que buscar una instrucción de la rama contraria a la predicha, y en el mismo ciclo modificar la BTB, se necesitarían dos puertos de acceso a la caché BTB. Si la BTB sólo tiene un puerto, se usará para modificar la BTB, y la fase IF de la instrucción de la rama contraria ha de bloquearse. • En el peor de los casos se pueden perder 2 ciclos de bloqueo en el DLX, pero esta situación ocurre en un porcentaje reducido de ocasiones, si la máq de predicción es suficientemente compleja. • Ejemplos: dibujar los cronogramas de estos casos para un DLX, suponiendo que se accede a la BPB en ID y que ésta tiene una máq compleja (más de 1 bit). 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

13

Esquema para acceso a BTB y BPB en un DLX. Enviar PC a IF y BTB

IF NO

NO

¿Fue salto T?

¿Acierto BTB?

SI

Enviar PCdest para IF

SI

ID NO

¿Acertó?

SI

Ejecución normal

Actualizar BPB (Si la Pred. cambia a T, añadir salto a BTB) 1 o 2 ciclos de bloqueo

2.9. Predicción de Saltos.

Mala predicción Actualizar BPB (Si Pred. NT, borrar salto de BTB) 1 o 2 ciclos de bloqueo

Predicción correcta. Actualizar 0 ciclos de bloqueo

EXE

Arquitectura de Sistemas Paralelos 1.

14

6. PRESTACIONES: CPICONTROL. CPIcontrol = Fsaltos* Psaltos = Fsaltos* (%Fallos_pred * Pfallo + %Aciertos_pred * Pacierto) ⇒ (típicamente) CPIcontrol = Fsaltos * %Fallos_pred * Pfallo ⇒ CPIcontrol es proporcional a %Fallos_pred y a Pfallo Para el DLX (con una BTB de varios puertos de acceso) la Pfallo es 1 c bq (muy baja): • BPB(2,2) DLX Prog INT: CPIcontrol = 0.2 * 0.06 * 1 = 0.012 c bq / instr • BPB(2,2) DLX Prog FP: CPIcontrol = 0.1 * 0.03 * 1 = 0.003 c bq / instr Para el DLX con una BTB de un único puerto de acceso, habría que distinguir entre penalidades de 1 o 2 c bq: Psaltos = Pfallo = %Fallos_pred * ( 2 * %Cambio_pred + 1 * %No_cambio_pred ) • Notar que tan importante es reducir el %Fallos_pred como la Pfallo . Aunque en el DLX la Pfallo sea sólo de 1 o 2 ciclos, en los procesadores reales, tienen de 11 a 22 fases (supersegmentados) y su Pfallo está entre 4 y 8 ciclos (y eso que usan técnicas de reducción de la misma). • P ej: BPB(2,2) Proc real Prog INT: CPIcontrol = 0.16 * 0.06 * 7 = 0.0448 c bq / instr 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

15

7. OTRAS MEJORAS EN LA PREDICCIÓN DE SALTOS.

• BTB con Plegado (Folding): consiste en almacenar en la BTB, además del PCdest, el código de la instrucción destino para, tras predecir T, lanzar directamente la etapa ID de la instrucción destino (que debería ejecutarse en paralelo con la ID del salto). • Buffer de instrucciones no predichas. Se guarda en un buffer especial de la CPU, las primeras instrucciones de la rama no predicha, de forma que si la predicción falla, la penalidad es mucho menor (empezaría a ejecutar las fases ID de la otra rama, ahorrando la fase IF). Ej: UltraSPARC III guarda instrucciones de la rama NT, para un salto predicho T (puesto que suele estar en la misma línea de caché que el salto) • Predictor por concurso (tournament predictor). Los bits de historia guardan la información local de un salto, mientras que la correlación guarda la información global o de correlación del programa. Por tanto, se dispone de dos máquinas opuestas (en el caso extremo sería una BPB(0,n) y otra BPB(m,0)) y en cualquier predicción podríamos optar por elegir una u otra (ambas “concursan” por la pred.). La decisión se toma con otra máquina de estados por cada salto, que suele ser similar a las BPB(0,2) (pero donde la máq se polariza hacia uno u otro predictor en vez de T/NT). El %error_pred es algo menor que en otras máquinas (2.5%). Ej Alpha 21264: o Inform local en 1 K líneas tipo BPB(0,10), BPB cuyo valor sirve para indexar otra tabla de 1K contadores de saturación de 3 bits: 1K*10 bits+1K*3 bits 12 o Inform global en una sola línea de BPB(12,2): 2 =4096 *2 bits 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

16

o Selector de 4K contadores de 2 bits (indexados tb por la propia dir del salto): 4K*2 bits...¡total 29Kbits! Máq con inform. Local Ej. BPB(0,n) Pred. Máq con inform. Global. Ej. BPB(m,0)

Máq de selección entre información global o local

• Caché de direcciones de retorno (return address prediction): se guarda en un buffer tipo pila, las últimas direcciones de retorno, así no hay que obtenerlas en ID (normalmente de un registro, JR R31), sino que su fase IF las irá sacando de la pequeña pila (la BTB redirecciona a tal pila). Con una pila de 6 direcciones de retorno almacenadas se acierta en el 81% de return. Útil en C++, Java, recursividad. • Caché de trazas (trace cache). Es una caché de instrucciones, que en lugar de mapear las instrucciones como es normal en los cachés, guarda la traza de ejecución (con instrucciones decodificadas si es posible), incluso con lo hecho por los saltos T. Mapeo muy complejo. Gran ventaja si decodificación es compleja y las instrucciones de pequeño tamaño como en CISC (evita desperdicio de caché). Ej Pentium 4 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

17