Riesgos de control y predicción de saltos (página 3)

Partes: 1, 2, 3, 4

En el esquema de 2-bit la predicción sólo se cambia sí hay dos errores de predicción:

Red: stop, not taken
Black: go, taken
Añade histéresis al proceso de toma de decisión
Propuesto por J. Smith en 1981
NT
(Gp:) T
(Gp:) T
(Gp:) Predict Taken
(Gp:) Predict Not
Taken
(Gp:) Predict Taken
(Gp:) Predict Not
Taken
(Gp:) T
(Gp:) NT
(Gp:) T
(Gp:) NT
(Gp:) NT

PREDICTOR DE SMITH: BUFFER DE PREDICCIÓN DE SALTOS (BPB) DE 2-BIT
31

Utiliza un array de contadores de 2-bits con saturación
La predicción es el bit más significativo (MSb) del contador
El contador se actualiza con la salida del salto
S – Strong
W – Weak
NT – Not taken
T – Taken
PREDICTOR DE SMITH: BUFFER DE PREDICCIÓN DE SALTOS (BPB) DE 2-BIT
32

Estado inicial: weakly taken (la mayoría de los saltos se efectúan).
Predice bien series monotónicas: sólo un error por iteración del ciclo
No predice bien saltos con patrones 010101….01
Saltos con patrones complejos requieren predictores más sofisticados
0 1 2 3
PREDICTOR DE SMITH: BUFFER DE PREDICCIÓN DE SALTOS (BPB) DE 2-BIT
33

PREDICTOR DE 2-BIT (BIMODAL)
En rojo, las pred. erróneas
Obsérvese el alto número de predicciones erróneas en las dos primeras secuencias.
34

PREDICCIÓN DINÁMICA: TABLAS DE PREDICCIÓN DE 2 NIVELES
Este predictor utiliza dos niveles independientes de información sobre el historial de los saltos para realizar la predicción.
Puede utilizar historia global o local lo que da lugar a algoritmos diferentes
También llamados correlados
35

Esquema básico
BHR: Branch History Register
PHT: Pattern History Table
(Gp:) Historia del salto
(Gp:) 2(n+m) contadores de 2 bits
(Gp:) .
.
.
(Gp:) Predicción de salto
(Gp:) 011001
(Gp:) BHR
(Gp:) PHT
(Gp:) 1 0

PROBLEMA: alto número de interferencias destructivas entre saltos
PREDICTOR DE 2 NIVELES DE HISTORIA GLOBAL: 1º IDEA
36

La conducta de algunos saltos esta muy correlada con la conducta de otros saltos:
if (x < 1)….
if (x > 1) …
Utilizando un Global History Register (GHR), la predicción del segundo if puede basarse en la dirección del primer if
GHR no es por salto específico, sino para el programa entero
Para otros saltos la interferencia entre historias puede ser destructiva
La interferencia entre historias puede reducirse significativamente utilizando los esquemas g-select o g-share
PREDICTOR DE 2 NIVELES DE HISTORIA GLOBAL
37

PREDICCIÓN DINÁMICA: PREDICTOR DE HISTORIA GLOBAL (G-SELECT)
El esquema anterior produce muchas interferencias destructivas por lo que se usa un esquema modificado denominado g-select
Este predictor funciona de la siguiente forma:
Primer nivel:
Los resultados de salto más recientes se almacenan en un registro de desplazamiento, que se desplaza cuando entra un nuevo salto, saliendo el más antiguo (se usan: 0 y 1, para indicar salto no tomado y tomado).
Se denomina registro de historial de salto (BHR, branch history register)
Segundo nivel:
Este nivel es una tabla con contadores de saturación de 2 bits.
Se denomina tabla de historial de patrones (PHT, pattern history table).
La tabla se indexa con un algoritmo hash, con concatenación de la dirección del salto con el contenido del BHR.
El contador indexado en la tabla PHT proporciona la predicción de forma similar a como se hace en el predictor Smith de 2 bit o bimodal.
38

PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES DE HISTORIA GLOBAL
Esquema g-select
(Gp:) Dirección del salto
(Gp:) 2(n+m) contadores de 2 bits
(Gp:) .
.
.
(Gp:) Predicción de salto
(Gp:) PC
(Gp:) 011010010101
(Gp:) 0110
(Gp:) BHR
(Gp:) 0111 01
(Gp:) PHT
(Gp:) 1 0
(Gp:) n
(Gp:) m

39

PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES DE HISTORIA GLOBAL
Con m bits de historia global y n bits de la dirección de salto la PHT requiere 2n+m entradas.
Hay que equilibrar ambos, ya que si se usan más bits de dirección disminuyen los conflictos de saltos,
Si se usa una historia más larga (más bit en el BHR) se permite que se correlacione con patrones más complejos
Esta técnica explota la idea de que el resultado de un salto puede estar correlacionado con un salto anterior
40

PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES DE HISTORIA LOCAL
En este esquema se pasa de tener un único BHR global a tener un BHR por salto.
La recopilación de BHR se denomina tabla de historial de saltos (BHT, branch history table).
Se puede considerar que el esquema con un único BHR global es una simplificación de este.
41

Esquema
(Gp:) Dirección del
salto
(Gp:) PC
(Gp:) 01101001 0101
(Gp:) BHT
(Gp:) 2(m) contadores de 2 bits
(Gp:) .
.
.
(Gp:) 0 Predicción de salto
(Gp:) PHT
(Gp:) 0 1
(Gp:) 1110

PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES DE HISTORIA LOCAL: 1º IDEA
42

PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES DE HISTORIA LOCAL
La historia de cada salto se salva en un Branch History Register (BHR):
BHR: es un registro de desplazamiento actualizado con la salida del salto
El BHR indexa un array de contadores saturados de 2-bits (bimodal)
Cada contador predice el salto para una historia dada
Puede predecir bien patrones complejos
El array de contadores puede ser
Privado: por BHR
Por-conjunto: compartido por todas las BHRs en el mismo conjunto
Global: compartido por todos los BHRs
BHRs demasiado largos no son buenos
La historia pasada puede no ser ya relevante
43

Esquema
(Gp:) Dirección del
salto
(Gp:) PC
(Gp:) 01101001 0101
(Gp:) BHT
(Gp:) 0101 110
(Gp:) 2(n+m) contadores de 2 bits
(Gp:) .
.
.
(Gp:) 0 Predicción de salto
(Gp:) PHT
(Gp:) 0 1
(Gp:) 110

PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES DE HISTORIA LOCAL: L-SELECT
44

Funcionamiento:
La dirección de salto se usa para seleccionar una de las entradas de la BHT que proporcional la historia local.
El contenido del BHR seleccionado en la BHT se combina con el PC en la misma forma que en el predictor de historia global para indexar la tabla PHT.
En la tabla PHT están los contadores de saturación de 2 bits.
Para actualizar el historial, se desplaza el resultado del registro del salto y se introduce el más reciente en la entrada BHR del BHT y se actualiza también en la PHT como en el predictor Smith de 2 bit.
La asignación de tamaños en este predictor es más compleja que en el predictor de 2 niveles de historia global.
Ejemplo: el Intel P6 (i686/pentium pro) utiliza un predictor de 2 niveles de historia local con longitud de historia de 4 bits.
PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES DE HISTORIA LOCAL: L-SELECT
45

PREDICCIÓN DINÁMICA: PREDICTOR DE HISTORIA LOCAL : EJEMPLO
El salto del bucle interno en:
For (j=0; j<1000;j++)
for (i=0; i<4; i++)
Puede generar la secuencia: 000100010001…..
Suponiendo una historia de longitud 6, en régimen permanente, se repetirán los siguientes patrones

Los contadores apuntados por 000100, 010001, 100010 irán a NT (not taken)
El contador apuntado por 001000 irá a T (taken)
46

PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES DE HISTORIA LOCAL
Otra visión del predictor local
(Gp:) Dirección del
salto
(Gp:) contadores de 2 bits
(Gp:) .
.
.
(Gp:) 1 Predicción
de salto
(Gp:) PC
(Gp:) 011010010101
(Gp:) 0110
(Gp:) BHR
(Gp:) PHTs
(Gp:) n
(Gp:) 0 0
(Gp:) 1 1
(Gp:) 1 0
(Gp:) 0 1
(Gp:) 1 0

47

PREDICCIÓN DINÁMICA: PREDICTOR DE 2 NIVELES POR CONJUNTOS
Esta variante usa una BHT que usa una función de hash arbitraria para dividir los saltos en conjuntos distintos.
Cada conjunto comparte un único BHR.
En lugar de usar los bits menos significativos de la dirección para seleccionar el BHR de la BHT utilizan los más significativos.
A este tipo de historial se le denomina historial de salto por conjunto y la tabla se denomina tabla de historial de salto por conjuntos (SBHT, set branch history table).
Se pueden obtener diversas combinaciones.
48

PREDICCIÓN DINÁMICA: PREDICTOR DE ÍNDICE COMPARTIDO
En general los predictores de 2 niveles son difíciles de equilibrar, en lo que se refiere al número de bits a utilizar en el BHR y el número de bits que se usan para indexar la PHT.
Para un tamaño fijo de PHT, el uso de más bits de historial permite establecer correlaciones con saltos más lejanos pero con el coste de usar menos bits de la dirección de salto y aumentar los conflictos.
Para evitar algunos de estos problemas Mc Farling propuso en 1993 una variación del predictor de 2 niveles de historia local que se denominó predictor Gshare.
49

Esta solución intenta utilizar mejor los bits de índice aplicando la función Hash al BHR y al PC conjuntamente para seleccionar la entrada en la PHT.
La función hash que se utiliza es un XOR a nivel de bit (a esto se le denomina compartición del índice).
El hardware del predictor g-share es muy parecido al predictor de 2 niveles excepto en la generación del índice de la PHT.
(Gp:) Dirección del
salto
(Gp:) 2(m) contadores de
2 bits
(Gp:) .
.
.
(Gp:) Predicción de salto
(Gp:) PC
(Gp:) 011010010101
(Gp:) 100110
(Gp:) BHR
(Gp:) PHT
(Gp:) 1 0
(Gp:) m
(Gp:) m
(Gp:) XOR

PREDICCIÓN DINÁMICA: PREDICTOR GLOBAL G-SHARE
50

PREDICCIÓN DINÁMICA: PREDICTOR P-SHARE (DE ÍNDICE COMPARTIDO)
Evers (1996) propuso una variación del predictor G-share que utiliza una tabla de historial de salto por dirección para almacenar el historial local del salto.
El P-share es análogo al G-share pero con la historia local del salto.
Se usan los bits de orden inferior de la dirección de salto para indexar en la BHT de primer nivel.
A continuación se hace un XOR entre el contenido del BHR indexado y la dirección de salto para formar el índice de la PHT.
(Gp:) Dirección del salto
(Gp:) 2(m) contadores de
2 bits
(Gp:) .
.
.
(Gp:) Predicción de salto
(Gp:) PC
(Gp:) 011010010101
(Gp:) PHT
(Gp:) 1 0
(Gp:) m
(Gp:) m
(Gp:) XOR
(Gp:) BHT

51

Se utilizan habitualmente en los micros actuales.
El IBM Power 4 utiliza una historia global (BHR) de 11 bits y una PHT de 16.384 entradas
El Alpha 21264 usa un predictor de historia global con un historial global de 12 bits y una PHT de 4096 entradas.
PREDICCIÓN DINÁMICA: PREDICTORES DE ÍNDICE COMPARTIDO: EJEMPLOS
52

