1

Estructura de Computadores Problema Un computador con instrucciones de longitud fija de 32 bits dispone de 256 registros generales y los siguientes grupos de instrucciones:

• Grupo 1: 13 instrucciones que hacen referencia a 3 operandos, 2 en registros y 1 desplazamiento de 12 bits. • Grupo 2: 40 instrucciones que hacen referencia a 3 operandos en registros • Grupo 3: 7 instrucciones que hacen referencia a 2 operandos, 1 en registro y 1 desplazamiento de 16 bits • Grupo 4: 16 instrucciones sin operandos A) Determina el formato de cada grupo de instrucciones B) Dibuja el diseño del decodificador completo C) Calcula el tiempo de decodificación de instrucciones si cada decodificador utilizado en el diseño tienes dos niveles de puertas lógicas y son 2 ns el tiempo de retardo de cada puerta.

Solución: A)

B)

C) Retardo = 3 mux * 2 nivels * 2 ns =12 ns.

CO (4 bits) R1 (8 bits) R2 (8 bits) D (12 bits)

1 1 0 1 CO (4 bits) R1 (8 bits) R2 (8 bits) R3 (8 bits)

1 1 1 0 CO (4 bits) R1 (8 bits) R2 (8 bits) R3 (8 bits)

1 1 1 1 CO (4 bits) R1 (8 bits) R2 (8 bits) R3 (8 bits)

1 1 1 1 CO (4 bits) R1 (8 bits) D (16 bits)

1 1 1 1 1 1 1 1 CO (4 bits)

0 0 0 0………..1 1 0 0

0 0 0 0………..1 1 1 1

0 0 0 0………..1 1 1 1

0 0 0 0………..0 1 1 1

1 0 0 0………..1 1 1 0

13 instrucciones Grupo 1

16 instrucciones Grupo 2

16 instrucciones Grupo 2

8 instrucciones Grupo 2

7 instrucciones Grupo 3

16 instrucciones Grupo 40 0 0 0 ………..1 1 1 1

2

Problema 1) Sabiendo que la frecuencia de ejecución de instrucciones en una máquina es la que aparece en la siguiente tabla:

Tipo de instrucciones Frecuencia de ejecución ADD SUB MUL DIV STA LDA JMP

0.42 0.26 0.21 0.04 0.04 0.02 0.01

Define un CO variable que minimice el tráfico de información con la memoria en las lecturas de las instrucciones. ¿Cuántos bits dejarán de transferirse entre CPU y Memoria con el CO de longitud variable frente a un CO de longitud fija en un programa que ejecuta 1.000 instrucciones? Solución:

Código de Huffman Tipo de instrucciones Frecuencia de ejecución

0

10

110

1110

11110

111110

111111

ADD

SUB

MUL

DIV

STA

LDA

JMP

0.42

0.26

0.21

0.04

0.04

0.02

0.01

0.03

0.07

0.11

0.32

0.58

1.00

10

0

0

0

0

1

1

1

1

1

Lmedia (v) =1 x 0.42 + 2 x 0.26 + 3 x 0.21 + 4 x 0.04 + 5 x 0.04 + 6 x (0.02+0.01) = 2.11 bitsL (f) = 3Cv = 1000 x 2.11 = 2110Cf = 1000 x 3 = 3000Cf – Cv = 890 bits

3

Problema Codificar con instrucciones SIMD del Pentium (MMX) el siguiente segmento de programa:

for i = 0 to 3 if a[i] = p then s[i] = (a[i] - c[i])/2 else if a[i] = q then s[i] = 4*c[i] else s[i] = s[i]*c[i]

Solución:

Desplazamiento << 2

7

a)

AND

= = = =

x x x x

mm0

a3 a2 a1 a0

mm1

p p p p

mm2

q q q q

mm2 1…1 1.…1 0….0 0...0

mm1

0…0 0.…0 1….1 0...0

mm4 c’’’3 c’’’2 c’’’1 c’’’0

mm3 c3 c2 c1 c0

mm4

s3 s2 s1 s0 - - - -

Desplazamiento >> 1 mm0

c’3 c’2 c’1 c’0

mm3

c3 c2 c1 c0

mm0

a3 a2 a1 a0

