UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA ELO311 Estructuras de Computadores Terecer Certamen

1. Se tiene la siguiente secuencia de instrucciones assembler MIPS: a) Determinar los riesgos que se producen en add $t6, $t6, $t6 la ejecución de la secuencia en un procesador lw $t1, 5($t2) segmentado. lw $t3, 6($t1) Indicando dónde se detecta cada riesgo y cómo add $t4, $t1, $t3 se corrige por hardware. sw $t4, 0($t3) 70 puntos. b) Explicar el número de ciclos de reloj que son necesarios addi $t7, $t7, 1 para la correcta ejecución de la secuencia. 10 puntos. c) Reordenar la secuencia, sin cambiar el algoritmo que realiza, de tal forma de optimizar la ejecución en la cañería. Determinar el número de ciclos para realizar la secuencia. 20 puntos. Solución. a) El siguiente diagrama ilustra los riesgos de datos sin considerar las correcciones que puedan efectuarse. add $t6, $t6, $t6

M R I L

lw $t1, 5($t2) lw $t3, 6($t1) add $t4, $t1, $t3 sw $t4, 0($t3)

M D

M R I L M I

tiempo M D

R L M I

M D R L M I

M D R L M I

addi $t7, $t7, 1

M D R L

M D

Orden de ejecución a1) La tercera debe leer $t1 que aún no ha sido actualizado por la segunda. Se detecta cuando la tercera está en decodificación y la segunda en operación. rs y RD son iguales a $t1, RegWr=1 y además MemRd=1 Se corrige deteniendo el ingreso de nuevas instrucciones(no habilitando la escritura de PC) e impidiendo que avance la instrucción que está en decodificación(deshabilitando la escritura de IR) y marcando como inválida la instrucción que está en decodificación, con válido igual a cero. a2) La cuarta debe leer $t3 que aún no ha sido escrito por la segunda.

Solución Tercer Certamen.

18-11-2002

1

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA ELO311 Estructuras de Computadores Terecer Certamen

Se detecta cuando la cuarta está en decodificación y la segunda en operación. rs y RD1 son iguales a $t1, RegWr1=1. Se corrige anticipando Mout hacia A, mediante el mux AntA. a3) La cuarta debe leer $t3 que aún no ha sido actualizado por la tercera. Se detecta cuando la cuarta está en decodificación y la tercera en operación. rs y RD son iguales a $t3, RegWr=1 y además MemRd=1 Se corrige deteniendo el ingreso de nuevas instrucciones(no habilitando la escritura de PC) e impidiendo que avance la instrucción que está en decodificación(deshabilitando la escritura de IR) y marcando como inválida la instrucción que está en decodificación, con válido igual a cero. a4) La quinta debe leer $t3 que aún no ha sido escrito por la tercera. Se detecta cuando la quinta está en decodificación y la tercera en memoria. rs y RD1 son iguales a $t3, RegWr1=1. Se corrige anticipando Mout hacia A, mediante el mux AntA. a5) La quinta debe leer $t4 que aún no ha sido actualizado por la cuarta. Se detecta cuando la quinta está en decodificación y la cuarta en operaciones. rt y RD son iguales a $t4, RegWr=1 y Cop =sw. Se corrige, almacenando rt en RD. Y la corrección se efectúa cuando la cuarta está en memoria y la quinta en operación(con RegWr1=1, MemWr=1, RD1 = RD) llevando Mout a D, mediante la activación del mux controlado por AntM. Considerando las detenciones los riesgos de datos se reducen, como muestra el siguiente diagrama. Ahora sólo se tienen tres riesgos: a11) Segunda en memoria, tercera en decodificación RD1 = rs, RegWr1=1 se anticipa Mout hacia A. a12) Tercera en memoria, cuarta en decodificación. RD1=rt, RegWr1=1 se anticipa Mout hacia B. a13) Cuarta en memoria, quinta en operaciones. RD1=RD, MemWr=1, se anticipa Mout hacia D.

Solución Tercer Certamen.

18-11-2002

2

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA ELO311 Estructuras de Computadores Terecer Certamen tiempo [ciclos de reloj]

add $t6, $t6, $t6

1

2

M I

R L

