Preguntas teoría

AOC 2021 FEBRERO

AOC 2021 JUNIO

AOC JULIO 2021

AOC 2022 FEBRERO

AOC 2022 JUNIO

AOC 2022 JULIO

Problemas

AOC 2021 FEBRERO

9. (2 puntos) Se dispone de un procesador con 4 núcleos, donde cada núcleo es un procesador superescalar con ejecución especulativa según el algoritmo de Tomasulo, y tiene una unidad vectorial por núcleo de 128 bits. Se pide lo siguiente: a) (0,5 puntos) Suponiendo que tenemos una aplicación que utiliza valores en doble precisión, y conseguimos una paralelización y vectorización perfecta del 90 % del tiempo de ejecución del programa secuencial, ¿cuál es la aceleración que obtenemos en la ejecución paralela y vectorizada comparada con la ejecución de la versión secuencial en un único núcleo sin vectorizar? ¿Cuál sería la máxima aceleración posible de esa aplicación en el caso ideal de tener un número infinito de núcleos y unidades vectoriales de tamaño ilimitado? b) (1 punto) Cada núcleo superescalar del procesador puede buscar, emitir y confirmar dos (2) instrucciones por ciclo, y suponemos que tiene estaciones de reserva y un buffer de reordenación (ROB) de tamaño ilimitado, y que dispone de las siguientes unidades de ejecución en coma flotante sin segmentar: 2 UF de sumas/restas (latencia de 2 ciclos), 1 UF de multiplicaciones (latencia 5 ciclos), y 1 UF de divisiones (latencia 40 ciclos). En uno de los núcleos queremos ejecutar las instrucciones del siguiente código:
   Instrucción F D I X W C Comentario addd f3, f1, f2 (1) addd f2, f3, f2 (2) multd f4, f3, f2 (3) divd f5, f2, f1 (4) subd f2, f3, f1 (5) c) (0,5 puntos) Muestra la estructura del ROB (con los campos instrucción, estado, destino y valor) al acabar el ciclo anterior al de la confirmación de la primera instrucción.
10. (2 puntos) Tenemos un computador con dos procesadores que sigue el modelo de memoria de consistencia secuencial. Cada procesador tiene una caché privada asociativa de 4 vías, las cuales están conectadas mediante un bus a una memoria compartida. La coherencia entre las cachés se mantiene mediante un protocolo MSI de fisgoneo como el visto en clase que no optimiza el patrón migratorio y que puede generar las transacciones BusRd, BusRdX y BusUpgr. En este computador se ejecuta un programa con dos hilos con las siguientes instrucciones:

Hilo A Hilo B A1: r1 = y B1: y = 3 A2: x = r1 + 2 B2: r2 = x A3: y = r1 + 5 B3: z = r2 + 1 Donde A1, A2, A3, B1, B2 y B3 son etiquetas; x, y y z son variables almacenadas en memoria inicializadas a 0; y r1 y r2 son registros. a) (1 punto) Indica, justificando la respuesta, cuáles son los posibles resultados del programa (valores finales de las variables de memoria). b) (1 punto) Suponiendo en este apartado que se ejecutan primero todas las instrucciones del primer hilo y después todas las del segundo hilo, que las cachés están inicialmente vacías y que cada variable se almacena en un bloque de memoria distinto, completa la siguiente tabla indicando las transacciones que se producen en el bus, el estado de cada bloque en la caché antes y después de la transacción y quién proporciona el bloque de datos.

AOC JUNIO 2021

9. (1,5 puntos) Se están planificando una serie de mejoras en el diseño de un procesador superescalar de 2 vías, con un IPC promedio de 1,4 que cuenta con un cauce de 10 etapas y que opera a una frecuencia de 2 GHz. La aplicación de prueba que usaremos para evaluar su rendimiento consta de 109 instrucciones con la siguiente distribución: 25 % instrucciones de saltos condicionales; 30 % de operaciones de memoria (de las cuales el 70 % son de tipo entero y el resto de punto flotante); 30 % de operaciones aritmético-lógicas de tipo entero; 10 % de operaciones aritmético-lógicas en punto flotante; y 5 % de saltos incondicionales. a) (0,5 puntos) La primera mejora que queremos estudiar es relativa al predictor de saltos. El predictor de saltos original tenía un acierto del 90 % mientras que el nuevo predictor diseñado tiene un acierto del 98 %, lo cual nos proporciona una ganancia en el tiempo total de ejecución de la aplicación (speedup) del 3 %. Se pide el tiempo de ejecución de la aplicación (en segs.) en el procesador original y en el procesador con la predicción mejorada de los saltos. b) (0,5 puntos) La segunda mejora, que se aplica sobre el procesador original sin la primera mejora, introduce el uso de cachés no bloqueantes en el procesador. Aunque la tasa de fallos no cambia, al permitir un mayor paralelismo entre los accesos a caché se consigue reducir el CPI medio de todas las operaciones de memoria en un 40 %, sin afectar al CPI medio del resto de instrucciones. Sabiendo que el CPI medio original de todas las operaciones de memoria era de 2, se pide el nuevo tiempo de ejecución de la aplicación (en segs.) así como la ganancia en tiempo de ejecución. c) (0,5 puntos) Calcular los MFLOPS del procesador original así como los de las dos mejoras presentadas.
10. (2,5 puntos) En este problema disponemos de un procesador CMP de 4 núcleos (quad-core). La coherencia del CMP se mantiene según el protocolo MSI, al que se le han incorporado las optimizaciones de Flush (envía el bloque a otra caché sin actualizar memoria) y Flush’ (envía el bloque a la memoria y a la caché peticionaria si la hay). Este protocolo no soporta mensajes BusUpg. a) (1,5 puntos) Considera la siguiente secuencia de operaciones sobre dos datos, X e Y, que pertenecen a bloques de caché diferentes: r1X r3Y r2X Rz3Y w2X w2Y w1Y r1X Rz1Y r2X w4Y, donde r indica una lectura, w una escritura, Rz el reemplazo del bloque de cache, y 1, 2, 3 ó 4 el núcleo que realiza la operación. Las operaciones no se solapan y se completan en el orden indicado. Indica, para cada una de las operaciones anteriores, la transacción o transacciones de bus que se generan, el vector de estados para cada bloque de datos tras realizar cada operación, y quién proporciona el bloque de datos en caso de ser necesario (inicialmente las caches están vacías), rellenando la siguiente tabla:
    Operaciones Trans. bus Vector estados X Vector estados Y Dato proporc. por ... b) (1 punto) Cuando ejecuta un aplicación secuencial de coma flotante este CMP obtiene un CPI de 0,56 (usando solo un núcleo). Para poder ejecutar la versión paralela se requiere usar un cerrojo y una barrera.

