Rendimiento y Speedup en Arquitecturas de Computadores
Cálculo del Speedup por Mejora de CPI y Ciclo de Reloj
En un cierto programa, las instrucciones de punto flotante (PF) representan el 40% del total de instrucciones ejecutadas y tienen un CPI=8, mientras que las de enteros (ENT) representan el 60% restante y tienen un CPI=1. Ese mismo programa lo ejecutamos en otro computador en el que, gracias a las mejoras de la arquitectura y la tecnología, hemos conseguido reducir el CPI de las instrucciones de PF a 2 y el ciclo de reloj lo hemos reducido en un 25%. El CPI de las instrucciones de ENT no ha variado. Determina razonadamente el valor del Speedup obtenido.
Tiempo de Ejecución del Sistema Original (TSM)
$$T_{SM} = N_{instr} \times CPI_{medio} \times t_c = N_{instr} \times (0,4 \times 8 + 0,6 \times 1) \times t_c$$
$$T_{SM} = N_{instr} \times 3,8 \times t_c$$
Tiempo de Ejecución del Sistema Mejorado (TM)
El nuevo ciclo de reloj es $t’_c = 0,75 \times t_c$.
$$T_{M} = N_{instr} \times CPI’_{medio} \times t’_c = N_{instr} \times (0,4 \times 2 + 0,6 \times 1) \times (0,75 \times t_c)$$
$$T_{M} = N_{instr} \times 1,4 \times 0,75 \times t_c$$
Cálculo del Speedup (S)
$$S = \frac{T_{SM}}{T_{M}} = \frac{3,8}{1,4 \times 0,75} \approx 3,62$$
El Speedup obtenido es de 3,62.
Consumo de Energía y Potencia Dinámica
Efecto de la Reducción de VDD en Energía y Potencia
Hemos estudiado que la reducción de la tensión de alimentación, VDD, de los procesadores tiene un importante efecto sobre el consumo de energía dinámica y la potencia dinámica. Si dado un procesador reducimos su VDD al 80%, explica razonadamente:
- En qué porcentaje se reduce el consumo de energía dinámica.
Por la expresión $E_{dinámica} \propto VDD^2 \times C_{load}$, sabemos que la energía dinámica es proporcional a $VDD^2$. Si cambiamos la tensión de alimentación original, $VDD$, por $(0,8 \times VDD)$, la energía dinámica consumida será proporcional a $(0,8 \times VDD)^2$, es decir, a $0,64 \times VDD^2$. Por lo tanto, esta energía consumida se reduce al 64% del valor original.
- En qué porcentaje se reduce la potencia dinámica.
La reducción de VDD también tiene un impacto lineal sobre la frecuencia. Por tanto, si multiplicamos VDD por 0,8, tenemos que multiplicar la frecuencia máxima por el mismo factor.
Por la expresión $P_{dinámica} \propto VDD^2 \times C_{load} \times Frecuencia$, sabemos que la potencia dinámica es proporcional a $VDD^2$ y a la frecuencia. El efecto es que la potencia dinámica queda multiplicada por $(0,8)^2 \times 0,8 = 0,512$. Es decir, se reduce al 51,2% del consumo original.
Diferencia entre Energía Estática y Dinámica y Técnicas de Reducción
Cuando hablamos del consumo de energía de los procesadores, explica brevemente qué entendemos por energía estática y energía dinámica. ¿Cuáles son las principales técnicas que se usan para reducir ambos tipos de energía?
Energía Dinámica
Energía consumida para la conmutación de los transistores.
Técnicas para reducirla:
- Evitar conmutaciones innecesarias.
- Usar transistores más pequeños, rápidos y de menor consumo (aunque esto implique una mayor cantidad en el chip).
Energía Estática
Energía que se consume, aunque los transistores no estén conmutando (debido a corrientes de fuga o leakage).
Técnicas para reducirla:
- Evitar leakage en módulos que no se están usando.
- Suprimir la alimentación (power gating).
Planificación Dinámica de Instrucciones (Algoritmo de Tomasulo)
Registro de Reordenación (ROB) en Tomasulo con Especulación
Explica brevemente cuál es la función que desempeña el ROB en el algoritmo de Tomasulo con especulación. ¿Qué fases del dicho algoritmo pueden ejecutarse fuera de orden y cuáles deben ser en orden?
Función del ROB (Reorder Buffer)
El ROB almacena resultados de instrucciones cuya ejecución ha finalizado, pero que:
- Están a la espera de actualizar registros o memoria.
- Son dependientes de un salto especulado.
Además, permite el paso de operandos entre instrucciones especuladas con dependencia LDE (Lectura Después de Escritura).
Fases de Ejecución
- Fases que pueden ejecutarse fuera de orden: Ejecución, Escritura (Write Result).
- Fases que deben ejecutarse en orden: Issue (Emisión), Commit (Confirmación).
Operaciones y Gestión de Fallos en el ROB
En una arquitectura con planificación dinámica de instrucciones y especulación mediante un ROB:
- Explica brevemente lo que ocurre cuando una instrucción de tipo ADDD ejecuta la fase WRITE.
Cuando el ADDD ejecuta la fase Write Result (Escritura), actualiza el campo Valor del ROB con el resultado de la ejecución de la instrucción y pone el campo Listo a ‘Sí’. Además, actualiza todas las Estaciones de Reserva (ER) que contenían la etiqueta del ROB (el número de entrada del ROB) como operando pendiente.
- ¿Qué se hace cuando una instrucción de salto llega a la cabecera del ROB?
- Si es instrucción de salto bien predicha: Se elimina del ROB.
- Si es instrucción de salto mal predicha:
- Se borra el contenido del ROB, las ER y el Load Buffer.
- Se borran las marcas (campo “número de ROB”) de todos los registros.
- Se busca la instrucción correcta para reanudar la ejecución.
- Si una instrucción genera una interrupción.
- Registrar la petición en el ROB.
- Si la instrucción llega a la cabecera del ROB (es decir, no está especulada), entonces se reconoce la interrupción.
- Cualquier instrucción anterior habrá finalizado. Por tanto, ninguna instrucción anterior puede provocar una excepción que deba manejarse antes.
Situación de Escritura Simultánea en el ROB (Fase WRITE)
En el algoritmo de Tomasulo con especulación, existe alguna situación en que dos instrucciones hacen la fase WRITE (escritura del resultado en el ROB) en el mismo ciclo de reloj. Explica en detalle cuál es esa situación. Para la explicación, se recomienda usar un ejemplo formado por un par de instrucciones concretas.
Esta situación se da cuando existe una dependencia LDE (Lectura Después de Escritura) entre una instrucción aritmética o load y un store posterior que hace issue antes de que la instrucción de la que depende escriba su resultado en el ROB.
Ejemplo: Si tenemos la secuencia:
ADDD F6, F4, F6
SD 0(R2), F6
Es muy probable que la instrucción SD
haga la fase issue antes de que ADDD
haya escrito su resultado en el ROB. En ese caso, al lanzar el SD
, se pone en su campo Valor el número de ROB donde está alojada la ADDD
(llamémosle $ROB_x$).
Cuando la operación ADDD
hace la fase Write Result (y $ROB_x$ aparece sobre el CDB), se chequea si alguna entrada del ROB tiene en su campo Valor el número $ROB_x$. Como esto es lo que ocurre con el campo Valor de la SD
, entonces el resultado que está sobre el CDB se copia:
- Sobre el campo Valor de la instrucción
ADDD
(su destino). - También sobre el campo Valor de la instrucción
SD
(que lo necesita como operando).
Ambas escrituras en el ROB ocurren simultáneamente en el mismo ciclo de reloj.
Riesgos de Dependencia a Través de Memoria en Tomasulo con Especulación
En una arquitectura con planificación dinámica de instrucciones que implementa el algoritmo de Tomasulo con especulación, explica brevemente si pueden aparecer riesgos LDE, EDL y EDE a través de memoria y, en caso afirmativo cómo se tratan.
- Riesgos EDE (Escritura Después de Escritura) y EDL (Escritura Después de Lectura): No pueden aparecer dado que la actualización de memoria (instrucciones
ST
) se hace en orden (solo cuando elST
llega a la cabecera del ROB). Esto asegura que todos losLD
yST
anteriores se han completado. - Riesgos LDE (Lectura Después de Escritura): Podrían producirse si una instrucción
LD
accede a la posición de memoria A, habiendo en el ROB unST
previo que almacena el resultado en A. Se evitan mediante el siguiente mecanismo:- Un
LD
no ejecuta el acceso a memoria si hay unST
previo en el ROB con la misma dirección de memoria. - Tampoco se ejecuta el
LD
si está pendiente el cálculo de la dirección efectiva de algúnST
del ROB.
- Un
Tomasulo sin Especulación: Función del Tag y del Store Buffer
En una arquitectura con planificación dinámica de instrucciones mediante Tomasulo sin especulación:
- Explica cuál es la función que desempeña el campo de tag de los registros.
El tag se llama $Q_i$. Indica el número o identificador de la Estación de Reserva (ER) que está produciendo el valor que se va a almacenar en el registro. Si $Q_i = 0$, significa que no hay ninguna instrucción en la ER que vaya a generar y almacenar un nuevo valor en el registro.
- Describe qué campos existen en un Store Buffer y cuál es su función.
El Store Buffer (SB) almacena las instrucciones de almacenamiento pendientes. Sus campos son:
- $V_i$: Valor que debe ser almacenado en memoria (si está calculado).
- $Dir$: Dirección de almacenamiento.
- $Q_i$: Número de la ER que está produciendo el resultado. Si $Q_i = 0$, el valor ya está calculado.
- $Busy$: 1 bit que indica si la entrada del SB está libre u ocupada.
Mecanismo de Escritura en el Bus Común de Datos (CDB)
Supongamos una arquitectura que utiliza el algoritmo de Tomasulo sin especulación. En el momento en que se deposita un resultado sobre el CDB, explica brevemente:
- Junto con el resultado, ¿qué información aparece además sobre el CDB?
Aparece la marca de identificación (tag) de la Estación de Reserva o Load Buffer del que proviene el resultado.
- ¿Cómo se determina cuáles son los elementos de la arquitectura en los que se guarda el valor de dicho resultado?
El resultado que está sobre el CDB se guarda en todos los registros, campos de operando de las Estaciones de Reserva y campos de operando del Store Buffer cuya marca coincida con la marca (tag) que está en ese momento en el CDB.
Estaciones de Reserva (ER) en Tomasulo sin Especulación
En un procesador con Planificación Dinámica mediante el algoritmo de Tomasulo sin especulación, explica brevemente qué son las Estaciones de Reserva, cuál es su función y qué información almacenan.
Las Estaciones de Reserva (ER) son registros asociados a las unidades funcionales. Contienen la información necesaria para la ejecución de la instrucción.
Función: La ER está a la espera de que los operandos que se necesitan para ejecutar la instrucción sean generados. Una vez que los operandos están listos, ejecuta la operación y libera el registro de la ER.
Cálculo de la Anchura del TAG y el Tamaño de la Ventana de Instrucciones
Supongamos una arquitectura con planificación dinámica de instrucciones que utiliza el algoritmo de Tomasulo sin especulación.
- Explica razonadamente qué datos necesitarías para poder calcular la anchura mínima necesaria para el campo de TAG. ¿Y para poder calcular el tamaño de la ventana de instrucciones?
Anchura del TAG
El ancho del TAG tiene que ser suficiente para identificar a los elementos que depositan datos sobre el CDB, más el caso de marca vacía (TAG = 0). Necesitamos conocer el número total de Estaciones de Reserva (ER) más el número de Load Buffers.
Tamaño de la Ventana de Instrucciones
La ventana de instrucciones es el número de elementos capaces de alojar una instrucción pendiente de ejecución. Necesitamos los mismos datos que antes (Número de ER + Número de Load Buffers), más el número de Store Buffers.
- Cuando una instrucción aritmética en punto flotante realiza su fase “write”, ¿qué debe suceder para que esta instrucción no actualice el valor de su registro destino? Acompaña la explicación con un pequeño ejemplo.
Para que la instrucción no actualice el valor de su registro destino, debe suceder que el tag del registro destino no contenga el identificador de la Estación de Reserva en donde se aloja la instrucción aritmética.
Ejemplo: Si la instrucción ADDD F6, F4, F6
está en $ER_1$, y antes de que $ER_1$ termine, se emite otra instrucción SUBD F6, F8, F10
que se aloja en $ER_2$. El registro $F6$ ahora tiene el tag $ER_2$. Cuando $ER_1$ termina y escribe su resultado en el CDB con el tag $ER_1$, el registro $F6$ ignora este resultado porque su tag actual es $ER_2$.
Predicción de Saltos
Predicción de Salto con Predictor de Dos Niveles (3,2)
Supongamos un programa, que incluye una única instrucción de salto que siempre se toma y que se ejecuta en un procesador dotado de un predictor de saltos de dos niveles (3,2). ¿A partir de qué número de ejecución del salto el predictor acertará en la predicción? El estado inicial del predictor es todo a cero. Explicar cómo se obtiene la respuesta.
Un predictor (3,2) utiliza un historial global de 3 bits y contadores saturados de 2 bits. El estado inicial es 00 (No Tomado, Débilmente).
Dado que el salto siempre se toma (T), la secuencia de estados del contador de 2 bits (PHT) será:
- Ejecución 1 (T): Estado 00 → 01 (No Tomado, Débilmente). Predicción: Falla.
- Ejecución 2 (T): Estado 01 → 10 (Tomado, Débilmente). Predicción: Falla.
- Ejecución 3 (T): Estado 10 → 11 (Tomado, Fuertemente). Predicción: Acierta.
El predictor acertará en la predicción a partir de la tercera ejecución del salto, ya que en ese momento el contador alcanza el estado 10, que predice ‘Tomado’.
Funcionamiento y Diagrama de Estados de un Predictor Bimodal (Dos Bits)
Explica brevemente en qué consiste un predictor de dos bits (bimodal) y dibuja su diagrama de estados. ¿Cómo se hace la predicción de un salto? ¿Cómo se actualiza el estado del predictor cuando se conoce el comportamiento del salto?
Descripción del Predictor Bimodal
La predicción de cada salto se hace mediante un contador saturado de 2 bits. Dada la dirección de una instrucción, se usa una parte de los bits menos significativos para acceder al contador correspondiente en la Tabla de Historial de Patrones (PHT).
Mecanismo de Predicción
El bit más significativo del contador seleccionado determina la predicción:
- Si el bit es 1 (estados 10 o 11): Predicción = Tomado (T).
- Si el bit es 0 (estados 00 o 01): Predicción = No Tomado (NT).
Actualización del Estado
Cuando se ha ejecutado el salto, el contador usado en la predicción se actualiza:
- Se incrementa en 1 su valor si el salto se ha tomado (T).
- Se decrementa en 1 si no se ha tomado (NT).
Diagrama de Estados (Descripción)
El diagrama de estados es un autómata finito con cuatro estados:
- 00 (NT, Fuertemente)
- 01 (NT, Débilmente)
- 10 (T, Débilmente)
- 11 (T, Fuertemente)
Las transiciones se mueven hacia 11 si el salto se toma, y hacia 00 si no se toma, saturándose en los extremos 00 y 11.
Concepto de Predictor Combinado
Un predictor combinado mezcla varios predictores (por ejemplo, un predictor bimodal y un predictor de historial global) y añade un mecanismo de selección del predictor.
El sistema elige, en cada caso, el predictor que haya dado mejores resultados hasta el momento.
Para combinar dos predictores, $P_1$ y $P_2$, se utiliza una tabla de contadores saturados de dos bits indexada por la dirección de la instrucción de salto.
Arquitecturas Vectoriales
Encadenamiento de Operaciones Vectoriales (Vector Chaining)
En un computador vectorial, explica brevemente en qué consiste el encadenamiento de operaciones vectoriales. Para una secuencia de operaciones vectoriales de la forma:
LV V1, R1
MULVV.D V3, V1, V2
ADDVV.D V5, V3, V4
Dibuja el diagrama de tiempo que muestra su ejecución en forma encadenada y explica el significado de cada uno de los tramos o intervalos que aparecen en el mismo.
Definición de Encadenamiento
Consiste en conectar directamente la salida de una Unidad Funcional (UF) segmentada que está produciendo un resultado (que se va a almacenar en un registro vectorial) a la entrada de otra UF que necesita ese resultado como operando. De esta forma, en el momento en que la primera UF produce el primer resultado, la segunda UF ya puede comenzar a operar.
Diagrama de Tiempo (Descripción)
El diagrama de tiempo muestra la ejecución solapada de las tres instrucciones:
LV V1, R1 (Carga) → MULVV.D V3, V1, V2 (Multiplicación) → ADDVV.D V5, V3, V4 (Suma)
Donde:
- $L_L$: Latencia de la unidad de Load (Carga).
- $L_M$: Latencia (nº etapas) del multiplicador.
- $L_A$: Latencia (nº etapas) del sumador.
- $N_{elem}$: Número de elementos que se procesan (valor del VLR).
La multiplicación comienza $L_L$ ciclos después de que comience la carga. La suma comienza $L_M$ ciclos después de que comience la multiplicación. El tiempo total de ejecución es aproximadamente $L_L + L_M + L_A + N_{elem}$.
Conflictos de Acceso a Memoria en Arquitecturas Vectoriales (VMIPS)
Supongamos un computador vectorial similar al VMIPS, cuya memoria está organizada en 16 bancos y cuyo tiempo de acceso a memoria es 6 ciclos de reloj. En esa memoria está almacenada por filas una matriz, A, de 40 filas por 50 columnas. Explica razonadamente si se producirán conflictos de acceso a memoria al cargar una columna de A en un registro vectorial mediante una instrucción de tipo LVWS.
Para cargar una columna, el stride (paso entre elementos consecutivos) es igual al número de columnas de la matriz, es decir, 50.
La condición para que no haya acceso sin conflicto es:
$$\frac{m.c.m (\text{nº bancos}, \text{stride})}{\text{stride}} \ge T_{\text{acceso a memoria}}$$
Cálculos:
- Número de bancos = 16
- Stride = 50
- $T_{\text{acceso a memoria}}$ = 6 ciclos
- $m.c.m (16, 50) = 400$
Verificación de la condición:
$$\frac{400}{50} = 8$$
Como $8$ es mayor que $6$, no se producirán conflictos de acceso a memoria.
Parámetros MVL y VLR en la Arquitectura VMIPS
En la arquitectura del VMIPS indica cuál es el significado del parámetro MVL y cuál es la función del registro VLR.
- MVL (Maximum Vector Length): Es un parámetro que indica el tamaño máximo de los registros vectoriales. Su valor es fijo y no puede cambiar.
- VLR (Vector Length Register): Indica el número de componentes sobre los que actúa la operación vectorial en curso. El valor almacenado en este registro es variable.
Nota: Si una operación vectorial se realiza sobre $n$ elementos, donde $n > MVL$ (y no es múltiplo de $MVL$), la operación se descompone en varias suboperaciones: una operación sobre $n \pmod{MVL}$ elementos (donde $VLR = n \pmod{MVL} \neq MVL$) y $n/MVL$ operaciones de longitud $MVL$ (en las que $VLR = MVL$).
Multithreading (MT)
Multithreading de Grano Fino (Fine-Grained MT)
Describe brevemente en qué consiste y cuáles son las principales características del multithreading de grano fino. Explica sus principales ventajas y desventajas. Cita un ejemplo de procesador que lo implemente.
Características
Consiste en conmutar entre threads en cada instrucción, entrelazando la ejecución de los diferentes threads. Generalmente se realiza en modo round-robin, saltándose los threads bloqueados. La CPU debe ser capaz de conmutar de thread cada ciclo.
Ventajas
- Puede ocultar stalls (paradas) de alta y baja latencia.
- Cuando un thread está bloqueado, los otros usan los recursos.
Desventajas
- Retarda la ejecución de cada thread individual, ya que un thread sin stall es retrasado por el reparto de recursos (ciclos) entre otros threads.
Ejemplo: Niagara y Niagara 2 (SUN).
Multithreading de Grano Grueso (Coarse-Grained MT)
Explica brevemente en qué consiste el multithreading de grano grueso y cuáles son sus principales ventajas y desventajas. Cita algún ejemplo de un procesador que lo implemente.
Características
Conmuta entre threads solo en caso de stalls largos, como fallos de caché L2.
Ventajas
- No necesita conmutación entre threads muy rápida.
- No retarda cada thread, ya que la conmutación solo se produce cuando un thread no puede avanzar.
Desventajas
- No elimina pérdidas por stalls cortos.
- La conmutación es costosa en ciclos.
Ejemplo: Itanium o SPARC64 VI.
Diferencia Fundamental del Multithreading Simultáneo (SMT)
Explica brevemente cuál es la diferencia fundamental entre multithreading simultáneo y los otros tipos de multithreading que hemos estudiado.
En MT de grano fino o de grano grueso, en cada ciclo solamente se pueden lanzar a ejecución instrucciones pertenecientes al mismo thread. Por el contrario, en MT simultáneo (SMT), en un mismo ciclo se puede lanzar a ejecución un grupo de instrucciones pertenecientes a diferentes threads, aprovechando la capacidad superescalar del procesador.
Implementación de Multithreading en IBM Power 5
Hemos estudiado el Power 5 de IBM como un ejemplo de arquitectura que implementa multithreading.
- ¿Qué tipo de multithreading implementa? ¿Por qué?
Implementa Multithreading Simultáneo (SMT) porque en cada ciclo de reloj pueden lanzarse a ejecución instrucciones pertenecientes a uno o a los dos threads que puede gestionar.
- Muchos de los recursos de la arquitectura son compartidos por los 2 threads que puede soportar. Entre ellos se encuentran muchos recursos de la fase fetch: caché de instrucciones, BTAC, tablas de historia de saltos… Sin embargo, cada thread tiene su propia pila de direcciones de retorno. ¿Puedes razonar brevemente sobre las razones para esta decisión?
La BTAC o las tablas de historia de saltos son accedidas mediante una función de hash. Si las tablas son suficientemente grandes, el número de sinónimos se mantendrá reducido, por lo que no importa si las direcciones con las que se accede pertenecen a un thread o al otro (es decir, si las direcciones son generadas por un PC o por el otro).
Sin embargo, las pilas de retornos se acceden según el orden de llamadas y retornos (última llamada, primer retorno) de cada thread. Si se usara una sola pila, las direcciones de retornos de un thread se mezclarían con las del otro y el número de direcciones de retorno mal predichas sería elevado. Estando separadas, lo que implica un coste moderado, se acierta casi siempre, excepto si el nivel de anidamiento de las llamadas llega a superar al número de entradas de la pila de retornos.
Otros Conceptos de Arquitectura
Traducción Dinámica de Instrucciones
Algunos procesadores superescalares fuera de orden implementan “traducción dinámica de instrucciones”. Explica brevemente en qué consiste este concepto, y en qué etapa del pipeline se realiza.
La traducción dinámica de instrucciones consiste en transformar un flujo de instrucciones (típicamente con un formato poco adecuado para su ejecución en un procesador segmentado, como longitud de instrucción variable o mezcla de operandos en registros y memoria) en otra secuencia de microinstrucciones equivalente, pero que tienen un formato más cercano a instrucciones tipo RISC.
Esta traducción se hace dinámicamente en la etapa de decodificación, conforme las instrucciones del repertorio original son entregadas por la etapa fetch.
Impacto de la Mejora de Hardware en el Valor SPEC FP2006
Dado un computador C, tal que el valor de SPEC FP2006 de C es 30, introducimos una mejora en su hardware de PF, de tal manera que tras la mejora ejecuta las operaciones en punto flotante en la mitad de tiempo. Explica razonadamente si se puede deducir que el valor de SPEC FP2006 del computador C mejorado será 60.
No se puede deducir que el valor de SPEC_2006 del computador C mejorado será 60. Para poderlo afirmar, la media geométrica de las ratios tendría que ser el doble, lo que sería cierto si todos los programas patrón se ejecutaran en la mitad de tiempo. Sin embargo, aunque las operaciones en PF se ejecuten en la mitad de tiempo, eso no significa que los programas patrón se ejecuten en la mitad de tiempo, dado que los programas patrón no pueden contener exclusivamente operaciones de PF, sino que también contienen necesariamente operaciones enteras cuyo tiempo de ejecución no cambia.
Cálculo de Coste de Obleas (Wafer Cost)
Cálculo basado en rendimiento de obleas (Die Yield):
En la oblea de la derecha:
$$Coste_{wafer} = Coste_{Die} \times Dies_{por\_wafer} \times Die_{yield}$$
$$Coste_{wafer} = 100 \times 9 \times (5/9) = 500 €$$
En la oblea de la izquierda:
$$Coste_{Die} = \frac{Coste_{wafer}}{Dies_{por\_wafer} \times Die_{yield}}$$
$$Coste_{Die} = \frac{500}{4 \times 1/4} = 500 €$$