mm3 c’’3 c’’2 c’’1 c’’0

mm3 c3 c2 c1 c0

mm3 c’’3 c’’2 0….0 0…0 mm0

0…0 0.…0 c’1 0...0 mm1

1…1 1.…1 1….1 0...0

mm1 0…0 0.…0 0….0 c’’’0

mm0 c’’3 c’’2 c’1 0…0

mm0 c’’3 c’’2 c’1 c’’’0

= = = =

AND

OR

NOT AND

OR

OR

11

10

9

8

1 2

3 4

5

6

b) c)

NOT AND

Código (0) MOVQ mm0, A MOVQ mm1, p MOVQ mm2, q MOVQ mm3, C MOVQ mm4, S (1) PCMPEQW mm1, mm0 (2) PCMPEQW mm2, mm0 (2’) PANDN mm2, mm1 (3) PSUBW mm0, mm3 PSRLW mm0, 1

(4) PMULLW mm4, mm3 (5) PSLLW mm3, 2 (6) PAND mm0, mm1 (7) PAND mm3, mm2 (8) POR mm1, mm2 (9) PANDN mm1, mm4 (10) POR mm0, mm3 (11) POR mm0, mm1 (12) MOVQ S, mm0

4

Problema Un computador tiene un CPI de 5 para las instrucciones aritmético-lógicas, un CPI de 7 para las instrucciones de carga-almacenamiento y un CPI de 15 para las instrucciones aritméticas de tipo trigonométrico. Cierto benchmark tiene un 30% de operaciones aritmético-lógicas, un 60% de carga-almacenamiento y el resto de operaciones aritméticas de tipo trigonométrico. Con el propósito de mejorar las prestaciones del computador, se manejan 2 alternativas de diseño:

a) Modificar la organización para aumentar la frecuencia de reloj en un 30% a costa de aumentar a 9 el CPI de las instrucciones de carga-almacenamiento

b) Incluir un HW específico para las operaciones trigonométricas que reduce el CPI de estas instrucciones a 7.

¿Qué opción es mejor? Justifica numéricamente la respuesta

Solución:

5*0,3+7*0,6+15*0,1 7,2

5*0,3 9*0,6 15*0,1 8,4

* * *7,2*

* * *8, 4*1,3

7,2 7,2 1,1148,4 /1,3 6,46

5*0,3 7*0,6 7*0,1 6,4

7,2

orig

A

orig orig orig orig

origA A A

origA

A

B

B

CPI = =

CPI = + + =

T N CPI TC N TC

TCT N CPI TC N

TSpeedUp = =

T

CPI = + + =

SpeedUp =

= =

= =

= =

1,1256,4

=

Luego es mejor la alternativa B porque consigue mayor ganancia de velocidad frente al diseño actual

5

Problema

Un procesador que opera a 500 MHz con un CPI = 4 dispone de un sistema de interrupciones con un tiempo de reconocimiento de interrupción de 100 ns. En cada interrupción se transmiten 8 bytes. ¿Cuál es el número máximo de instrucciones que puede ejecutar la rutina de servicio de interrupción si queremos que la capacidad de entrada de datos (ancho de banda) a través del sistema de interrupciones sea de 20 MBytes/segundo?

Solución: 500 MHz Tc = 2 ns.

Tiempo total de una interrupción = 8 bytes /interrupción / 20* 106 bytes/segundo = 400 ns./ interrupción = 100 + NI_RT * 4 * 2 = 100 + NI_RT * 8

NI_RT = (400 – 100)/8 = 37,5 NI_RT = 37 instrucciones

6

Problema Un procesador con CPI = 5 ciclos/instrucción y tiempo de ciclo Tc = 2 ns dispone de un sistema de E/S con interrupciones y DMA.

a) Calcula el número máximo de instrucciones que deberá tener la rutina de servicio de interrupción cuando sólo se conecta una tarjeta de adquisición de datos que opera a una velocidad de 10 MBytes/segundo, sabiendo que el tiempo de reconocimiento de una interrupción es de 100 ns. y que se transmiten 8 bytes en cada interrupción.

b) Calcula el ancho de banda mínimo que debe proporcionar el DMA para poder conectar un disco magnético de 256 sectores/pista y 2048 bytes/sector que gira a 9.600 revoluciones por minuto.

c) ¿Se podría conectar el disco a través de DMA por robo de ciclo si en cada operación de DMA se transfieren 8 bytes?

d) Calcula el número máximo de instrucciones que debería tener la rutina de servicio de interrupción si el procesador opera simultáneamente con la tarjeta de adquisición de datos conectada por interrupciones y con el disco magnético conectado por DMA (robo de ciclo).

Solución:

a) 100 + Nºinst(RT) * 5 ciclos/inst. * 2 ns./ciclo < (8 Bytes/inst. / 107 Bytes/seg) 109ns = 800 ns. Nºinst(RT) < (800 – 100)/10 = 700/10 = 70 instrucciones

b) 9.600 r.p.m = 160 r.p.s. Tlectura_pista = 1/160 = 6.250 *10-6 segundos Capacidad_pista = 28 x 211 = 219 bytes/pista ABmin = 219 bytes/pista / 6.250 *10-6 segundos/pista = 83 MB/s.

c) AB(dma)= 8B/(6*2)ns = 8B/12*10-9 s=0,66*109 = 660*106 = 660 MB/s > 83 MB/s SI se podría conectar

d) Las 70 instrucciones calculadas en el apartado a) corresponden a 70*5 = 350 ciclos de CPU La rutina de servicio debe durar como máximo 350 ciclos.

Cuando opera simultáneamente el DMA(robo de ciclo) cada instrucción (5 ciclos) dedica 1 ciclo a transferencia DMA Nºins(rt+DMA) = 350/6 = 58 instrucciones

7

Problema Sea un procesador segmentado de cinco etapas. Ejecutamos en este procesador una aplicación con las siguientes características:

El 18% de las veces las instrucciones Ii+1 tienen una dependencia de LDE con las instrucciones Ii. El 29 %de éstas corresponden a instrucciones de load.

El 6% de las veces las instrucciones Ii+2 tienen dependencias de LDE con la instrucción Ii El 25% de las instrucciones son de bifurcación condicional, de las cuales se toman el 35%

Calcula: a) Los CPIs respectivos para las siguientes características del procesador:

1) Procesador sin técnicas para reducir o eliminar paradas. Los saltos se resuelven en ejecución. Se puede escribir y leer el registro en el mismo ciclo de reloj.

2) Procesador con cortocircuito (forwarding). Los saltos se resuelven en decodificación. b) La ganacia de velocidad (speedup) del segundo caso frente al primero.

Solución: a.1) Vamos a ver las paradas por dependencias que ocurren en cada caso:

Paradas por dependencia entre Ii+1 e Ii

Ii F D E M W Ii+1 F DP DP D E M W

El número de paradas es 2. En este primer caso los load y el resto de las instrucciones con dependencia tienen el mismo número de paradas puesto que en todos los casos se espera hasta la etapa de escritura para poder leer el nuevo valor.

Paradas por dependencias entre Ii+2 e Ii

Ii F D E M W Ii+1 F D E M W Ii+2 F DP D E M W W

En este segundo caso se produce un ciclo de parada entre Ii e Ii+2

Paradas por bifurcación condicional: 3 ciclos de parada

BC F D E M W Ii+1 FP FP FP F D E M W

Por lo tanto el CPI de este procesador será:

𝐶𝐶𝐶𝐶𝐶𝐶 = 𝐶𝐶𝐶𝐶𝐶𝐶𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 + � 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑖𝑖 𝑥𝑥 𝑝𝑝𝑓𝑓𝑓𝑓𝑓𝑓𝑝𝑝𝑓𝑓𝑝𝑝𝑓𝑓𝑓𝑓𝑓𝑓ó𝑓𝑓𝑖𝑖

𝑡𝑡𝑖𝑖𝑡𝑡𝑡𝑡𝑡𝑡 𝑖𝑖𝑖𝑖 𝑖𝑖𝑖𝑖𝑡𝑡𝑡𝑡𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑡𝑡𝑖𝑖

𝑖𝑖

CPI= 1+0,18*2+0,06*1+0.25*3 = 1+0,36+0,06+0,75 = 2,17 CPI

