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

INTRODUCCIÓN: PREDICCIÓN ESTÁTICA VS. DINÁMICA. CACHÉS DE PREDICCIÓN DINÁMICA DE SALTOS TIPOS DE MÁQUINAS PREDICTIVAS. 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). • 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 (doble número de tipos de saltos). ¾ 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 especial: BTB 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

2

2. CACHÉS DE PREDICCIÓN DE SALTOS • Por cada salto, se guarda su historia de una forma condensada en una máquina de estado predictiva. • Almacenar la historia completa de cada salto no es viable en hardware (muchos bits, mucho tacc, etc.). Tampoco almacenar todos los saltos. • Para un número fijo de saltos en implem. hardware simple que aprovecha ppio. de localidad temporal (el espacial, aquí no) ⇒ caché. • Por tanto se almacena: o Una máquina de M bits para cada salto (llamados de historia, aunque no guardan exactamente la historia): caché o Tabla de predicción de saltos (BPB, Branch Prediction Buffer). El estado de cada máquina lleva asociado una predicción (T/NT) o Las direcciones de destino, indexadas junto a lo anterior: Tabla de destino de saltos (BTB, Branch Target Buffer). Así se conoce cuanto antes la dirección de destino. • El conjunto anterior se suele llamar simplemente BTB (Branch Target Buffer) • Dicha caché es accedida por medio de la dirección de la instrucción. En la línea de datos del caché estará la información del salto (máq estados y dir destino). Se obtiene así una predicción para dicho salto. • Las líneas se asignan según los mapeados normales de cachés: mapeado directo, asociativo por conjuntos o completamente asociativo. Tam_línea = 1 salto • Luego estamos saltando a una instr predicha en IF (¡sin haber decodificado aún el salto!) 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

3

NOTA: Recordar (funcionamiento de un caché): la parte menos significativa de la dirección de la instrucción (salto) que está haciendo IF, sirve de índice para seleccionar una línea de la caché. La parte más significativa de la dirección, sirve para distinguir si la línea almacenada en la caché contiene la dirección buscada o no. Una coincidencia de los MSB implica acierto en el acceso a caché, Hit (si no, fallo Miss). PC (dirección de la instrucción 2 de salto) LSB (mod) MSB

Etiqueta de esta línea (MSB)

BPB

BTB

Predicción (máq. estados de un salto)

PC destino

Miss: La instrucción no es salto o es un salto pero no almacenado. Sólo se puede buscar la instrucción de la rama NT. Si tras la decodificación se descubre que es un salto, se ha de ocupar una línea (vacía o ocupada por otro salto) con la dir dest. y la máq inicializada.

NO

= SI Hit: La instrucción es un salto y se tiene una predicción. En el siguiente ciclo se busca (IF) la instrucción predicha. Si tras la ejecución del salto, se descubre que la predicción fue incorrecta, se ha de cambiar la máq de estados de la BPB. 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

4

3. TIPOS DE MÁQUINAS PREDICTIVAS (en la BPB). 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(salida de la máq) . Transición en azul NT T T NT NT A/T

T Máquina de 1 bit.

T T

NT NT

C/NT

D/NT

T

0 NT

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

B/NT

A/T

B/T

T:decrem

Valores peq./T

2n-1

Valoresgrand/NT gr/NT Valores

2n-1-1 NT:increm

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

5

T

NT A/T

B/T

T NT

T C/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 con n bits de predicción. Datos: PC de 32 bits, 512=29 líneas. (VER DIBUJO) 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 + dir destino: 21+n+32 Tamaño de caché: 512 líneas * (21+n+32) (faltaría bit Válido/Inv por cada línea) 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

6

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 BTB. ¿Cómo? Se guarda en un registro de desplazamiento, (llamado registro de correlación, no incluido en la BTB sino genérico de la máquina) el comportamiento de los últimos m saltos ejecutados del programa. P. ej, entra por la derecha 1 si el salto se tomó y 0 si no se tomó y se expulsa el bit de la izquierda. El valor de estos m bits debe influir en la predicción. En cada salto, hay una máquina de n bits de historia para cada valor del registro de correlación (en total 2m máq por salto). Sólo una de ellas va a usarse para predecir. La selección de la máquina viene dada por el valor del registro de correlación. • Se suelen denotar como BTB(m,n) m = número de bits de correlación. n = nº bits predicción o historia. • La BTB (0,1) se dejó pronto de usar porque su porcentaje de error es bastante mayor que la BTB(0,2). Esto se nota claramente en bucles anidados (la BTB(0,1) falla dos veces porcada iteración del bucle interno). • Las más usuales son las BTB(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.

7

Esquema con 1 bit de correlación 0 1

BTB(2,1): 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

Reg de Corr.

K

Línea 2 1 MUX

Último salto

T K

2 líneas

T

2=T,NT

T

T

A/T

A/T

A/T

A/T

T NT

T NT

T NT

T NT

B/NT

B/NT

B/NT

B/NT

Predicción

NT

...

NT

...

NT

...

NT

...

NOTA: el registro de desplazamiento puede estar cargado con el comportamiento de un mismo salto (ejecutado en dos ocasiones distintas) NOTA: Para una BTB (0,1) basta con sólo con almacenar las direcciones de destino de los saltos predichos T, y no almacenar nada si el salto es pred NT. Así son la mayoría de ejemplos del libro de Hennessy-Patterson 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

8

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

PC (dirección instrucción) LSB

2K líneas Etiquetas

PCdest

Predicciones (máq de n bits)

M0

M1

M2

V/I

M2m-1

Total de bits: 2k líneas × (bits etiq + n bits por máq × 2m columnas + bits PCdest + bit vál/inv)

2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

9

Ejerc: Para una BTB(2,2) inicializadas todas las máq al estado no polarizado T, y el reg. correlación inicializado a 01(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%). Media: 6.8% 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%). Media: 3.7% o SPEC89 FP: 3% (del 0.1 al 5%). o 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. 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

