Paralelismo a nivel de instrucción (ILP)

Reducir el tiempo de ejecución de un programa: $$ T = IC \cdot CPI \cdot T_{CK} $$

Con lo que habrá que reducir el CPI (ciclos por instrucción) porque se supone IC fijo (compilador) y \( T_{CLK} \) (tecnología).

Existen dos formas:

1. Segmentación: Solapamiento: incremento de etapas
2. Paralelización
   • Paralelismo espacial (replicación: incremento de recursos)
   • Técnicas estáticas de planificación: lo hace el compilador
   • Técnicas dinámicas de planificación: lo hace el compilador
3. Ténicas de compilación (reordenación)

Arquitectura segmentada en MIPS

Divide cada tarea en varias etapas más cortas y solapa su ejecución.

1. IF (instruction fetch): Carga de instrucción desde memoria
2. ID (instruction decode): Decodificación de instrucción y lectura de registros
3. EX (execute): Ejecución de operación o cálculo de dirección
4. MEM (memory): Acceso a operando de memoria
5. WB (write back): Escritura del resultado en registro

Riesgos segmentado

Situaciones en las que la siguiente instrucción no se puede ejecutar en el ciclo siguiente y se debe retrasar (stall) :

• Riesgos estructurales:Se necesita un recurso que está siendo utilizado
• Riesgos de datos: Hay que esperar a que la instrucción previa lea/escriba un dato
• Riesgos de control: Hay que completar la instrucción para conocer la decisión de control

El paralelismo a nivel de instrucción lo determinan

• Las dependencias: propiedad del programa: Fija el orden, el máximo paralelismo y la posibilidad de riesgos
• Los riesgos: propiedad de la arquitectura: Fija los riesgos detectables y los riesgos que producen paradas

Prestaciones en presencia de paradas

$$ S = \frac{T_{\text{no-seg}}}{T_{\text{seg}}} = \frac{(\text{CPI}\text{no-seg} \cdot T{\text{CK,no-seg}})}{(\text{CPI}{\text{seg}} \cdot T{\text{CK,seg}})} $$

Segmentar puede interpretarse como bajar CPI o \(T_{CK}\). Si hay paradas (Stalls) \(\text{CPI}{\text{seg}} = \text{CPI}{\text{ideal}} + \text{CPI}{\text{stall}} = 1 + \text{CPI}{\text{stall}}\)

• Segmentación interpretada como bajada de CPI: Se supone que \(T_{CK} = T_{CK,seg}\), luego \(CPI_{no-seg} \gt 1 \). Con N etapas perfectamente equilibradas: \(CPI_{no-seg} = N\) $$ S = \frac{\text{CPI}{\text{no-seg}}}{1 + \text{CPI}{\text{stall}}} = \frac{N}{1 + \text{CPI}{\text{stall}}} = \frac{N}{1 + f{\text{salto}} + \text{Coste}_{\text{salto}}} $$

$$ CPI_{\text{seg}} = \frac{\text{Total ciclos}}{\text{Total instrucciones}} = 1 \qquad CPI_{no-seg} = 1 $$ Lo que marca la diferencia es el reloj.

Tipos de riesgo de datos

• Lectura tras escritura (RAW)

add $r1, $r2, $r3
sub $r4, $r1, $r3

• Escritura tras lectura (WAR)

sub $r4, $r1, $r3
add $r1, $r2, $r3

• Escritura tras escritura (WAW)

sub $r1, $r4, $r3
add $r1, $r2, $r3

Ténica de adelanto de datos

Se denomina forwarding o bypssing. Se usa el dato cuando se acaba de calcular o cargar. Sin esperar a gruadarlo en un registro. Se necesitan conexiones adicionales en la ruta de dato.

No se puede adelantar datos, es decir, atrás en el tiempo.

Reordenación para evitar riegos load-ALU

El primero es menos eficiente, Operación es \(A = B + E; C = B + F\)

lw $t1,0($t0) 
lw $t2,4($t0) 
add $t3,$t1,$t2 
sw $t3,12($t0) 
lw $t4,8($t0) 
add $t5,$t1,$t4 
sw $t5,16($t0)

Se reordena para ser más eficiente

lw $t1,0($t0) 
lw $t2,4($t0) 
lw $t4,8($t0) 
add $t3,$t1,$t2 
sw $t3,12($t0) 
add $t5,$t1,$t4 
sw $t5,16($t0)

Riegos de penalización por salto

Un salto determina el flujo de control

• La carga de la siguiente instrucción depende de la dirección
• La dirección de salto no siempre se sabe al cargar (IF)
• Si la dirección de salto se conoce en MEM -> 3 ciclos de parada

Técnicas estáticas de predicción de salto

• Predicción estática de salto (~50% de aciertos)
  • Nunca se salta (not-taken) o siempre se salta (taken)
  • Si se falla: parar, descartar instrucciones (flush) y cargar nuevo destino
• Salto retrasado (delayed branch) (~50% de paradas evitadas)
  • El compilador pone una instrucción tras el salto que siempre se ejecuta

Ténicas dinámicas de predicción de salto

• Ejecución especulativa
  • Se sigue ejecutando mientras no se sabe el resultado del salto
  • Se pueden ejecutar las dos secuencias de instrucciones posibles (más hardware)
• Predicción dinámica de salto (80-97% de paradas evitadas)
  • Se almacena en HW la historia reciente de cada instrucción de salto
  • Se supone que la tendencia se va a mantener
  • Si se falla: parar, cargar la instrucción destino y actualizar la historia

En la predicción dinámica de salto

• Correlación temporal: predecir lo mismo que pasó la última vez
• Correlación espacial: resultado correlado en saltos próximos

Búfer de predicción de saltos (BHT, Branch History Table)

• Indexado con las direcciones de las instrucciones de salto
• Sólo se mantienen las instrucciones de salto más recientes
• Almacena el resultado (salto o no salto)
• Al ejecutar una instrucción de salto
  • Buscar en el búfer y esperar el mismo resultado
  • Empezar a cargar instrucciones según la predicción
  • Si la predicción no es correcta, vaciar el pipeline y corregir la predicción

Predictor de 1 bit bimodal

Sólo almacena el último reslultado. Presenta limitaciones

Predictor de 2 bits bimodal

Sólo cambia la predicción después de fallar dos veces. (El caso más frecuente).

Ejercicio típico