Arquitecturas de Computadores6 Organización Básica y Lenguaje de Máquina

Prof. Javier Cañas R.

Temario1. Introducción

2. Estructura Básica de un Computador

3. Lenguaje de Máquina Básico

4. Instrucciones para decisiones

5. Procedimientos

6. Direccionamiento

7. Assemblers y Linkers

1 Introducción• Para dar órdenes a un computador digital se

debe hablar su mismo lenguaje.

• Las palabras del lenguaje de un computador se denominan instrucciones, y el vocabulario conjunto de instrucciones.

• En este capítulo nos concentraremos en el conjunto de instrucciones de una máquina real. En forma previa debemos conocer la estructura básica de un computador.

2 Estructura Básica de un Computador

• Un computador digital se compone de tres grandes bloques:

- El Procesador

- El Sistema de Memoria

- El Sistema de Entrada y Salida

... Estructura

• El Procesador es el elemento central, y como tal, el objetivo principal de nuestro estudio. Se Implementa en un Chip VLSI y está formado por la unidad de Control y el Camino de Datos.

Bloques principales

Unidadde

Control

Caminode

Datos

Procesador

Memoria

Entrada

Salida

Compilador

3 Lenguaje de Máquina Básico

• Consideraremos la máquina MIPS (R3000 y R4000) para nuestro estudio.

• El procesador MIPS tiene 32 bits y se desarrolló con tecnología RISC.

• Si bien consideraremos una máquina en particular, su diseño es lo suficientemente general como para entender el lenguaje de máquina de cualquier procesador.

Aritmética

• Todo computador debe ser capaz de realizar operaciones aritméticas.

• Sumas y restas en MIPS se realizan de la siguiente manera:

add a,b,c! #a ←b+csub a,b,c #a ←b-c

• Toda instrucción aritmética tiene 3 operandos: simplicidad→regularidad → desempeño (Regla 1 de diseño)

EjemplosCódigo en C:

a=b+c;

d=a-e;

Lenguaje de Máquina:

add a,b,c

sub d,a,e

Código en C:

f=(g+h)-(i+j) ¿..?

Operadores y registros

• A diferencia de los lenguajes de alto nivel, los operandos de las instrucciones aritméticas se ubican en memorias muy rápidas llamadas registros.

• Un registro de la máquina MIPS tiene 32 bits. Se dice entonces, que la palabra de la máquina MIPS es de 32 bits.

...Operadores y registros

• Una colección de 32 registros rápidos se denomina Archivo de Registros.

• ¿Por qué el archivo de registros tiene sólo 32 registros?

- Lo pequeño es rápido (regla 2 de diseño)

• La identificación de los registros se puede hacer usando números (del 0 al 31).

Identificación de registros y convenciones

• Usaremos $s0,$s1,..$s31 para designar registros que corresponden a variables de programas.

• Usaremos $t0,$t1,..$t31 para designar registros que corresponden a variables temporales.

Ejemplo

• Compilar “a mano”:

f=(g+h)-(i+j)

add $t0,$s1,$s2 #$t0←g+h

add $t1,$s3,$s4 #$t1←i+j

sub $s0,$t0,$t1 #f←$t0-$t1

Tratamiento de Arreglos

• Los lenguajes de programación además de manejar variables simples son capaces de manipular estructuras más complejas.

• Estructuras de datos como los arreglos, son mantenidos en memoria principal.

• Para llevar una palabra de memoria a un registro se utiliza la instrucción lw.

Ejemplo

• Compilar “a mano”, la siguiente expresión en C:

g=h+A[8];

lw $t0,8($s3) #$t0 ← A[8]add $s1,$s2,$t0 #g ←h+A[8]

• La dirección de memoria se obtiene sumando una constante con el contenido del segundo registro

Contenido delsegundo registroConstante

Offset y Registro base

• La constante en una instrucción de transferencia se denomina offset y el registro que se le suma para formar la dirección, se denomina registro base.

lw $t8,8($s3)