a.2) Procesador con forwarding y los saltos se resuelven en decodificación:

• En este caso solo producen parada por LDE las instrucciones que dependen del load que son el 0,18*0,29=0,0522 del total

LOAD F D E M W Ii+1 F DP D E M W

Como el cálculo de la dirección y de la condición se realiza en decodificación solo se produce un ciclo de parada en los saltos que se toman que son 0,25 * 0,35=0,0875 del total.

BC F D E M W Ii+1 FP F D E M W

CPI= 1+0,0522*1+0,0675*1=1,1397

c) speed up =CPIviejo/CPInuevo =2,17/1,1397=1,904

8

Problema Un computador dispone de un sistema de memoria central constituido por una memoria principal Mp de 64 K palabras y una cache Mc de 1 K palabras con correspondencia directa y 64 palabras por bloque. El tiempo de ciclo de Mp es 10 veces superior al de Mc que es de 10 ns. Se ejecuta un programa que sigue el siguiente perfil de referencias a memoria:

17 . . 23 <------ . | . | ------165 | | . | 20 iteraciones | . | 10 iteraciones | . | - --------239 | . | . | 1200 ------- . . 1500

Se pide:

a) Interpretación de los bits de la dirección física del sistema de memoria para Mc.

b) Tiempo de ejecución del programa despreciando las lecturas/escrituras de operandos.

Solución: Mp (dir. posiciones) Mp( dir. bloques ) Mc (líneas)

17 . . . 23 . . . 165 . . . 239 . . . 1200 . .

1500

B0 . . . B0 . B1 . B2 . . . B3 . B15 . B18 . .

B23

MB0

MB1

MB2

MB3

MB15

MB14

MB13

a) Nº de líneas = 1K/64 = 16 = 24 4 bits de bloque (línea) 64 palabras/bloque = 26 6 bits de palabra

16

6 4 6

etiqueta palabra linea

b) ciclo interno: 0 fallos (se contabilizan en el externo ya que no se sustituye ninguna línea del interno en la ejecución del externo) ciclo externo: 1ª iteración: 19 fallos forzosos 2ª-10ª iteraciones: (3+3) * 9 = 54 tramo final: 5 fallos Nº total de fallos = 19+54+5 = 78 Tfallo = 78*64*10T = 49.920T Nº de referencias = 6+10*(142+20*75+961)+300=26.336 Treferencia =26.336T Total = (49.920+26.336)T = 76.256T = 762.560 ns

9

Problema Un computador dispone de un sistema de memoria central constituido por una memoria principal Mp de 64 K palabras y una caché de datos Mc de 32 palabras con correspondencia directa y 8 palabras por línea. El tiempo de acceso a Mp es de 200 nanosegundos y el de Mc 10 nanosegundos. En Mc opera una política de escritura directa (write through) sin asignación en cache. Se ejecuta el siguiente programa:

for(i= 0; i < 2; i++) for(j = 0; j < 8; j++)

x[i] [j] = 3*y[i] [j]; Los arrays x[i][j], y[i][j] están ubicados en posiciones consecutivas de memoria a partir de la dirección 0, uno a continuación de otro, ordenados por filas, y sus elementos están codificados con 4 palabras. Determinar: a) El formato de la dirección física de memoria respecto a Mc. b) El número de fallos que se producen en Mc al ejecutar el programa. c) El tiempo total de acceso a los arrays x[i][j], y[i][j] durante la ejecución del programa. Nota: Se supone que todas las referencias del programa a los arrays x[i][j], y[i][j] son convertidas por el compilador en accesos al sistema de memoria (Mc-Mp), sin la utilización de registros internos. Solución:

a) Mc = 32p = 25

Nº líneas = 25 / 23 = 22 =4 Mp = 64Kp = 216

16

11 2 3

etiqueta palabra linea

b)

Mp Mc L0

L1

L2 L3

B0 B1 B3 B4 B7 B8 B9 B11 B12 B15

X[0][0] X[0][1]

X[0][2] X[0][3]

X[0][6] X[0][7]

X[1][0] X[1][1]

X[1][6] X[1][7]

Y[0][0] Y[0][1]

Y[0][2] Y[0][3]

Y[0][6] Y[0][7]