10

Pequeños cronogramas de salto con acceso a BTB. (Miss/Hit) // si salto predicho correctamente: (flecha azul: predicción BTB) BEQZ R2,etiq IF ID EX ME WB Instr predicha IF ID EX ME WB Instr post a predicha IF ID EX ME WB // si salto predicho incorrectamente: // flecha azul: predicción BTB; roja: rectificación BTB BEQZ R2,etiq IF ID EX ME WB Instr predicha IF ABORT Buscar instr rama contraria y quizás cambiar predicción de la BTB. @ // si salto no estaba cacheado (se busca la instr sig): 2 casos // flecha roja: rectificación BTB 1. Salto no se tomará BEQZ R2,etiq IF ID EX ME WB Instr siguiente IF ID EX ME WB Insertar en la BTB una nueva línea, inicializando el estado y predicción. 2. Salto se tomará BEQZ R2,etiq IF ID EX ME WB Instr siguiente IF ABORT Buscar instr rama contraria e insertar en la BTB una nueva línea, inicializando el estado y predicción. 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

11

4. IMPLEMENTACIÓN DE BTB EN DLX: Casos de acceso BTB almacena TODOS los saltos (Pred. T o Pred. NT) con máq estados compleja @Suponemos que en IF se accede a BTB (solo direcc predicha) y en ID a BPB 1. Falla acceso BTB en IF (Miss) En ID se descubre que: 1.a) No es salto . . . . . . . 1.b) Es salto: añadirlo a la maq de estados o 1.b1) NT. . . . . . . o 1.b2) T . . .. . . .

.0 c.b.q. .0 ó 1 c.b.q. .1 ó 2 c.b.q. acceso a BTB@

2. Acierto acceso BTB en IF (Hit): es salto seguro En ID se resuelve salto, se modifica su maq estado (en BPB) y se descubre que: 2.a) Acierta en la predicción . . . 2.b) Falla en la predicción o 2.b1) BTB no cambia su predicción o 2.b2) BTB cambia su predicción

.0 c.b.q. 1 c.bq. @ 1 ó 2 c.bq. acceso a BTB@

Si la BTB tiene dos puertos de acceso los c.bq. se reducen a dos casos : 0 ó 1 .El ciclo de bloqueo adicional es para puerto único: este será el “modelo de DLX” que usemos • En el peor de los casos hay 2 c.bq. en DLX, pero esto ocurre en un porcentaje reducido de ocasiones si la máq de predicción es suficientemente compleja. • Ejemplos: dibujar cronogramas de estos casos para DLX con máq compleja (más de 1 bit). NOTA: En práctica 4 hay diagrama flujo por cada fase en DLX con BTB que almacena todos los saltos.@ 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

12

5. 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): • BTB(2,2) DLX Prog INT: CPIcontrol = 0.2 * 0.06 * 1 = 0.012 c bq / instr • BTB(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 ó 2 ciclos, los procesadores reales (y actuales) 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: BTB(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.

13

6. 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). Como Bits de historia guardan información local de un salto, mientras que la correlación guarda la información global o de correlación del programa ⇒ se dispone de dos máquinas opuestas (en el caso extremo sería una BTB(0,n) y otra BTB(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 BTB(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 (Media 2.6%). Ej Alpha 21264: o Inform local en 1 K líneas tipo BTB(0,10), BTB cuyo valor sirve para indexar otra tabla de 1K contadores de saturación de 3 bits: 1K*10 bits+1K*3 bits o Inform global en una sola línea de BTB(12,2): 212=4096 *2 bits 2.9. Predicción de Saltos.

Arquitectura de Sistemas Paralelos 1.

14

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.

15