Registro BaseOffset

Restricción de Alineamiento

• La memoria principal está organizada en Bytes. Esto significa que las direcciones son direcciones de Bytes

• Los procesadores están organizados en registros de 32 bits (palabras).

• La forma de ubicar Bytes en palabras da origen a dos organizaciones distintas llamadas Big Endian y Little Endian.

Big Endian y Little Endian

3 2 1 0

7 6 5 4

0

4

Bytes

Memoria Little Endian

VAX

Intel

DEC Risc

0 1 2 3

4 5 6 7

0

4

Memoria Big EndianMIPS

Sparc

IBM 360

Direcciones de palabras

Ejemplo: Arreglo con variable índice

• Se pide el código assembly correspondiente a la sentencia C: g=h+A[i]

• Asumir que A tiene 100 elementos. La base está en el registro $s3 y además el compilador asocia las variables:

g ↔ $s1,h ↔ $s2, i ↔ $s4

... Solución g=h+A[i]

• Antes de cargar A[i] en un registro temporal, se necesita su dirección. Antes de sumar i a la base del arreglo para generar su dirección, es necesario multiplicar el índice i por 4, debido a la forma de direccionar bytes.

• La multiplicación por dos se puede generar:

i+i=2i, 2i+2i=4i, etc..

Soluciónadd $t1,$s4,$s4 #$t1←2*i

add $t1,$t1,$t1 #$t1←4*i

• Para obtener la dirección de A[i], necesitamos sumar $t1 con la base de A que está en $s3add $t1,$t1,$s3 #$t1←dirección A[i]

• Con esta dirección se puede cargar A[i] en un registro temporal:lw $t0, 0($t1) # $t0 ← A[i]

• Finalmente el resultado queda en g:add $s1,$s2,$t0 # g←h+ A[i]

Assembly a Lenguaje de máquina

• La instrucción que se representa en assembly por add $t0,$s1,$s2 en una instrucción de máquina (notación decimal) queda:

OP6b

rs5b

rt5b

rd5b

shamt5b

funct6b

Formato tipo R

0 17 18 8 0 32

$s1 $s2 $t0add add

Campos del formato• op: código de operación

• rs: Primer operando fuente

• rt: Segundo operando fuente

• rd: Registro destino