Y[1][0] X[1][1]

Y[1][6] Y[1][7]

X[ ][ ]

Y[ ][ ]

Y[0][0] Y[0][1]

Y[0][2] Y[0][3]

Y[0][6] Y[0][7]

Y[0][4] Y[0][5]

Iteraciones i, j 0, 0 X[0][0]=2*Y[0][0] C0 1 fallo 0, 1 X[0][1]=2*Y[0][1] C0 0 fallos 0, 2 X[0][2]=2*Y[0][2] C1 1 fallo 0, 3 X[0][3]=2*Y[0][3] C1 0 fallos 0, 4 X[0][4]=2*Y[0][4] C2 1 fallo 0, 5 X[0][5]=2*Y[0][5] C2 0 fallos 0, 6 X[0][6]=2*Y[0][6] C3 1 fallo 0, 7 X[0][7]=2*Y[0][7] C3 0 fallos

1, 0 X[1][0]=2*Y[1][0] C0 1 fallo 1, 1 X[1][1]=2*Y[1][1] C0 0 fallos 1, 2 X[1][2]=2*Y[1][2] C1 1 fallo 1, 3 X[1][3]=2*Y[1][3] C1 0 fallos 1, 4 X[1][2]=2*Y[1][2] C2 1 fallo 1, 5 X[1][3]=2*Y[1][3] C2 0 fallos 1, 6 X[1][6]=2*Y[1][6] C3 1 fallo 1, 7 X[1][7]=2*Y[1][7] C3 0 fallos

Nº Fallos = 4 x 2 = 8 fallos d) Tfallos = 8 fallos * 8 palabras*200 ns = 12.800 ns

Tescritura = 16 elementos x[][] * 4 accesos/elemento * 200 ns = 12.800 ns

TlecturaMc = (16 elementos Y * 4 palabras/elemento – 8 lec. Simultaneas) * 10 ns = 560 ns

Ttotal = 12.800 + 12.800 + 560 = 26.160 ns

10

Problema Un computador dispone de un sistema de memoria central constituido por una memoria principal Mp de 4 K palabras y una cache Mc de 1 K palabras asociativa por conjunto, con 4 líneas por conjunto y 16 palabras por bloque, con política de reemplazamiento RLU. Se ejecuta 5 veces el programa que referencia las siguientes direcciones: 0, 1, 2, …, 1023, 1040, 1041,…, 1055 Si el tiempo de acceso a Mp es 10 veces superior al de Mc (T) se pide:

a) Interpretación de los bits de la dirección física del sistema de memoria para Mc. b) Evolución de los conjuntos de bloques durante la ejecución del programa. c) Tiempo medio de acceso a memoria.

Solución a) Mp 4K = 212 palabras 12 bits de dirección Bloque 16 palabras = 24 4 bits de palabra Mc 1K palabras/16 palabras/bloque = 64 líneas Nº conjuntos = 64/4 = 16 = 24 4 bits de conjunto 12-4-4 = 4 bits de etiqueta

12 bits

4 bits 4 bits 4 bits

Etiqueta Conjunto Palabra

b) direcciones físicas 0,1,2,3,…,15 ¦,16,…,31¦,32…¦....1023¦,1040,1041,…1055 número de bloque B0 B1 B4…….. B63 B65 C0 B0 B16 B32 B48 C1 B1/B65 B49 B17 B1/B65 B33 B17 B49 /B33 C2 B2 B18 B34 B50 C14 B14 B30 B46 B62 C15 B15 B31 B47 B63

c) 1ª pasada 65 fallos (1 por bloque) 2ª-5ª pasadas 4 pasadas x 5 fallos/pasada = 20 fallos Nº fallos = 65+20=85 Nº referencias = 5(1024+16)=5.200 Tfallos = 85/5.200 = 0,0163 Taccesomedio = (1-0,0163)T+0,0163*10T = 0,837T+0,163*10T*16 = 1,14T

11

Problema Un computador dispone de un sistema de memoria virtual con una capacidad de 4 GB, con tamaño de página de 4K y 8 MB de memoria principal. El TLB contiene un total de 128 entradas con un bit de validez por entrada. Se pide:

