Facultad de Informática, UPV Dpto. de Arquitectura y Tecnología de Computadores

Arquitecturas Paralelas Examen

19 – enero – 2009

Apellidos:

Grupo:

Nombre:

Firma:

1

2

3

4

5

6

7

8

9

10

11

12

13

El examen consta de dos partes (t. total: 2:45 h + 1 h). La primera parte es obligatoria (26 puntos en total) y la asignatura se aprueba sacando al menos 13 puntos; la nota máxima de esa parte es un 8. La segunda parte es optativa, y se evalúa en 2,5 puntos, pero sólo si en la primera parte se obtienen al menos 17 de los 26 puntos.

1ª parte

11 ejercicios — 2:45 h — 26 puntos

1. (3 p.) Un computador vectorial tiene las siguientes características: encadenamiento de instrucciones; 2 buses para acceder a memoria; registros vectoriales de 256 elementos; frecuencia de reloj de 666 MHz. a. Completa la siguiente tabla indicando los principales momentos (ciclos) en la ejecución del programa vectorial indicado. No tengas en cuenta los conflictos en el acceso a los módulos de memoria. El esquema de segmentación de las instrucciones es: [ B/D - L - AM - M (6 ciclos) - E ] para las instrucciones de memoria, y [ B/D - L - A (+, 2 ciclos; *, 3 ciclos) - E ] para la suma y el producto. t. inicio

LV

V1,A(R1)

SV

B(R1),V1

MULV

V2,V1,V1

lat. UF.

dato 1

dato N

ADDVI V3,V2,#1.0 SV

A(R1),V3

b.

Sin rehacer los cálculos, ¿de qué orden sería el tiempo de ejecución si sólo hubiera un bus? ¿Y si hubiera tres buses pero las instrucciones no se encadenaran? Justifica tus respuestas.

c.

Los vectores A y B son de 100 elementos. ¿Qué velocidad de cálculo (en MF/s) se consigue al ejecutar el programa anterior? ¿Qué fracción (%) representa esa velocidad del máximo teórico posible si los vectores fueran muy grandes?

2. (3 p.) Dibuja el grafo de dependencias de este bucle, y, si es posible, escribe el código vectorial completo para el mismo. k = 4 do i = 1, 100 (1) A(i) = A(i) + 3 (2) B(i) = A(i+1) + A(i) (3) C(i) = A(i-1)+ B(k) k = k + 2 enddo

3. (3 p.) Una máquina SMP de 4 procesadores mantiene la coherencia de los datos mediante un snoopy y un protocolo de invalidación tipo MESI. En un momento dado de la ejecución de una aplicación paralela de memoria compartida, los procesadores acceden a la variable A, cuyo valor inicial es 20 y que no se encuentra en ninguna de las caches del sistema, en el siguiente orden: P1: LD R1,A; a.

P2: ST A,#5;

P0: LD R2,A;

Para cada una de las cuatro referencias, indica cómo se resuelve, las señales de control y el tráfico de datos que se genera, y el valor de A y el estado final del bloque de datos que la contiene en las cuatro caches y en memoria principal. MC0 inicio

b.

P3: LD R1,A;

MC1

MC2

MC3

MP A=20

Señ. Control

Tráf. datos

Sin rehacer el ejercicio, indica qué cambios habría en relación con el caso anterior si el protocolo de coherencia fuera de tipo MOESI.

4. (1 p.) En una máquina SMP de 16 procesadores se dispone de instrucciones Test&Set para operaciones de sincronización. Una determinada aplicación requiere utilizar una sección crítica que sabemos se va a ejecutar frecuentemente. Escribe código para las funciones que protegen la sección crítica (lock y unlock) de la manera más eficiente posible. Explica las ventajas para este caso del código que propones.

5. (3 p.) Se va a ejecutar este programa entre los 8 procesadores de una máquina SMP: suma = 0; for (i=0; i