• shamt: Shift amount (se usa en instrucciones de desplazamiento

• funct: selecciona una variación específica del código de operación (Código de operación expandido)

Formato tipo I (Inmediato)

• Consideremos la instrucción assembly:lw $t0, 32($s3) # $t0 ← A[8]

OP

6brs5b

rt5b

dirección16b

Formato tipo I

35 17 18 32

$s3 $t0lw

Formato tipo I (Inmediato)

• Consideremos la instrucción assembly:sw $t0, 32($s3) # A[8] ← $t0

OP

6brs5b

rt5b

dirección16b

Formato tipo I

43 17 18 32

$s3 $t0sw

Resumen de Formatos

• Es un buen principio de diseño tomar compromisos: regularidad de formatos y tamaño del código de operación (número de instrucciones)

bits 6 5 5 5 5 6

op rs rt rd shamt funct

op rs rt Dirección

R

I

Pseudo Instrucciones• Muchas instrucciones Assembly no existen en el

Lenguaje de Máquina, pero pueden ser generadas con otras instrucciones.

• Un ejemplo es la instrucción move que permite copiar un registro en otro. Esta instrucción no existe en la máquina MIPS

move $s1,$s2 #$s1← $s2

• El Assembler MIPS genera: add $s1,$0,$s2 #$s1← $s2+ 0

4 Instrucciones para decisiones

• La máquina MIPS presenta dos instrucciones para la toma de decisiones:

• beq: branch equal:

beq reg1, reg2, L1

#if (reg1==reg2) goto L1

• bne: branch not equal:

bne reg1, reg2, L1

#if (reg1!=reg2) goto L1

Ejemplo de decisiones

• Generar lenguaje de máquina para el siguiente código C:

if(i==j) goto L1;

f=g+h;L1: f=f-i;

• Asumir que las 5 variables: f,g,h,i,j; corresponden a los 5 registros: $s0,....,$s5

Solución

• L1 representa la dirección de la instrucción de resta

beq $s3,$s4,L1 #if(i==j) goto L1add $s0,$s1,$s2 # f=g+h L1: sub $s0,$s0,$s3 #f=f-i

Ejemplo 2

• Usando las mismas variables y registros del ejemplo anterior, generar código de máquina para:

if(i==j) f=g+h; else f=g-h;

Solución

• Este ejercicio introduce otro tipo de salto llamado salto incondicional. La instrucción MIPS se denomina jump y se abrevia j

bne $s3,$s4,Else #if(i!=j)goto Elseadd $s0,$s1,$s2 #f=g+hj Exit #goto ExitElse: sub $s0, $s1, $s2 #f=g-hExit:

Saltos Incondicionalesj Exit #goto Exitjr $t1 #goto $t1

Prof. Javier Cañas R. 32

2 Dirección6b 26b

j es del tipo J

jr es del tipo R

op6b

rs5b

rt5b

rd5b

shamt5b

funct6b

0 rs 0 0 0 8

Compilación de Loops

• Compilar el código C:while (A[i]==k)

i=i+j;

• Asumiremos que i,j k corresponden a los registros $s3, $s4, y $s5. Además la base del arreglo A está guardada en $s6.

• El primer paso es cargar A[i] en un registro temporal:

... LoopsLoop: add $t1,$s3,$s3 #$t1=2*i add $t1,$t1,$t1 #$t1=4*i add $t1,$t1,$s6 #$t1 es la dirección de A[i] lw $t0,0($t1) #$t0=A[i] bne $t0,$s5,Exit # ir a Exit si A[i] ≠ k add $s3,$s3,$s4 #i=i+j j LoopExit:

Comparaciones

• La máquina MIPS tiene dos instrucciones de comparación:slt $s1,$s2,$s3 #set on less than

#if $s2<$s3 $s1←1 else $s1←0

... comparaciones

• Saltar menor que se puede construir:slt $s1,$s2,$s3

bne $s1,$0, Menos #va a Menos si #$s1≠0, o sea si a < b

• Existe la pseudo instrucción blt (branch less than), pero el compilador genera las dos instrucciones anteriores si encuentra blt.

La sentencia switch

• Ejemplo, compilar el segmento C:switch(k) {

case 0: f=i+j; break; //k=0

case 1: f=g+h; break; //k=1 case 2: f=g-h; break; //k=2 case 3: f=i-h; break; //k=3

}

• Asumiremos que las 6 variables desde f a k, corresponden a los registros $s0 a $s5. El registro $t2 contiene el valor 4

... Asignación de registros

f ↔ $s0g ↔ $s1h ↔ $s2i ↔ $s3j ↔ $s4k ↔ $s54 ↔ $t2

Código

• Usaremos la variable k para indexar una tabla de salto. El salto se hace vía el valor cargado.

• Lo primero es verificar rangos para k

slt $t3,$s5,$0 # ¿k <0?bne $t3,$0,Exit #si k<0, goto Exitslt $t3,$s5,$t2 # ¿k<4?beq $t3,$0,Exit # si k >=4 goto Exit

... Código

• Hay que multiplicar por 4 el valor de k para convertirlo en dirección de byte.

add $t1,$s5,$s5 # $t1=2*k

add $t1,$t1,$t1 # $t1=4*k

• Las direcciones de los códigos correspondientes a los distintos valores de k, se mantienen en una tabla de salto.

... Código

• Asumiremos una secuencia de 4 palabras de memoria, comenzando de la dirección almacenada en $t4. Obtenemos así la dirección de L0, L1,L2 y L3:

L0L1L2L3

Tabla de Salto

... Código

• Obtención de la dirección de L0, L1,L2 y L3:

add $t1,$t1,$t4 #$t1= dirección de Tabla Salto [k]lw $t0,0($t1) #$t0=Tabla Salto[k]

... Códigojr $t0 #salto basado en registro $t0

• Los primeros tres casos de switch son los mismos:L0: add $s0,$s3,$s4

j Exit L1: add $s0,$s1,$s2 j Exit L2: sub $s0,$s1,$s2 j Exit

... Código

• Finalmente:

L3: sub $s0,$s3,$s4 Exit:

5 Procedimientos

• Los procedimientos o subrutinas son las herramientas más poderosas para estructurar programas.

• En la ejecución de un procedimiento un programa sigue los siguientes pasos:

- Poner parámetros en un lugar accesible

- Transferir el control al procedimiento

- Realizar la tarea

- Poner el resultado en lugar accesible

- Volver el control al punto original

...Procedimientos

• El software MIPS asigna los siguientes registros a Procedimientos:

- $a0-$a3: Argumentos para el paso de parámetros

- $v0-$v1: Registros para el retorno de valores

- $ra: Dirección de retorno para volver al punto original

Jump and Link

• La máquina MIPS incluye la instrucciónjal

jal DirecciónProcedimiento

• Tiene como efecto saltar a la dirección indicada, pero simultáneamente salva la dirección de retorno en $ra

• La dirección almacenada en $ra se denomina dirección de retorno. Esto es necesario ya que el mismo procedimiento puede ser invocado en diferentes partes del programa.

El Program Counter PC

• Es necesario disponer de un registro que permita almacenar la dirección de la instrucción que está siendo ejecutada.

• Por razones históricas este registro se denomina PC: Program Counter.

• Debería llamarse IAR (Instruction Address register).

Jal y Jr

• La instrucción jal salva PC+4 en el registro $ra para establecer la dirección de retorno.

• La instrucción que permite volver al punto inicial es: jr $ra

Retorno de procedimiento

instruc1Dir1

jr $ra

Procedimiento

jal Dir1PC

PC+4

Prog. Principal

Procedimientos Anidados

• Lo normal en el desarrollo de un programa es que un procedimiento pueda llamar a otro, y que también se pueda llamar a si mismo en forma directa o indirecta (Recursividad):

.....jal B;

A instb.....jal C;.......jr $ra

B

inst1.......jr $ra

C

Manejo del Stack

• Es necesario el uso de un stack para permitir flexiblemente usar procedimientos anidados y recursividad:

Stack

$sp

sp: Stack Pointer

$ts

ts: Ajusta tope del Stack

Código usando Stack

.......jal B;

A ............add $sp,$sp,$tssw $ra,0($sp)jal C;lw $ra,0($sp)sub $sp,$sp,$ts.......jr $ra

B

.......

.......jr $ra

C

6 Direccionamiento

• Los mecanismos de direccionamiento responden a las preguntas:

- ¿Dónde ir a buscar un operando?

- ¿A qué dirección transferir el control del programa?

• Ambas preguntas se refieren a los mecanismos de direccionamiento de los computadores.

... Direccionamiento• La Máquina MIPS presenta todos los modos de

direccionamiento de las máquinas reales.

• Los mecanismos de direccionamiento que estudiaremos son:

- Tipo Registro

- Operandos Inmediatos

- Direccionamientos Absolutos

- Direccionamientos relativos al PC

- Direccionamiento Registro Base

Direccionamiento tipo Registro

• Lo más fácil es que el operando se encuentre en un registro. Este es el caso de las instrucciones tipo R.

• Ejemplo: add,$s1,$s2,$s3

OP6b

rs5b

rt5b

rd5b

shamt5b

funct6b

-44 36 -8

Direccionamiento: Operandos Inmediatos• Estadísticas de programas muestran que el

50% de los operandos son constantes, y estas constantes son números relativamente pequeños.

• Una forma es almacenar las constantes en la memoria principal y recuperar mediante una instrucción lw

• Ejemplo en C: a=a+5;

...Operandos Inmediatos

• Supongamos que el número 5 lo guardamos en la dirección DIREC, y que la variable a la almacenamos en el registro $s1, entonces a=a+5 se genera:

lw $t1,DIREC($0)

add $s1,$s1,$t1

• Veremos una solución mejor.

Instrucciones Inmediatas: adi

• Una alternativa al código anterior es: addi $s1,$s1,5

• Formato es tipo I:

• Se puede apreciar que los operandos están limitados a 16b.

86b

rs5b

rt5b

Operando Inmediato16b

Instrucciones Inmediatas: slti,lui

• Otras instrucciones con operandos inmediatos son:

slti $t1,$s1,5 #if($s1<5)$t1=1. set on less than inmediate

lui $s1,255 #load upper inmediate

$s1 00000000111111111 00.......................00

lui permite cargar una constante en un registro

Direccionamiento Absoluto

• La única instrucción que permite este direccionamiento es jump (j).

• El espacio de direcciones alcanzable es de 64MB. El código que se genera no es relocalizable. Ejemplo:j 1000 # goto 1000

2 10006b 26b

tipo J

Direccionamiento Relativo al PC

• Ejemplo:

bne $s1,$s2,Exit # goto Exit si $s1 !=$s2

• El espacio de direcciones alcanzable es de 216B. Para aumentar este espacio, se considera que el campo de 16b son direcciones de palabras de 32b

56b

rs ($s1)5b

rt($s2)5b

Exit16b

Formato tipo I

...Direccionamiento Relativo al PC

Limitado por 16bPC

...Direccionamiento Relativo al PC

• El hardware modifica el PC antes de terminar la instrucción actual. PC ←PC+4. Esto significa que la dirección es relativa a la dirección de la siguiente instrucción.

Limitado por 16bPC

PC+4

... EjemploEjemplo:

a: bne $s2,$s3,FIN

add $t4,$s4,$s6

j a

FIN:

80000 5 8 21 280004 0 19 20 19 0 3280008 2 8000080012

$s2 ↔ 8, $s3 ↔ 21

$t4 ↔ 19, $s6 ↔20

a: Dirección 80000

Resumen Direccionamientos

Tipo Registro

OP rs rt rd shamt funct

Registro Base

OP rs rt dirección

+

Memoria

...Resumen Direccionamientos

Inmediato

OP rs rt

Relativo al PC

OP rs rt dirección

PC +

Memoria

...Resumen DireccionamientosAbsoluto

OP dirección

Memoria

7 Assemblers y Linkers

• El lenguaje assembly es la representación simbólica de la codificación binaria de un programa.

• El lenguaje assembly tiene directivas que no generan código: .data, .global

• Los roles que tiene el lenguaje assembly son: lenguaje intermedio para un compilador, embedded computers.

Compilación y Ensamblado

Programa Compilador Assembler

LinkerComputador

Lenguaje Assembly

Ejecutable

Ejemplo de compilaciónswap(intv[],int k)

{int temp;

temp=v[k];

v[k]=v[k+1];

v[k+1]=temp;

}

swap:

muli $2,$5,4

add $2,$4,$2

lw $15,0($2)

lw $16,4($2)

sw $16,0($2)

sw $15,4($2)

jr $31

De la programación en Assembly

• Programar en Assembly tiene varias desventajas:

- Específico a una máquina (baja portabilidad)

- La relación entre líneas de código de un lenguaje de alto nivel y Assembly se denomina factor de expansión

... De la programación en Assembly

• ...desventajas:

- Estudios demuestran que un programador escribe el mismo número de líneas de código por día programando en Assembly o programando en un lenguaje de alto nivel.

- Si X es el factor de expansión, la productividad de un Lenguaje de Alto Nivel respecto a Assembly es X

Links a URL relacionados

• www.mips.com

• http://pages.cs.wisc.edu/~larus/spim.html

Arquitecturas de Computadores6 Organización Básica y Lenguaje de Máquina

Prof. Javier Cañas R.