TARDP Curso 05/06

Prophet/Critic Hybrid Branch Prediction

Ayose Falcón, Stark, Ramirez, Lai y Valero ISCA’04

Pablo Carazo Minguela – Junio/2006

TARDP Resumen Curso 05/06

• Híbrido ¿novedoso?

• Profeta • Crítico

pasado pasado

futuro

Híbrido 8K+8K vs 16K 2Bc-gskew

• Reduce errores hasta un 39%• Aumenta PC 7,8 .. 18%• Reduce PC leídas en un 8,6%

Resultados

BBB

TARDP 3

ÍNDICE• Introducción

• Trabajos relacionados

• Primera aproximación

• Filtrando el crítico

• Juntándolo todo

• Simulación

• Resultados

• Conclusiones

TARDP Introducción 4

Valdebernardo

profeta

crítico

??

TARDP 5

ÍNDICE• Introducción

• Trabajos relacionados

• Primera aproximación

• Filtrando el crítico

• Juntándolo todo

• Simulación

• Resultados

• Conclusiones

PredicA PredicB

BHSR

PC

Selec | Fusión

Híbrido

bitFuturo

TARDP Trabajos relacionados 6

PredicA PredicB

BHSR

PC

=?

Salto1 Salto2

Sobre-escrituraBHSR

PCPredictor

CT

0110 reduc

Estimador Confianza

BHSR’ Novedoso

tPi Ci

TARDP 7

ÍNDICE• Introducción

• Trabajos relacionados

• Primera aproximación

• Filtrando el crítico

• Juntándolo todo

• Simulación

• Resultados

• Conclusiones

TARDP Primera aproximación8

Profeta

Predicción

LQRSTUVWXY

PPC

BHSR

t

QRSTUVWXYP

Crítico

Crítica

BORQRSTU WXYPV

¿Unos ciclos más tarde?

UVWXY ABCDP

UVWXY ABCDP

Pasado

Futuro

P DCBA

¡Ojo!

A

B

E

H

D

C

GF

I J

T T

TARDP Primera aproximación (Un ejemplo) 9

WXYZ

• Error => Crítico se entrena

NOPQ

¿Esto es frecuente?

+ Interferencia…WXYZ

…NOPQ

PC

¡n*2 fallos!

• Sig (A, T) => Crítico (A,T)

Profeta

T T

T T

Crítico

TT

TT¿Cuánto?

TARDP Primera aproximación (Tasa de interferencias) 10

• Chang, Evers y Patt (1996)

• gcc y gshare con 8K entradas

Entradas con 32 interferencias o menos

Entradas con 325 interferencias o más

¡ 325 interferencias de media !

154.450.036

25.903.086

2.772.686

1.679.135

977.729

115.822

InstruccionesBccInterferencias

Neutras Destructi. Constructi. 0

500000

1000000

1500000

2000000

Neutras Destruc. Construc.

1.513.438

957.999

471.607

83.832

¡Filtrado!

TARDP 11

ÍNDICE• Introducción

• Trabajos relacionados

• Primera aproximación

• Filtrando el crítico

• Juntándolo todo

• Simulación

• Resultados

• Conclusiones

BOR10101 01000

dirSalto

Crítico

predicc.

TARDP Filtrando el Crítico 12

• El Profeta acierta ≈ 90..95% => El Crítico se centre en el otro 5..10%

Filtro

tagHash

=?

Acierto CríticaFalloProfecía

Falla Meter salto en el Crítico

TARDP 13

ÍNDICE• Introducción

• Trabajos relacionados

• Primera aproximación

• Filtrando el crítico

• Juntándolo todo

• Simulación

• Resultados

• Conclusiones

TARDP Juntándolo todo (I) 14

• Reinman, Austin y Calder (1999):

Escalado de conexiones Front-End desacoplado

FTQ L1 I-CacheSegmentada

Decodi. Ejecución

MUX sigPC

sigBloque

L1 FTB

ultBloque

miss [jump, jsr, rst]miss Bcc

L2 FTB L2 I-CacheProfeta

Crítico

profeta

crítico

??

Crítico

TARDP Juntándolo todo (II) 15

ProfetaI-Cache & Fetch

A

FTQ

ABCDEFGHIJKL BCDEF

BOR

4 b futuro

I H G

Ideal: FTQ casi siempre bastante llena

2xCiclo

1xCiclo 6µOpxCicloBcc cada 13µOP

Pega: No hay suficientes bits de futuro Con 8b 0,1% veces

¡ Usar los que haya !

¿Crítico corrige predicción?Efecto limitado a la FTQ

TARDP 16

ÍNDICE• Introducción

• Trabajos relacionados

• Primera aproximación

• Filtrando el crítico

• Juntándolo todo

• Simulación

• Resultados

• Conclusiones

TARDP Simulación 17

• Micro tipo Pentium 4 * 2

3,8GHz; 6OPC; L1I 64KB; L1D 32KB; L2 2MB; FTQ 32

• Predictores utilizados: Gshare, 2Bc-gskew y Perceptron

• 108 bancos de pruebas: tpcc, premiere, msvc7, unzip, facerec, …

TARDP 18

ÍNDICE• Introducción

• Trabajos relacionados

• Primera aproximación

• Filtrando el crítico

• Juntándolo todo

• Simulación

• Resultados

• Conclusiones

TARDP Resultados 19

• Importancia de los bits de futuro

• Precisión de la predicción

• Distribución de las críticas

• Productividad del conjunto

TARDP Resultados (Importancia de los bits de futuro) 20

Profeta: 8KB perceptron + Crítico: 8KB gshare etiquetado

Unos pocos bits OK Más no rentables?

¿8 OK?

TARDP Resultados (Precisión de la predicción) 21

Mejoras:25..31%

Con 32KBparecido

TARDP Resultados (Distribución de las críticas) 22Pro Crí

Pro Crí

Pro Crí

Pro Crí

¿ Profeta + [Crítico] ?3Bcc => 1 Crítico 4Bcc => 1 Crítico

Profeta2 3

¡ Acierta el 98,7% !

TARDP Resultados (Productividad del conjunto) 23

TARDP 24

ÍNDICE• Introducción

• Trabajos relacionados

• Primera aproximación

• Filtrando el crítico

• Juntándolo todo

• Simulación

• Resultados

• Conclusiones

TARDP Conclusiones 25

Híbrido 8K+8K vs 16K 2Bc-gskew

• Reduce errores hasta un 39%• Aumenta PC 7,8 .. 18%• Reduce PC leídas en un 8,6%

Resultados

BBBSegún los

propios autores

• Needs fast hardware to compute prediction/mispredictions and refile the FTQ before branches consumed by I-Cache

• Large tag small coverage, small tag contention; Therefore it is not universal

• How to select branches to cover in the filtered critic

FIN