La PHT que se utiliza en los predictores de dos niveles es una estructura sin etiquetas asignada de forma directa.
El alias se produce entre dos parejas diferentes dirección/salto de la PHT.
La PHT puede ser considerada como una memoria de tipo caché en la que se pueden producir fallos.
Estos fallos en la PHT se pueden producir por diversas razones:
Por alias obligatorio la 1ª vez que se utiliza la pareja dirección/salto para indexar la PHT.
La capacidad de alias aparece debido a que el conjunto de trabajo actual de parejas direcc/salto es mayor que la capacidad de la PHT.
Los conflictos de alias aparecen cuando dos parejas distintas direcc/salto asignan la misma entrada a la PHT.
En general, la solución estándar en las caches es aumentar la asociatividad de la caché, pero los predictores son diferentes.
PREDICCIÓN DINÁMICA: PREDICTORES DE REDUCCIÓN DE INTERFERENCIAS
53

Utiliza múltiples PHTs para reducir los efectos de alias (1997), utiliza dos PHTs indexadas con un esquema g-share.
Ambas utilizan el mismo índice.
El predictor de selección se indexa con los bits inferiores de la dirección de salto y es un predictor de Smith de 2 bits, en el que el bit más significativo indica que PHT hay que usar para la predicción.
Se basa en que la mayoría de los saltos se desplaza (en %) hacia ser tomado o no tomado.
El predictor recuerda esto, de forma los que se inclinan a ser tomados se almacenan en una PHT y los que se inclinan a no ser tomados en la otra.
Esto reduce las interferencias destructivas entre ambas PHTs.
Una vez conocido el resultado del salto, se actualiza la PHT que ha marcado el predictor de selección.
PREDICTORES DE REDUCCIÓN DE INTERFERENCIAS:PREDICTOR BI-MODE
54

Esquema
Dirección del
salto
.
.
.
Predicción de salto
PC
011010010101
100110
BHR
PHT0
1 0
m
m
(Gp:) XOR

PHT1
0 0
(Gp:) XOR

.
.
.
1 0
Predictor de
selección
PREDICTORES DE REDUCCIÓN DE INTERFERENCIAS:PREDICTOR BI-MODE
55

PREDICTORES TOURNAMENT
El motivo para correlar los predictores de salto es que los predictores de 2-bit fallan en saltos importantes; al añadir información global, se mejoran las prestaciones
Los Tournament predictors: utilizan 2 predictores, 1 basado en información global y 1 basado en información local, y los combina con un selector
La esperanza es seleccionar el predictor correcto para el salto correcto
56

El selector decide para cada salto que predictor es el mejor
Cada salto es predicho por dos predictores: P1 y P2
El puntero a la instrucción de salto también indexa un contador de saturación de 2-bits en el array del selector
Si P1 es correcto y P2 erróneo el contador se incrementa
Si P2 es correcto y P1 erróneo el contador se decrementa
En otro caso, el contador no se modifica
El valor del selector será utilizado para predecir la próxima vez que se encuentre este salto
Si 11 o 10 => se elige P1
Si 00 o 01 => se elige P2
SELECTOR
57

SELECTOR (CONTINUACIÓN)
El selector puede también ser indexado por el GHR
58

TOURNAMENT PREDICTOR EN EL ALPHA 21264
4K de contadores de 2-bit para elegir entre un predictor local y un predictor global
Predictor Global, tiene también 4K entradas y esta indexado por la historia de los últimos 12 saltos; cada entrada del predictor global es un predictor standard de 2-bit
Patrón de 12-bit:
i-ésimo bit 0 => i-ésimo salto previo no efectuado;
i-ésimo bit 1 => i-ésimo salto previo efectuado;
59

TOURNAMENT PREDICTOR EN EL ALPHA 21264

Predictor Local, consiste de un predictor de 2-niveles:
Top level es una tabla de historia local que consta de 1024 entradas de 10-bit; cada entrada de 10-bit corresponde a los resultados de los 10 saltos más recientes. Esta historia de 10-bit permite que patrones de 10 saltos sean descubiertos y predichos.
Next level Las entradas seleccionadas de la tabla de historia local se usan como índice de una tabla de 1K de entradas, que consisten en contadores de saturación de 3-bit, los cuales suministran la predicción local
Tamaño total: 4K*2 + 4K*2 + 1K*10 + 1K*3 = 29K bits! (~180,000 transistores)
60