lw $t1, 5($t2) lw $t3, 6($t1) add $t4, $t1, $t3 add $t4, $t1, $t3 sw $t4, 0($t3)

M I

3

4

5

6

7

M D R L M I

M I

10

11

12

termina lw $t3,6($t1)

M D R L M I

9

sale aire de la cañería

M D R L

8

M D R L M I

M D R L M I

sw $t4, 0($t3)

M D R L M I

addi $t7, $t7, 1

termina sw $t4,0($t3) M D

R L

M D

Instrucción que es leída

En el cuarto ciclo se detecta condición de detención, por lo tanto en el quinto ciclo vuelve a decodificarse la instrucción lw $t3, 6($t1); también se realiza(de nuevo) la búsqueda de la instrucción add $t4, $t1, $t3; se realiza en la parte de control de operaciones la acción de invalidar las órdenes que modifican el estado(RegWr1 queda igual a cero, en este caso); en la parte de datos de operaciones se realizan acciones mudas para lw $t3, 6($t1), se calcula la dirección efectiva. En el sexto ciclo se detecta condición de detención, por lo tanto en el séptimo ciclo vuelve a decodificarse la instrucción add $t4, $t1, $t3; también se realiza(de nuevo) la búsqueda de la instrucción sw $t4, 0($t3); y se realiza en la parte de control de operaciones la acción de invalidar las órdenes que modifican el estado(RegWr1 queda igual a cero, en este caso); en la parte de datos de operaciones se realizan las acciones para add $t4, $t1, $t3, se calcula la suma de $t2 con $t3. En el séptimo y noveno ciclo sale una burbuja de la cañería; es decir, no se completa la ejecución de una instrucción. Se pierden dos ciclos en la ejecución de esta secuencia de instrucciones. Solución Tercer Certamen.

18-11-2002

3

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA ELO311 Estructuras de Computadores Terecer Certamen

b) Observando el diagrama anterior, la secuencia se realiza en 12 ciclos del reloj. c) Cambiando el orden de la secuencia de instrucciones: tiempo[ciclos de reloj]

lw $t1, 5($t2) add $t6, $t6, $t6 lw $t3, 6($t1) addi $t7, $t7, 1

1

2

M I

R L M I

3

4

5

6

7

8

9

M D R L M I

M D R L M I

M D

M I

add $t4, $t1, $t3

M D

R L R L M I

sw $t4, 0($t3)

M D R L

M D

Instrucción que es leída

Las operaciones sobre los registros $t6 y $t7, no interactúan con el resto de las instrucciones y pueden cambiarse de lugar en la secuencia. La ubicación después de las instrucciones lw, permiten ahora que la secuencia se efectue sin detenciones. Entre la primera y la tercera se anticipa el valor del registro $t1 desde la memoria hacia el registro A previo a la unidad de operaciones y no es necesario efectuar una detención. Entre la tercera y la quinta se anticipa el valor del registro $t3 desde la memoria hacia el registro B previo a la unidad de operaciones y no es necesario efectuar una detención. Entre la quinta y la sexta se adelanta desde la memoria el valor del registro $t4 hacia el registro D previo a la unidad de memoria. Considerando que la instrucción store word, ocupa cuatro ciclos en su ejecución, se requieren ahora 9 ciclos de reloj para realizar la secuencia.

Solución Tercer Certamen.

18-11-2002

4

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA ELO311 Estructuras de Computadores Terecer Certamen

