RIESGOS DE CONTROL: ALTERNATIVAS
Detener hasta que la dirección de salto este clara
Predecir que el salto no se va a efectuar
Ejecutar las instrucciones siguientes en la secuencia
PC+4 ya está calculado, se utiliza para obtener la siguiente instrucción
Eliminar las instrucciones introducidas en el cauce en el caso de que el salto haya que efectuarlo
47% de los saltos en el proc MIPS no se efectúan (en promedio)
Predecir que el salto se va a efectuar
53% de los saltos en el proc MIPS se efectúan (en promedio)
Pero en el caso de este proc. La dirección objetivo del salto no tiene que calcularse.
MIPS sólo tiene una penalización de 1 ciclo por salto
Otras máquinas: el objetivo del salto es conocido antes de que finalice la instrucción
11
RIESGOS DE CONTROL: ALTERNATIVAS (CONT)
Saltos retardados (delayed branch)
Se rellena con instrucciones no dependientes situadas antes de la instrucción de salto la burbuja que genera el salto.
Efectividad de esta técnica (la realiza el compilador) para una ventana de 1 ciclo (branch delay slot = 1)
El compilador es capaz de rellenar alrededor de un 60% de estas ventanas de retardo
Alrededor del 80% de las instrucciones ejecutadas en estas ventanas de retardo son instrucciones útiles en los cálculos
Aproximadamente el 50% (60%x80%) de los slots son adecuadamente rellenados
instrucción de salto
instrucción 1
instrucción 2
…
instrucción n
instrucción si salto tomado
retardo de longitud “n”
12
Optimización Branch CPI speedup v. speedup v. tipo penal. nosegment stall
Detención 3 1.42 3.52 1.0
Predic. taken 3 o 0 1.27 3.93 1.11
Predic. not taken 3 o 1 1.24 4.04 1.14
Delayed branch 0.5 1.07 4.6 1.31
IMPACTO DE LAS DETENCIONES
(Gp:) Pipeline depth
(Gp:) 1 + Branch frecuency x Branch penalty
(Gp:) Pipeline Speedup =
13
PREDICCIÓN DEL SALTO
Para disminuir el efecto sobre las prestaciones de los riesgos de control se utiliza la predicción
En la etapa IF (instr fetch) es necesario predecir la dirección y el objetivo del salto
La predicción puede ser:
Estática:
Siempre se predice si el salto es efectuado o no
Dinámica:
La predicción se basa en la historia previa del salto
14
PREDICCIÓN DINÁMICA DE SALTOS
Motivo: los saltos tienden a ser consistentes
Por ejemplo: bucles, condiciones de error, tratamiento de casos límite
Idea: predecir dinámicamente si un salto va a ser efectuado o no de acuerdo con la historia previa del salto
Predicción:
Una vez que el salto es descodificado, la búsqueda continua por uno de sus caminos posibles
Predicción incorrecta:
Si la ejecución del salto muestra que el camino predicho es incorrecto, es necesario seguir por el otro
Se vacían todas las instrucciones del camino incorrecto
Los errores de predicción tienen un impacto muy importante en las prestaciones, este impacto depende de:
Profundidad de la segmentación y de la frecuencia de las instrucciones de salto
15
PREDICCIÓN DINÁMICA DE SALTOS
Algoritmo con dos fases:
Fase de predicción:
Se realiza durante la etapa de búsqueda
Se realiza de acuerdo con la historia del salto
Fase de actualización
Se realiza durante la etapa de ejecución
Se realiza de acuerdo con la predicción y el resultado
(Gp:) IF
(Gp:) ID
(Gp:) EXE
(Gp:) MEM
(Gp:) WB
(Gp:) BRANCH
PREDICTOR
(Gp:) UPDATE
(Gp:) LOOKUP
16
2. TÉCNICAS DE PREDICCIÓN DE SALTOS
La predicción de saltos condicionales requiere:
Predecir si se tomará el salto
Predecir la dirección destino del salto
Las técnicas se pueden clasificar en dos grandes grupos:
Predicción estática. Son predictores que no utilizan ningún tipo de información en tiempo de ejecución sobre el comportamiento anterior de los saltos.
Predicción dinámica. Son predictores que pueden supervisar el comportamiento de los saltos mientras se ejecutan y realizan predicciones en función de las observaciones .
17
2.1. TÉCNICAS DE PREDICCIÓN ESTÁTICA DE SALTOS
Suelen ser técnicas simples, pero limitadas en su eficiencia.
Existen dos grandes grupos:
Predicción estática basada en reglas.
Usan reglas predeterminadas.
Predicción estática basada en perfiles.
Las técnicas basadas en perfiles se basan en la posibilidad de aproximar el comportamiento de un salto mediante distintas ejecuciones del programa sobre datos de prueba.
Pueden aprovechar también la información de alto nivel disponible en tiempo de compilación.
Pueden conseguir mejores rendimientos que las basadas en reglas.
Su desventaja es que al ser creadas en tiempo de compilación es necesario recompilar de nuevo para cambiarlas.
Si las estadísticas no están bien realizadas la predicción puede ser mala.
18
PREDICCIÓN ESTÁTICA BASADA EN REGLAS
Existen diversas estrategias, entre ellas:
Predicción en una única dirección.
Predicción BTFNT (backwards taken/ forward not taken)
Predicción heurística basada en el programa [Ball-Larus, 1993]
19
PREDICCIÓN EN UNA ÚNICA DIRECCIÓN
Consiste en predecir que la dirección de todos los saltos va siempre en la misma dirección (es decir siempre tomado o siempre no tomado).
Se basa en que estadísticamente los saltos suelen ser tomados con más frecuencia (60%) que no tomados (40%).
El Intel 486 (1997) usaba la estrategia de predecir siempre que el salto no se toma porque simplifica la estrategia de extraer la instrucción, ya que se comienzan a ejecutar de forma automática las instrucciones situadas después del salto condicional.
La estrategia opuesta, suponer que el salto se tomará siempre tiene mejor tasa de aciertos que la anterior, pero requiere un hardware más complejo ya que la dirección de destino del salto no suele estar disponible cuando se hace la predicción.
Siempre se puede usar el concepto de ventana de retardo.
20
PREDICCIÓN BT-FNT
Es una variante del esquema anterior, consiste en predecir que los saltos hacia atrás se tomarán siempre y que los saltos hacia adelante no se tomarán.
Se basa en que los saltos hacia atrás suelen corresponder a bucles que suelen ser iterados bastantes veces antes de terminar.
Muchos procesadores han utilizado este enfoque.
Es muy fácil de implementar pues basta con comprobar el signo del desplazamiento respecto al PC que va codificado en la propia instrucción.
El Intel Pentium IV ha usado esta estrategia.
21
PREDICCIÓN HEURÍSTICA BASADA EN EL PROGRAMA
Consiste en predecir la dirección mediante una serie de reglas:
Regla:
Salto de bucle: Si el destino del salto vuelve al comienzo del bucle se predice que será tomado.
Terminación de bucle: si se salta dentro de un bucle, y ninguno de los destinos es el comienzo del bucle se predice que el salto no será tomado.
Comienzo de bucle: se predice que el bloque posterior a un salto que sea comienzo de un bucle será tomado.
Llamada: si el bloque posterior contiene una llamada a subrutina se predice que el salto va a ese bloque posterior.
Almacenamiento: si un bloque posterior contiene una instrucción de almacenamiento se predice que el salto no va a ese bloque posterior.
ETC.
Es necesario añadir algo de información al código de operación de los saltos cuando se usa esta estratega.
22
PREDICCIÓN ESTÁTICA BASADA EN PERFILES
Esta estrategia de predicción requiere ejecutar el programa sobre datos de ejemplo para extraer y recopilar estadísticas que hay que suministrar al compilador.
El compilador usa estos perfiles para hacer predicciones estáticas que se insertan en el código binario del programa como ayudas a los saltos.
Una estrategia simple consiste en determinar la frecuencia de saltos tomados para cada instrucción de salto del programa (o si hay varias ejecuciones del programa usar datos promediados).
Si el promedio es superior al 50% el bit de ayuda al salto se marca para predecir que será tomado.
Ventaja: esta técnica es muy fácil de implementar en términos de hardware.
Desventaja: el sistema es muy rígido, ya que se establece y fija en tiempo de compilación y se requiere que la instrucción lea de la cache para poder conocer la predicción del salto.
23
2.2. TÉCNICAS DE PREDICCIÓN DINÁMICA DE SALTOS
Las técnicas de predicción estáticas alcanzan tasas de acierto del 70-80%. Pero si la información estadística no es buena la tasa de aciertos baja considerablemente.
Los métodos de predicción dinámicos suelen lograr tasas de acierto entre el 80% y 95%.
Métodos básicos:
Algoritmo de predicción de Smith (1981).
Predictor de 1-bit
Predictor de 2-bit.
Tablas de predicción de 2 niveles (1992).
Predictor de historia global
Predictor de historia local
Por conjuntos
Predictores de índice compartido (1993).
Gshare (1993)
Pshare (1996)
Predictores de reducción de interferencias
Predictores Tournament
24
PREDICCIÓN DINÁMICA: PREDICTOR DE SMITH
El predictor de Smith (1981) fue uno de los primeros algoritmos de predicción dinámica.
Consiste en:
Una tabla que registra para cada salto si las instancias anteriores se tomaron o no.
Se cuenta las veces que se tomó el salto en las últimas veces que se presentó, y el bit más significativo de este contador se utiliza como predicción del salto.
Si el salto se toma se incrementa en 1 el contador (salvo que esté en el valor máximo, es decir saturado)
Se le denomina también contador de saturación de k bits.
25
Esquema
Dirección de salto
(Gp:) 2m contadores de
k bits
(Gp:) .
.
.
Contador de saturación
incr./decrem.
bit más
significativo
Predicción de
salto
valor actualizado
del contador
Resultado del
salto
m
PREDICCIÓN DINÁMICA: PREDICTOR DE SMITH
26
Si k=1 bit, tenemos el denominado predictor de un bit que utiliza sólo la información de la última vez que se presentó el salto.
Si k=2 bits, es el denominado contador de saturación de 2 bits o predictor bimodal, que se utiliza en muchos predictores.
Ejemplo:
PREDICCIÓN DINÁMICA: PREDICTOR DE SMITH
27
Fase de predicción
Se mantiene y actualiza una Tabla Histórica de Saltos (Branch Prediction Buffer BPB)
Los bits menos significativos del PC sirven como índice de una tabla de 1-bit
Este bit indica si se efectuó o no el último salto
PREDICTOR DE SMITH: BUFFER DE PREDICCIÓN DE SALTOS (BPB) DE 1-BIT
28
Fase de actualización
Después de la ejecución, se marca en la entrada apropiada si el salto ha sido tomado o no (T/NT)
Problema: el BPB sólo es útil si el salto puede calcularse antes de la predicción del salto (esto no es posible en el MIPS)
PREDICTOR DE SMITH: BUFFER DE PREDICCIÓN DE SALTOS (BPB) DE 1-BIT
29
Problema: en un bucle, la predicción con 1-bit origina 2 predicciones erróneas (en promedio un bucle se ejecuta 9 veces antes de finalizar):
Al final del bucle, cuando termina en vez de continuar el bucle como en los casos anteriores
La primera vez que pasa por el bucle, se predice que se saldrá en vez de predecir que se hace el bucle
Esto origina un 80% de precisión en la predicción
Solución: esquema de 2-bits donde el cambio de predicción sólo se hace si hay dos errores de predicción
PREDICTOR DE SMITH: BUFFER DE PREDICCIÓN DE SALTOS (BPB) DE 1-BIT
30
 Página anterior | Volver al principio del trabajo | Página siguiente  |