precisión de predicción de bifurcación de 2 bits

Navega tus respuestas
4

Estoy tratando de resolver este problema, la respuesta debería ser 15/20 = 75%.

Sin embargo, no estoy seguro de cómo se calculó esto y quiero entender el concepto subyacente.

Un núcleo de programa consta de cinco ramas condicionales. El núcleo del programa será ejecutado miles de veces. A continuación se muestran los resultados de cada rama para una ejecución del núcleo del programa (T = tomada, N = No tomada). 

 Branch 1: T-T
 Branch 2: N-N-N
 Branch 3: T-N-T-N-T
 Branch 4: T-T-T-N
 Branch 5: T-T-N-T-T-T

Este comportamiento sigue siendo el mismo. Para esquemas dinámicos, suponga que cada rama tiene su propio búfer de predicción y que cada búfer se inicializa en el mismo estado antes de la ejecución.

¿Cuál es la precisión de la predicción para el predictor de 2 bits, inicializada para predecir débilmente tomada? (La respuesta es al principio, pero me gustaría entender el concepto del cálculo).

    
pregunta Carlo

4 respuestas

5

En primer lugar, creo que es importante que especifique cuándo hace este tipo de problemas (y aclare preguntando a su profesor) qué tipo de predictor de 2 bits se está utilizando, porque hay 2 tipos.

El primer tipo realiza una transición de un estado débil al estado débil alternativo en caso de fallo.

El segundo tipo realiza una transición de un estado débil al estado fuerte alternativo en caso de falla.

Para este problema, asumo que es el tipo first , que pasa de un estado débil al estado débil alternativo en caso de fallo. Ese es el tipo que se muestra en la siguiente imagen:

Considere lo que sucede en cada caso individualmente:

WT = tomado débilmente ST = fuertemente tomado WN = débilmente no se toma SN = fuertemente no tomado

Rama # 1 

Predict WT - T : 1/1

Predict ST - T : 1/1

Total: 2/2

Rama # 2 

Predict WT - N : 0/1

Predict WN - N : 1/1

Predict SN - N : 1/1

Total 2/3

Rama # 3 

Predict WT - T : 1/1

Predict ST - N : 0/1

Predict WT - T : 1/1

Predict ST - N : 0/1

Predict WT - T : 1/1

Total: 3/5

Rama # 4 

Predict WT - T : 1/1

Predict ST - T : 1/1

Predict ST - T : 1/1

Predict ST - N : 0/1

Total: 3/4

Rama # 5 

Predict WT - T : 1/1

Predict ST - T : 1/1

Predict ST - N : 0/1

Predict WT - T : 1/1

Predict ST - T : 1/1

Predict ST - T : 1/1

Total: 5/6

Total de todas las sucursales : 15/20

    
respondido por el krb686
2

Un predictor de dos bits es solo un número de 0 a 3, como este

  • 0 - fuertemente no tomado
  • 1 - débilmente no tomado
  • 2 - tomado débilmente
  • 3 - fuertemente tomada

donde estado (2) es lo que obtendrías en la primera ejecución de la rama.

  • Rama 1: T-T: el predictor es correcto la primera vez, y el predictor aumenta (con saturación en (3)) y predice "tomado" para ambas iteraciones
  • Rama 2: N-N-N: la primera es una falla, y el predictor disminuye (con saturación en (0)), lo que predice las siguientes dos Ns. Tenemos 2 hits, 1 miss.
  • Rama 3: T-N-T-N-T: la que está aquí es interesante. Oscilamos entre (3) y (2), equivocándonos en cada "N". 3 hits, 2 fallidos.
  • rama 4: T-T-T-N - esto es similar; de cada 4 casos, uno está mal manejado
  • Rama 5: T-T-N-T-T-T: nuevamente, de cada 6 ocurrencias, una está mal predicha.

Sumando éxitos y fallos: (2h + 0m) + (2h + 1m) + (3h + 2m) + (3h + 1m) + (5h + 1m)

Sumando: 15 hits, 5 fallos

Precisión = aciertos / (aciertos + fallos) = 15 / 20.

    
respondido por el anrieff
2

Suponiendo que este es un predictor de rama local, la respuesta de 5 predicciones erróneas y 15 predicciones correctas. La forma más fácil de visualizar este problema es creando el FSM para un predictor de ramificación de 2 bits y fluyendo a través de cada rama para ver qué predice el predictor y a qué estado se mueve:

Usando este FSM, nosotros por rama vemos lo que predice y lo que sigue: 

Branch 1:

Step:         T   T
Prediction:   T   T
State:        WT  ST
NextState:    ST  ST
Correct?:     Y   Y

Branch 2:

Step:         N   N   N
Prediction:   T   N   N
State:        WT  WNT SNT
NextState:    WNT SNT SNT
Correct?:     N   Y   Y

Branch 3:

Step:         T   N   T   N   T
Prediction:   T   T   T   T   T
State:        WT  ST  WT  ST  WT
NextState:    ST  WT  ST  WT  ST
Correct?:     Y   N   Y   N   Y

Branch 4:

Step:         T   T   T   N
Prediction:   T   T   T   T
State:        WT  ST  ST  ST
NextState:    ST  ST  ST  WT
Correct?:     Y   Y   Y   N

Branch 5:

Step:         T   T   N   T   T   T
Prediction:   T   T   T   T   T   T
State:        WT  ST  ST  WT  ST  ST
NextState:    ST  ST  WT  ST  ST  ST
Correct?:     Y   Y   N   Y   Y   Y

Entonces, si contamos el número de Y, obtenemos 15/20 o una precisión del 75%. (a la inversa, 5/20 Ns, con un 25% de predicción errónea).

    
respondido por el Unn
0

Bueno, ni siquiera necesita hacer los cálculos matemáticos si observa que un predictor de 2 bits cambia de parecer si predice mal dos veces seguidas.

Rama 1: siempre predice a la derecha (2/2)

Rama 2: siempre predice derechos (3/3)

Rama 3: esta es interesante. Para esto necesitas escribir los estados y hacer los cálculos. Resulta que puede predecir correctamente 3 de 5. En este caso, el valor inicial del predictor es importante.

Rama 4: 3 de 4

Rama 5: 5 de 6

el total es 15 de 20.

Para llevar: un predictor local de 2 bits funciona bien para las ramas muy sesgadas, pero no para las ramas que cambian con frecuencia (como la rama 3).

    
respondido por el aminfar

Lea otras preguntas en las etiquetas

Reducir el ruido de lectura analógica en arduino ¿La proximidad al agua afectaría un magnetómetro?