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

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