1. (0,25 puntos) Si las operaciones de sincronización no introdujeran ninguna sobrecarga, ¿cuál sería el valor del CPI obtenido usando los 4 núcleos?
2. (0,75 puntos) Sabiendo que los cerrojos representan un 2 % de las instrucciones en el código paralelo, y las barreras un 2 por mil de las instrucciones, y que los cerrojos tardan en ejecutarse 10 ciclos, ¿cuál sería el límite de la latencia que nos pueden introducir las barreras en el CPI para que la ejecución en cuatro núcleos no sea peor que en uno sólo?

AOC JULIO 2021

9. (2 puntos) Para la siguiente secuencia de instrucciones:

a) (1,25 puntos) Muestre un cronograma de la ejecución de las primeras dos iteraciones en un procesador superescalar de 2 vías como el propuesto en clase (F+D en orden, I+X+W fuera de orden, C en orden) que utiliza un ROB. Se dispone de las siguientes unidades funcionales: 2 unidades de carga/almacenamiento con 2 ciclos de latencia en los aciertos de caché, 2 ALUs enteras de latencia 1, un sumador en coma flotante de latencia 3, un divisor en coma flotante de latencia 5, y una unidad de saltos que resuelve los saltos en la etapa de ejecución. Todas las unidades funcionales están segmentadas. El predictor de saltos es estático y predice que no se va a saltar en los saltos hacia adelante, y que sí se va a saltar en los saltos hacia atrás. Suponga para este problema un tamaño ilimitado del ROB, un número ilimitado de estaciones de reserva de todos los tipos y un número ilimitado de entradas en las colas de cargas y almacenamientos. Suponga también que todos los accesos a memoria aciertan en la caché. El cronograma debe indicar la etapa en la que se encuentra cada instrucción en cada ciclo y se debe indicar por qué se producen las detenciones. b) (0,75 puntos) Calcule cuántos ciclos tardaría en ejecutarse una iteración normal, y los ciclos totales de ejecución del programa completo. Para el cálculo de los ciclos de una iteración normal, considere la diferencia entre el ciclo del commit de la última instrucción de la segunda iteración y el ciclo del commit de la última instrucción de la primera iteración.

Solución: a) El cronograma quedaría como sigue. Se muestran 3 iteraciones, aunque se pedían solo 2 en el enunciado.

b) Para el cálculo de los ciclos que tarda en ejecutarse una iteración normal, mirando el cronograma, vemos que la primera iteración realiza el commit de su última instrucción en el ciclo 17, y que a partir de ese momento se realiza el commit de la última instrucción de una iteración cada 5 ciclos, por lo que una iteración normal tarda 5 ciclos. El programa ejecutará 1024 iteraciones (12288 / 12). Para el cálculo de los ciclos totales de ejecución del programa completo, tendremos 1023 iteraciones más los ciclos de la primera iteración (17 ciclos), por tanto, en total se tardarán: Tiempoprograma-completo = 17 + 1023 × 5 = 5132 ciclos.

10. (2 puntos) Tenemos un CMP con 4 núcleos que utiliza un protocolo de coherencia snoopy basado en invalidación con estados MSI y política de post-escritura (writeback). El tamaño de bloque es de 32 bytes. El protocolo genera los mensajes BusRd, BusRdX en el bus, acepta peticiones PrRd y PrWr por parte de los núcleos y los controladores de caché son capaces de realizar las acciones Flush_$M y Flush$ (enviar el dato a caché y memoria, o solo a caché). a) (0,5 puntos) Complete la siguiente tabla mostrando las transiciones de estados de las cachés, indicando para cada transición el estado destino, los mensajes que se envían y las acciones que se realizan.

b) (1,5 puntos) En este CMP se producen los accesos a memoria que se muestran en la siguiente tabla. Dichos accesos corresponden a bloques diferentes de caché. Los accesos se producen secuencialmente, de forma que uno no empieza hasta que ha acabado completamente el anterior. Complete la tabla siguiente, que muestra para cada acceso si se trata de un fallo o acierto en las cachés privadas, el estado en las cachés del bloque antes y después del acceso y los mensajes de red y acciones que se generarían para resolver el acceso. Suponga que inicialmente las cachés se encuentran vacías.

Solución: a) Tabla de transiciones para las cachés:

b) La tabla solicitada quedaría como sigue: