CLASE 13

FORMATOS DE INSTRUCCIÓN DEL MIPS

FORMATO TIPO R

FORMATO TIPO I

FORMATO TIPO J

Operaciones Aritmético lógicasadd, sub, and, or, nor, sll, srl, slt

Instrucciones inmediatas, de acceso a memoria, saltos condicionales

addi, andi, ori, nori, lw, sw, beq, bne

Instrucciones de salto incondicionalj, jal

EJEMPLOS DE REPASO

Ejemplo:Compilar la siguiente porción de código en ensamblador del MIPS:

while(save[i] == k) i += 1;

Solución:Asumiendo que la variables i y k corresponden a los registros $s3 y $s5, y la dirección base de save esta en $s6

Loop: add $t1,$s3,$s3 add $t1,$t0,$t0 add $t1,$t0,$s6 lw $t0,0($t1) bne $t0,$s5,Exit addi $s3,$s3,1 j loopExit: ...

MODOS DE DIRECCIONAMIENTO

El MIPS implementa 5 modos de direccionamiento:• Registro.• Inmediato.• Base o desplazamiento.• Relativo al PC.• Pseudo-directo.

SOPORTE DE BAJO NIVEL PARA PROCEDIMIENTOS

• El stack pointer (registro $sp) apunta al tope de la pila• El stack “crece” de las direcciones superiores a las inferiores.• Operaciones sobre el stack:

Llevar un dato al stack: PUSH$sp = $sp – 4El dato se lleva al stack en el nuevo $sp

Recuperar un dato del stack: POPDato tomado del stack en $sp$sp = $sp + 4

PILAStack Pointer $SP

Memoria

Ultima posición de Memoria

PUSHDecrementar $SPMover valor

Stack Pointer $SP valor

POPLeer valorIncrementar $SP

INTRODUCCION• Ecuación de rendimiento

Time Cycle ClockCPICount nInstructiotime CPU

Número de instrucciones (IC): Determinado por la arquitectura (ISA) y el compilador

CPI y tiempo de ciclo: Determinado por el hardware de la CPU

INTRODUCCION• Procesador (CPU)

– Ruta de datos (datapath)• Porción del procesador que corresponde al HW necesario para ejecutar las

operaciones que él demanda– Unidad de control

• Porción del procesador (también en HW) que le indica al datapath lo que debe hacer

IMPLEMENTACION BASICA MIPS

Subconjunto de la arquitectura MIPS (suficiente para ilustrar los principios que orientan el diseño de un datapath y una unidad de control para cualquiera otra ISA).

• Instrucciones de acceso a memoria– Load word, lw– Store word, sw

• Instrucciones aritmético-lógicas– Suma, add– Resta, sub– AND lógica, and– OR lógica, or– Set on less than, slt

• Instrucciones de salto– Branch if equal, beq– Jump, j

PASOS PARA LA EJECUCION DE UNA INSTRUCCION

• Búsqueda (fetch) de la instrucción– Trae una instrucción desde la memoria de instrucciones de acuerdo con el valor del PC

(Program Counter)• Lectura de operandos

– Acceso al banco de registros empleando los campos de la instrucción para leer uno (load) o dos registros (ALU, store)

• De acuerdo con el tipo de instrucción:– Emplear la ALU para calcular:

• Un resultado aritmético o lógico (instrucciones aritmético-lógicas)• Una dirección de memoria para las instrucciones load/store• Una condición de igualdad (branch)

– Acceder a la memoria de datos en las instrucciones load/store– Acceder al banco de registros para escribir el resultado de la ALU o un valor proveniente

de memoria (instrucciones aritmético-lógicas, load)– Actualizar el valor del PC de acuerdo con el resultado de la comparación con:

• PC + 4• Dirección de destino de salto

PASOS PARA LA EJECUCION DE UNA INSTRUCCION

VISTA DE ALTO NIVEL DE LA IMPLEMENTACION DEL MIPS

Dos tipos de unidades funcionales:• Elementos que operan en los valores de datos (combinacional).• Elementos que contienen el estado (secuencial).

• Operación en un solo ciclo.• Modelo de memoria dividida (Harvard): Una memoria para instrucciones y una

para datos.

VISTA DE ALTO NIVEL DE LA IMPLEMENTACION DEL MIPS• No se pueden unir los cables así

de simple• Es necesario usar un multiplexor

(selector de datos)• Varias unidades deben controlarse

de acuerdo con el tipo de instrucción.

PRINCIPIOS DE DISEÑO LOGICOInformación codificada en binario• Voltaje bajo = 0• Voltaje alto = 1• Un cable por bit• Datos de múltiples bits se codifican en buses formados por múltiples cablesElementos combinacionales

Operan sobre datosLa salida es función de las entradas actuales

Un elemento combinacional siempre producirá la misma salida ante la misma entrada

Ej: ALUElementos secuenciales

Almacenan información (estado)Ej: registros, memorias de datos e instrucciones

PRINCIPIOS DE DISEÑO LOGICOInformación codificada en binario• Voltaje bajo = 0• Voltaje alto = 1• Un cable por bit• Datos de múltiples bits se codifican en buses formados por múltiples cables.

Elementos combinacionales• Operan sobre datos• La salida es función de las entradas actuales• Un elemento combinacional siempre producirá

la misma salida ante la misma entrada• Ej: ALU

Elementos secuenciales• Almacenan información (estado)• Ej: registros, memorias de datos e instrucciones

D

Clk

Q

PRINCIPIOS DE DISEÑO LOGICO – ELEMENTOS COMBINACIONALES

Compuerta AND (Y = A & B)

Sumador ( Adder)(Y = A + B)

Multiplexor(Y = S ? I1 : I0)

Unidad aritmetico-logicaY = F(A ,B)

AB

Y

A

B

Y+

I0I1

YMux

S

A

B

YALU

F

PRINCIPIOS DE DISEÑO LOGICO – ELEMENTOS SECUENCIALES

Flip-flop (Tipo D)• Almacena un bit• Actualiza el valor almacenado cuando la señal de reloj pasa de 0 a 1

D

Clk

QClk

D

Q

Flip-flop con control de escritura• Sólo actualiza el valor almacenado en el flanco de reloj cuando la

entrada de control de escritura es 1

D

Clk

Q

Write Write

D

Q

Clk

METODOLOGIA DE TEMPORIZACION• Esquema empleado para determinar cuándo un dato es válido y estable respecto

al reloj Accionada por flanco (edge-triggered): todos los cambios de estado (de los

elementos secuenciales) ocurren en un flanco de reloj• La lógica combinacional transforma los datos entre flancos de reloj

Ejecución típica: lectura del elemento de estado propagación del dato a través de la lógica combinacional escritura del resultado en otro elemento de estado

El retardo más largo determina el periodo de la señal de reloj

• CPU monociclo (Single-cycle CPU) Todas las instrucciones se ejecutan por completo en un ciclo de reloj. La ejecución comienza en un flanco y termina en el siguiente (del mismo

tipo).

CONSTRUYENDO EL DATAPATHDatapath• Colección de componentes del procesador que tienen la capacidad de

operar sobre datos y almacenarlos. (Memorias de datos e instrucciones, banco de registros, ALU, sumadores).

• Construiremos gradualmente un datapath para el MIPS, refinando la vista de alto nivel expuesta anteriormente

• Partiremos por definir los elementos requeridos para ejecutar cada tipo de instrucción para luego combinarlos todos

BUSQUEDA DE INSTRUCCIONESLa búsqueda de instrucciones implica:• leer una instrucción de la memoria de instrucciones usando la dirección indicada

por el PC.• Actualizar el valor del PC a la dirección de la próxima (secuencial) instrucción.

• El PC es actualizado cada ciclo de reloj de manera que no necesita una señal explicita de control.

• La ejecución secuencial de programas implica actualizar el PC para que apunte a la instrucción inmediatamente consecutiva en la memoria de instrucciones.

• El nuevo valor de PC debe ser PC+4. Memoria direccionable por bytes. Tamaño de palabra de 32 bits.

BUSQUEDA DE INSTRUCCIONES

BUSQUEDA DE INSTRUCCIONES

DECODIFICACION DE INSTRUCCIONESDecodificar instrucciones implica:• Enviar el opcode y el campo fuction de la instrucción a la unidad de control.• Leer dos valores del Register file.

Las direcciones del banco de registros (Register file) son contenidas en la instrucción.

BANCO DE REGISTROS

• Agrupa los 32 registros definidos en la ISA MIPS

• Permite el acceso simultáneo a 3 registros• Acceso de lectura a dos registros

Entradas de 5 bits cada una para identificar los registros. Salidas de datos de 32 bits

• Acceso de escritura a un registro Entrada de 5 bits para identificar el

registro. Entrada de datos de 32 bits Una señal de control de escritura

explícita (RegWrite) porque no se escribe en el banco en cada ciclo (Ej: instrucción sw).

Una entrada de reloj (no ilustrada) determinante en las operaciones de escritura.

Es posible leer y escribir el mismo registro dentro de un ciclo de reloj.

BANCO DE REGISTROS

INSTRUCCIONES TIPO RLas instrucciones aritmético-lógicas realizan:

Y requieren:• Leer dos operandos fuente (desde los registros rs y rt)• Realizar la operación aritmético-lógica (funct)• Escribir el resultado en el registro rd

R[rd] R[rs] funct R[rt]

Ej:add $t0, $t1, $t2

INSTRUCCIONES TIPO REl banco de registros no es escrito (sw) cada ciclo, de manera que se necesita una señal explicita de control de escritura (WE: Register Write) para el banco de registros.

PONIENDO TODO JUNTO

Decodificar rs, rt, rd, op, …

INSTRUCCIONES TIPO ILas instrucciones aritmético-lógicas realizan:

Y requieren:• Leer el registro rt • Leer el numero inmediato de 16 bits, el cual debe ser extendido a un numero de

32 bits.• Escribir el resultado en el registro rs

Ej:ori $8, $9, 64

INSTRUCCIONES TIPO I

COMBINACION DE LOS DATAPATH• Para tal fin se adicionan

multiplexores. Donde? Cuando?

MUX

COMBINACION DE LOS DATAPATH

INSTRUCCIONES DE MEMORIALas instrucciones load/store realizan:

• En la ALU se calcula la dirección de acceso a memoria sumando el registro base (tomado del banco de registros) y el campo de 16 bits de la instrucción extendido en signo

• Store: Almacena el valor (extraído del banco de registros) en la memoria de dato.• Load: Escribe en el banco de registros el valor leído de la memoria de datos.

R[rt] MEM[R[rs] + sign_ext(Imm16)] #loadMEM[R[rs] + sign_ext(Imm16)] R[rt] #store

Ej:lw rt, offset(rs)sw rt, offset(rs)

INSTRUCCIONES DE MEMORIAlw $1, 30($2) $1=M[$2+30]sw $3, 10($4) M[$4+30]=$3

INSTRUCCIONES DE SALTO CONDICIONALLa instrucción branch if equal (beq) realiza:

• Compara dos operandos leídos del banco de registros haciendo una sustracción en la ALU y chequeando su igualdad mediante la salida Zero

• Calcula la dirección de destino de salto: Extendiendo en signo el desplazamiento de 16 bits Desplazando 2 bits a la izquierda el valor previo Y sumándolo a PC+4 (valor calculado antes en la búsqueda de la instrucción)

• Salto tomado (branch is taken): los dos registros comparados son iguales La condición de igualdad se verifica PC = PC PC + 4 + (sign_ext(Imm16) || 00)

• Salto no tomado (branch is not taken): los dos registros comparados NO son iguales

La igualdad no se verifica PC = PC + 4

if (R[rs] == R[rt])then PC PC+4+(sign_ext(Imm16)||00) /* Branch is taken*/else PCPC+4 /* Branch is not taken*/

INSTRUCCIONES DE MEMORIA

BEQ $1, $2, 12Acción: si ($1!=$2) entonces PC=PC+4Acción: si ($1==$2) entonces PC=PC+4+48

INSTRUCCIONES DE SALTO

• Las operaciones de salto poseen el siguiente formato:

• Lo que se hace es reemplazar los 8 bits menos significativos del PC con los 26 bits menos significativos de la instrucción buscada corrida 2 bits a la izquierda.

COMPOSICION DE LOS ELEMENTOS

• Conociendo los componentes requeridos para la ejecución de las instrucciones aritmético-lógicas, load/store y branch, podemos combinarlos en un solo datapath que pueda ejecutarlas todas, agregando algunos multiplexores y señales de control

• En esta primera versión del datapath cualquier instrucción se ejecuta en un ciclo de reloj

Cada componente del datapath sólo puede realizar una función a la vez durante la ejecución de una instrucción

Por lo tanto, aquellos componentes que requieran ser utilizados más de una vez deben replicarse

Tal es el caso de las memorias: se requieren memorias de datos e instrucciones independientes

• Es necesario emplear multiplexores cuando un dato pueda provenir de diferentes fuentes en una instrucción

Para elegir la fuente de datos se emplean señales de control

JUNTANDO TODO

Búsqueda de instrucciones tipo R y acceso a memoria

JUNTANDO TODO

Insercion del multiplexor

JUNTANDO TODO

Distribución del reloj.

JUNTANDO TODO

Añadiendo la porción de salto

REFERENCIAS

• http://microe.udea.edu.co/~farivera/docencia.html• http://www.cse.hcmut.edu.vn/~

anhvu/teaching/2010/BTKT-KTMT/MIPS%20Green%20Card.pdf• http://www.ece.eng.wayne.edu/~

gchen/ece4680/lecture-notes/lecture-notes.html• http://www.cs.uiowa.edu/~ghosh/6011.html• http://www.cse.hcmut.edu.vn/~anhvu/teaching/2010/504002CS/• http://cs.wellesley.edu/~cs240/• http://www.utdallas.edu/~dodge/EE2310/• Computer organization and design. The hardware/software interface, 3rd

ed., Chapter 5. D. Patterson and J. Hennessy. Morgan Kaufmann Publishers