a) Formato de las direcciones virtual y física. b) Número de páginas virtuales y marcos de página. c) Tamaño en bytes del TLB. d) Número en decimal de página virtual y desplazamiento de página correspondiente a la dirección virtual: 100AB01D (hex)

Solución: a) Tamaño de página = 4 KB = 212 bytes 12 bits DP Tamaño Mv = 4 G = 232 bytes 32 bits DV 32 -12 = 20 bits NPV Tamaño Mp = 8 MB = 223 bytes 23 bits DF 23 -12 = 11 bits NPF

NPV = 20 bits DP =12 bits

NPF =11 bits DP = 12 bits

DV DF

b) Nº PVs = 220 = 1.048.576 páginas Nº MPs = 211 = 2.046 marcos c) Entrada al TLB

V NPV = 20 bits NPF = 11 bits

Longitud = 32 bits Tamaño del TLB = 128 * 32 = 4.096 bits = 4.096/8 bytes = 512 bytes d) NPV = 1 0 0 A B(16 = 11*160 + 10*161 + 0*162 + 0*163 + 1*164 = 11+160+65.536 = 65.707(10

NMP = 0 1 D(16 = 13*160 + 1*161 + 0*162 =13+16 = 29(10

1 0 0 A B 0 1 D

NPV = 65.707(10 DP = 29(10

12

Problema Un computador dispone del siguiente sistema de memoria:

Memoria virtual de 4GBytes Memoria física de 64MB y páginas de 8MB con política de reemplazamiento FIFO Cache de datos de 256KB con correspondencia directa. El tamaño del bloque es de 64KB.

El sistema almacena 20 álbumes de fotos (Alb1, ... , Alb20). Cada álbum ocupa 2MB y cada foto 64KB. El Alb1 empieza en la dirección virtual 0x02800000 y los demás están en direcciones virtuales consecutivas. Sabiendo que en un momento de la ejecución el contenido de la tabla de páginas es el siguiente:

Solución:

a) Indica los formatos de las direcciones virtual y física, esta última respecto a

la memoria virtual y la memoria cache. b) Indica que álbumes están en ese momento en la memoria principal y en qué

paginas físicas se encuentra cada uno. c) En qué direcciones físicas empiezan los álbumes de la última página que se

colocó en memoria principal

a)

9 23

Nº pag Virt Byte de la pagina

3 23

pag F

Byte de la pagina

10 16

Nº Bloq MP

Byte del Bloq

8 2 16

BloqC Byte del Bloq Etiqueta

b) Cada álbum ocupa 2MB → hay 4 álbumes por página (223 / 221 = 4) y cada álbum contiene 32 fotos (221 / 216 = 32) Nº pag Virt Byte de la pag Dir Virtual de Alb1 = 0x02800000 = 0000 0010 1000 0000 0000 0000 0000 0000 → página virtual 5 Como los álbumes van consecutivos ocupan desde la página virtual 5 hasta la página virtual 9 Mirando la tabla de páginas podemos decir que en la MP están los álbumes contenidos en la página virtual 5, 6 y 9 que se ubican en las páginas físicas 6, 0 y 1 respectivamente

c) La última página virtual a la que se ha accedido es la 9 pag Virt Byte de la pag Dir Virtual página virtual 9 = 0000 0100 1000 0000 0000 0000 0000 0000 = 0x04800000 → corresponde al Alb17 pag Fis Byte de la pag Dir Física del Alb17 = 00 1000 0000 0000 0000 0000 0000 = 0x0800000 → página física 1 A esta dirección se le va sumando el tamaño del álbum = 2MB = 221 = 0x200000 Dir Física del Alb18 = 0x0A00000 Dir Física del Alb19 = 0x0C00000 Dir Física del Alb20 = 0x0E00000

13

Problema Supongamos que en un sistema de memoria virtual que dispone de 3 marcos de página (páginas físicas) en Mp se ejecuta un programa que realiza la siguiente secuencia de referencias a páginas virtuales: 2,3,2,1,5,2,4,5,3,2,5,2. Determina la evolución del contenido de Mp y el número de fallos de página que se producen cuando se aplican las siguientes políticas de sustitución:

a) LRU b) FIFO c) CLOCK (FINUFO) d) OPTIMA

Solución