6 organización básica y lenguaje de máquina prof. javier ...arreglos •los lenguajes de...
TRANSCRIPT
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.