2. Para el procesador multiciclo, visto en las clases, efectuar las modificaciones al hardware(si son necesarias), para que pueda ejecutarse la instrucción que efectúa las siguientes transferencias lógicas: dobleintercambio: R[rs] ↔ R[rt]; R[rd] ↔ R[sa]; PC = PC + 4; Donde sa es el campo shift amount de la instrucción de tipo R. El contenido de R[rs] debe ser escrito en R[rt]; y el contenido de R[rt] debe ser escrito en R[rs]. El contenido de R[rd] debe ser escrito en R[sa]; y el contenido de R[sa] debe ser escrito en R[rd]. No puede modificarse la estructura interna del arreglo de registros. a) Determinar las modificaciones necesarias al camino de datos, del procesador multiciclo, visto en clases. 25 puntos. b) Indicar las secuencias de transferencias físicas, separadas por ciclo, para realizar la instrucción. Determinar el número de ciclos para ejecutar la instrucción. 25 puntos. c) Indicar los valores de las señales de control, separadas por ciclo, para realizar la instrucción. 25 puntos. d) Dibujar las modificaciones al diagrama de estados y escribir el microprograma, con la notación vista en clases, indicar todas las líneas que ejecutan la instrucción. 25 puntos. Solución: a) Modificando la unidad de memoria tal que puedan colocarse en el busW los contenidos de los registros A y B. Modificando el mux de entrada a la dirección de registro Ra tal que puedan efectuarse: A= R[rs] y A=R[rd]. Modificando el mux de entrada a la dirección de registro Rb tal que puedan efectuarse: B= R[rt] y B=R[sa]. Modificando el mux de entrada a la dirección de registro Rw tal que puedan efectuarse: R[rs]=busW, R[rt]=busW, R[rd]=busW, y R[sa]=busW.

Solución Tercer Certamen.

18-11-2002

5

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA ELO311 Estructuras de Computadores Terecer Certamen MemRd

MemWr

WEM

MemtoReg

0 AddrD

S

Memoria Dout Datos M

1

Din

B

busW

2

A

3

B

RegWr

SrcRa SrcRb RegDst

WEA WEB Equal

rs

0 5

rd

1

rt

0 5

sa

1

rd rt rs sa

busW

b) Transferencias físicas. dobleintercambio: IR = MemInst[PC], PC = PC+4; A=R[rs], B=R[rt]; R[rs] = B; R[rt] = A; A=R[rd], B=R[sa]; R[rd] = B; R[sa] = A; Solución Tercer Certamen.

Ra Rb

WE

32 Registros 32-bit

0 1 5 2 RW Rw 3

32

A

busA

32

busB

B

32

R[rs] ↔ R[rt]; R[rd] ↔ R[sa]; PC = PC + 4; Unidad Instrucción. Unidad Registros. Lectura. Unidad Registros. Escritura. Unidad Registros. Escritura. Unidad Registros. Lectura. Unidad Registros. Escritura. Unidad Registros. Escritura. 18-11-2002

6

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA ELO311 Estructuras de Computadores Terecer Certamen

Se requieren 7 ciclos para realizar la nueva instrucción. d) Señales de control. R[rs] ↔ R[rt]; R[rd] ↔ R[sa]; PC = PC + 4;

dobleintercambio:

nPC_sel = “+4”, WEPC , WEIR ; SrcRa=”rs”, SrcRb=”rt”, WEA , WEB ; RegDst = "rs" , Memtoreg="B", RegWr. RegDst = "rt" , Memtoreg="A", RegWr. SrcRa=”rd”, SrcRb=”sa”, WEA , WEB ; RegDst = "rd" , Memtoreg="B", RegWr. RegDst = "sa" , Memtoreg="A", RegWr.

Unidad Instrucción. Unidad Registros. Lectura. Unidad Registros. Escritura. Unidad Registros. Escritura. Unidad Registros. Lectura. Unidad Registros. Escritura. Unidad Registros. Escritura.

d) Diagrama de estados. 0000 j

inc 0001 T0

dobleintercambio

add 1101

0010

inc

T1

sub

ori

load

0101

0011

sw

1110

0110

inc

1111

inc

inc

0100

inc 1011

1001

Cero

Cero

1100

1000

writereg

inc

1010

0111

inc

inc

beq

Cero

Cero Cero

10000 inc 10001 Cero

Solución Tercer Certamen.

18-11-2002

7

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA DEPARTAMENTO DE ELECTRONICA ELO311 Estructuras de Computadores Terecer Certamen

Microprograma: fetch: IR = MemInst[PC], PC = PC+4; µPC = µPC +1;

A=R[rs], B=R[rt],if(COp == J) PC = (PC)&0xF0000000+add_26*4, µPC = T0[OP];

dobleintecambio: R[rs] = B, µPC = µPC +1; R[rt] = A, µPC = µPC +1; A=R[rd], B=R[sa], µPC = µPC +1; R[rd] = B, µPC = µPC +1; R[sa] = A, µPC = 0.

Solución Tercer Certamen.

18-11-2002

8