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

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