View
217
Download
0
Category
Preview:
Citation preview
Organización del Computador I Verano
MIPS (1 de 2) Basado en el capítulo 3 del libro de Patterson y Hennessy
Verano 2004 Profesora Borensztejn
Lenguajes para la máquina • Las computadoras son circuitos electrónicos, por lo
tanto para hablar con ellas se necesita enviarles señales eléctricas
• Las señales viajan por los circuitos electrónicos que están formados por (millones de) transistores.
• Los transistores son interruptores que, en función del valor de la señal eléctrica que los controla, dejan o no pasar esa señal. Por eso a su salida habrá dos posibles valores: estos valores se pueden representar simbólicamente con los dígitos cero y uno.
• Los símbolos cero y uno se llaman bits.
Transistores: ¿que podemos hacer con algunos pocos de
ellos?• Con sólo dos: convertir un 1 en un 0 (y viceversa):
hacer una puerta NOT• Con 4 transistores podemos hacer una puerta
lógica NAND o NOR.• Con estas puertas elementales se puede construir
cualquier función.• Un computador no es más que un conjunto
(grande) de funciones de un conjunto (grande) de entradas (señales)
Lenguajes para la máquina• En realidad, el lenguaje máquina está formado por números
en base 2! Tanto los datos como las instrucciones se codifican como números en base 2.
• Cada máquina (o familia de máquinas) tiene su propio lenguaje máquina. Los lenguajes máquina,en realidad, no difieren mucho entre sí, debido a que:– la tecnología de implementación de los circuitos es la misma para
todos los fabricantes– Todas las máquinas deben proporcionar un repertorio básico de
instrucciones (sumar, por ejemplo).
• Asi que, no se preocupen, lo que aprendan de MIPS será...........totalmente diferente en INTEL (orga2)
Lenguajes Máquina• Una computadora, está formada por
• La Unidad de Proceso y Control (es donde nos vamos a centrar en este curso) implementa un conjunto de funciones (de propósito general) a través de millones de transistores.
• Imposible de entender mirando lo que hace cada transistorNecesitamos una abstracción
Processor I/O
Control
Datapath
Memory
Input
Output
Abstraccionesswap(int v[], 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
00000000101000010000000000011000000000001000111000011000001000011000110001100010000000000000000010001100111100100000000000000100101011001111001000000000000000001010110001100010000000000000010000000011111000000000000000001000
Binary machinelanguageprogram(for MIPS)
C compiler
Assembler
Assemblylanguageprogram(for MIPS)
High-levellanguageprogram(in C) • Lenguaje ensamblador:
– Notación más humana que los números binarios
– Requiere una instrucción por línea
• Lenguajes de alto nivel permiten:– Facilidad al programar– Menor tiempo de desarrollo
(mayor productividad)– Independencia del
computador
MIPS
• Machine without Interlocked Pipelined Stages• Arquitectura diseñada por Hennessey, en 1980,
guiada por los siguientes principios:– La simplicidad favorece la regularidad– Más pequeño es más rápido (menos es mas)– Hacer rápido el caso común
• Objetivos de diseño: maximizar rendimiento y reducir costos
• Usado por: NEC, Nintendo, Silicon Graphics, Sony.
Aritmética MIPS• Todas las instrucciones tienen 3 operandos• El orden de los operandos es fijo (primero el destino)
Ejemplo:
código C: A = B + C
código MIPS: add $s0, $s1, $s2
(el compilador asocia las variables a los registros)
Aritmética MIPS• Principio de Diseño: la simplicidad favorece la uniformidad.
– Operaciones con número de operandos variables complica el hardware. • Pero esto complica algunas cosas ...
código C: A = B + C + D;E = F - A;
código MIPS: add $t0, $s1, $s2add $s0, $t0, $s3sub $s4, $s5, $s0
• Los operandos deben ser registros, y solo hay 32 registros.• Los registros son de 32 bits• Principio de Diseño: cuanto más pequeño, mas rápido.
Registros vs Memoria
• Las instrucciones aritméticas deben tener sus operandos en registros, de los cuales la arquitectura provee 32.
• El compilador realiza la asociación de variables con registros. • ¿Que sucede con los programas que tienen muchas variables?
– El compilador intenta mantener las variables usadas más frecuentemente en registros. Aquellas menos usadas se guardan en memoria. El proceso de poner estas variables en memoria se llama spilling.
– Los registros tienen menor tiempo de acceso que la memoria, y además son mas útiles porque se puede operar con ellos.
– El compilador, para obtener un rendimiento alto, debe hacer un uso eficiente de los registros.
Organización de la Memoria
• Se ve como un vector muy largo de una dimensión. Cada posición tiene asociada una “dirección”.
• Una dirección de memoria es un índice al vector.
• "Byte addressing" significa que el índice apunta a un byte de memoria.
0
1
2
3
4
5
6
...
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
Organización de la Memoria
• En general, los datos son de una longitud mayor que un byte4 bytes: se llaman words en MIPS.
• La memoria se puede ver como un vector de:– 232 bytes con direcciones (de byte) que van desde 0 a 232-1– 230 words con direcciones (de byte) 0, 4, 8, ... 232-4
• Los words están alineados en memoria:– Es decir, los dos bits menos significativos de una dirección de memoria
que identifica a un word son cero.
• La organización de un word en memoria se llama “big endian” (en contraposición con “little endian”): consiste en almacenar el byte de mas peso del word en la dirección más baja de memoria.
...
0
4
8
12
000000000000000000000000000000000
4
8
12
32 bits of data
32 bits of data
32 bits of data
32 bits of data
00000000000000000000000000000001
00000000000000000000000000000010
00000000000000000000000000000011
Instrucciones para leer/escribir datos en memoria
• Load: carga de un operando de memoria a registro• Store: almacenamiento de un operando de registro a memoria• Ejemplo:
C código: A[8] = h + A[8];
MIPS código: lw $t0, 32($s3)add $t0, $s2, $t0sw $t0, 32($s3)
• El destino en la instrucción de Store está al final.
• Recordar: operandos aritméticos no pueden estar en memoria.
Hasta ahora:
• MIPS— carga de words pero direccionamiento a
nivel de byte— aritmética solo en registros
• Instrucción Significado
add $s1, $s2, $s3 $s1 = $s2 + $s3sub $s1, $s2, $s3 $s1 = $s2 – $s3lw $s1, 100($s2) $s1 = Memory[$s2+100] sw $s1, 100($s2) Memory[$s2+100] = $s1
• Instrucciones para la toma de decisiones– Alteran el flujo secuencial del programa– “Controlan” el orden de ejecución de las
instrucciones del programa
• Instrucciones MIPS de salto condicional:bne $t0, $t1, L1 beq $t0, $t1, Ll
• Ejemplo: if (i= = j) h = i + j; bne $s0, $s1, Lladd $s3, $s0, $s1
Ll: ....
Control
• Intrucción MIPS de salto incondicionalj Ll
• Ejemplo:
if (i!=j) beq $s4, $s5, L1 h=i+j; add $s3, $s4, $s5else j L2 h=i-j; L1: sub $s3, $s4, $s5
L2: ...
• Como sería un bucle for?for (i=0;i<10;i++)
h=h+i;
Control
Hasta Ahora:
• Instrucción Significado
add $s1,$s2,$s3 $s1 = $s2 + $s3sub $s1,$s2,$s3 $s1 = $s2 – $s3lw $s1,100($s2) $s1 = Memory[$s2+100] sw $s1,100($s2) Memory[$s2+100] = $s1bne $s4,$s5,L Siguiente instr.en L si $s4!=$s5beq $s4,$s5,L Siguiente instr.en L si $s4 =$s5j L Siguiente instr.en L
• Instrucción SetLessThan:if $s1 < $s2 then $t0 = 1
slt $t0, $s1, $s2 else $t0 = 0
• Usamos la instrucción SLT para construir el salto si menor que: "blt $s1, $s2, L “ slt $t0, $s1, $s2 bne $t0, $zero, L
• El registro $zero se corresponde con el registro 0 que está cableado a cero.• El compilador MIPS construye todas las variantes de saltos condicionales utilizando las
instrucciones bne, beq y slt. De esta manera, se aplica el criterio de simplicidad: la incorporación de estas instrucciones alargaría el tiempo para ejecutar una instrucción: se prefieren dos instrucciones rápidas frente a todas mas lentas.
2
Control: Saltar si Menor?
Instrucción Jump Register
• Instrucción MIPS jr: sirve para saltar a la dirección contenida en el registro especificado.
jr $t0
• Permite implementar la sentencia switch
• Se implementará con una Tabla que contiene las direcciones (etiquetas) de los distintos trozos de código correspondientes a cada caso. (Tabla de direcciones de salto).
switch(k){case 0: f=i+j; break; case 1: f=g+h; break; case 2: f=g-h; break; case 3: f=i-j; break;}
Implementación de la sentencia switch
Las variables f a k se corresponden con $s0..$s5, $t2 contiene 4. La variable k se usará como índice a la tabla de etiquetas.La tabla se almacena a partir de la dirección guardada en $t4
switch(k){case 0: f=i+j; break; case 1: f=g+h; break; case 2: f=g-h; break; case 3: f=i-j; break;}
; comprueba si k>0 y k<4slt $t3, $s5, $zeroBne $t3, $zero, finslt $t3, $s5, $t2Bne $t3, $zero, fin
;multiplica $s5 (k) por 4 ;para acceder a la Tabla
add $t1,$s5,$s5add $t1,$t1,$t1
;cargar la dirección de Tabla[k]add $t1,$t1,$t4lw $t0,0($t1)
;saltar a la instrucciónjr $t0
L0: add $s0,$s3,$s4J fin
L1: add $s0,$s1,$s2J fin
L3: sub $s0,$s1,$s2J fin
L3: sub $s0,$s3,$s4Fin:
• Constantes pequeñas son usadas muy frecuentemente (52% de los operandos son contantes pequeñas en gcc)
por ej: A = A + 5;B = B + 1;C = C - 18;
• Soluciones:– Almacenar algunas constantes típicas en memoria, y luego cargarlas.
lw $t0,dir_constante($zero)add $s1,$t0,$t0
– Crear constantes cableadas en registros (como $zero).– Incorporar a MIPS versiones de instrucciones en los cuales un operando es
una constante y dicha constante, de 16 bits, está almacenada en la instrucción.addi $s1, $s1, 4slti $s2, $s3, 10andi $t0, $t2, 6
3
Constantes
• LUI (load upper immediate) almacena los 16 bits mas altos de una constante en un registro.
lui $t0, 1010101010101010
Luego se suma al registro la parte baja de la constante utilizando una instrucción aritmética con operando inmediato
ori $t0, $t0, 1010101010101010
1010101010101010 1010101010101010
1010101010101010 0000000000000000
0000000000000000 1010101010101010ori
1010101010101010 0000000000000000
Se llena con ceros
¿Constantes mas grandes?
Caracteres y BytesUn carácter se representa mediante el código standard ASCII (American Stantard Code for Information Interchange)
ASCII Carácter ASCII Carácter ASCII Carácter ASCII Carácter ASCII Carácter ASCII Carácter
32 espacio 48 0 64 @ 80 P 96 112 p
33 ! 49 1 65 A 81 Q 97 a 113 q
34 " 50 2 66 B 82 R 98 b 114 r
35 # 51 3 67 C 83 S 99 c 115 s
36 $ 52 4 68 D 84 T 100 d 116 t
37 % 53 5 69 E 85 U 101 e 117 u
38 & 54 6 70 F 86 V 102 f 118 v
39 ` 55 7 71 G 87 W 103 g 119 w
40 ( 56 8 72 H 88 X 104 h 120 x
41 ) 57 9 73 I 89 Y 105 i 121 y
42 * 58 : 74 J 90 Z 106 j 122 z
43 + 59 ; 75 K 91 [ 107 k 123 {
44 , 60 < 76 L 92 \ 108 l 124 |
45 - 61 = 77 M 93 ] 109 m 125 }
46 . 62 > 78 N 94 ^ 110 n 126 ~
47 / 63 ? 79 O 95 0 111 o 127 DEL
Caracteres• Instrucciones para leer y escribir bytes:
– Lb: carga un byte de memoria y lo sitúa en los 8 bits más bajos del registro (derecha)
– Sb: lee el byte que está a la derecha en el registro especificado y lo escribe en memoria.
• Los caracteres se combinan en cadenas: en C, el fin de una cadena se marca con un byte cuyo valor es cero (carácter Null)
lb $t0, 0($sp)sb $t0, 0($gp)
Strcpyvoid strcpy(char x[],char y[]){
int i;i=0;while ((x[i]= y[i])!=0)
i=i+1;}
strcpy:; direcciones de x e y en $a0 y $a1; se usa $s0 para i
sub $sp, $sp, 4 sw $s0, 4($sp)
;inicializa i en cero add $s0,$zero,$zero
L1: ;guarda la direccion de y[i] en $t1
add $t1,$a1,$s0;carga y[i] en $t2
lb $t2,0($t1);guarda la direccion de x[i] en $t3
add $t3,$a0,$s0;guarda $t2 en x[i]
sb $t2,0($t3);aritmética de punteros
addi$s0,$s0,1bne $t2, $zero, L1
;restaura los valores antiguos; y retorna
lw $s0, 4($sp)add $sp, $sp, 4jr $ra
Soporte para procedimientos
Mecanismo de llamada y retorno de un procedimiento:
1.Paso de parámetros a través de un lugar conocido
2.Transferencia de control a la subrutina
3.Ejecución del código de la subrutina
4.Situar el resultado en un lugar conocido
5.Retornar el control al punto de origen
1. $a0..$a3
2. Instrucción MIPS:
jal dirección_subrutina
3. Ejecución del código de la subrutina
4. $v0-$v1
5. $ra: contiene la dirección de retorno. La instrucción jr $r0 devuelve el control al programa llamador.
Instrucciones JAL y JR (call y return)
• Jump and Link: salta y enlaza
• Cambia el valor del PC por la dirección especificada en la instrucción y almacena en el registro $r0 la dirección de retorno (PC+4).
• La instrucción JR $r0 se utiliza para el retorno del procedimiento
La Pila• ¿Que sucede si el programa necesita utilizar más registros
(temporales) para hacer cálculos? El compilador puede usarlos, siempre y cuando preserve los valores que tenían antes de invocarse el procedimiento.
• Para preservar los valores, se vuelcan los registros en memoria (spilling).
• El lugar idóneo para realizar el spilling (vuelco) es una estructura de datos en memoria llamada pila: una cola donde el último que entra es el primero que sale.
• Los programas MIPS reservan un registro, $sp (stack pointer), que es el puntero al tope de la pila: es decir, apunta a la posición de memoria donde se ha almacenado el último dato.
Ejemplo de una función
Las variables g a j se corresponden con $a0..$a3, y f se corresponde con $s0.
int ejemplo(int g,int h,int i,int j){
int f;f=(g+h)-(i+j);return f;
}
ejemplo:; salvar los registros $s0,$t0 y $t1
sub $sp, $sp, 12; *sw $t1, 8($sp)sw $t0, 4($sp)sw $s0, 0($sp)
;realiza el cálculo de f ;y lo deja en $s0
add $t0,$a0,$a1add $t1,$a2,$a3sub $s0,$t0,$t1
;copia $s0 en $v0 (reg. de retorno)add $v0,$s0,$zero
;restaura los valores antiguos; y retorna
lw $s0, 0($sp)sw $t0, 4($sp)sw $t1, 8($sp)add $sp, $sp, 12jr $ra
0($sp)
4($sp)
8($sp)
$sp $s0
$spAntes de instrucción *
$t0
$t1
Convenciones • Los compiladores establecen una convención en el uso de
los registros para evitar salvar y restaurar registros cuyo valor nunca se usa.– $t0..$t9: 10 registros temporales cuyo valor no es preservado por
el procedimiento invocado– $s0..$s7: 8 registros que si deben ser salvados si son utilizados por
el procedimiento invocado
• Además, recordamos que:– $a0..$a3: 4 registros para paso de parámetros– $v0..$v1: 2 registros para devolver resultados– $sp: registro puntero a pila – $ra: registro que guarda la dirección de retorno
Procedimientos anidados
c
A CB
• Lo mismo sucede con la dirección de retorno, y con todos los registros temporales que cada procedimiento deba seguir usando despues de la llamada.
• El invocador apila sus registros de argumentos ($a0..$a4) y temporales ($t0..$t9). El invocado apila el registro $ra y cualquier registro salvado $s0..$s7 usado por el invocado.
• El puntero a la pila ($sp) se ajusta a la cantidad de registros salvados. Antes del retorno, se restauran los registros y $sp se ajusta al valor inicial (el que recibió).
• Si B recibe de A en $a0..$a4 sus parámetros, deberá salvarlos en la pila antes de llamar a C
Bloque de Activación• Las variables locales a los procedimientos que no caben
en los registros, tales como tablas o estructuras, también se almacenan en la pila.
• El conjunto de información almacenada en la pila es:– Argumentos (si hay mas de 4)– Dirección de Retorno– Registros Salvados– Variables Locales
• El bloque de pila que contiene esa información se denomina Bloque de Activación y los programas pueden utilizar un registro, el $fp, como puntero al Bloque.
Bloque de Activación
Argumentos
Dirección de Retorno
Registros Salvados
Variables Locales
$FP
$SP
El puntero $fp, a diferencia de $sp, se mantiene fijo durante toda la ejecución del procedimiento, brindando un registro base estable para acceder a parámetros y variables.
Convenciones
Nombre Número Uso Preservado$zero 0 valor constante cero n.a.$at 1 reservado para el ensamblador no$v0-$v1 2-3 resultados y evaluación expresiones no$a0-$a3 4-7 argumentos si$t0-$t7 8-15 temporales no $s0-$s7 16-23 salvados si$t8-$t9 24-25 temporales no$k0-$k1 26-27 reservado para el sistema operativo no$gp 28 puntero glogal si$sp 29 puntero pila si
ResumenMIPS operands
Name Example Comments$s0-$s7, $t0-$t9, $zero, Fast locations for data. In MIPS, data must be in registers to perform
32 registers $a0-$a3, $v0-$v1, $gp, arithmetic. MIPS register $zero alw ays equals 0. Register $at is $fp, $sp, $ra, $at reserved for the assembler to handle large constants.
Memory[0], Accessed only by data transfer instructions. MIPS uses byte addresses, so
230 memory Memory[4], ..., sequential w ords differ by 4. Memory holds data structures, such as arrays,
words Memory[4294967292] and spilled registers, such as those saved on procedure calls.
MIPS assembly language
Category Instruction Example Meaning Commentsadd add $s1, $s2, $s3 $s1 = $s2 + $s3 Three operands; data in registers
Arithmetic subtract sub $s1, $s2, $s3 $s1 = $s2 - $s3 Three operands; data in registers
add immediate addi $s1, $s2, 100 $s1 = $s2 + 100 Used to add constants
load word lw $s1, 100($s2) $s1 = Memory[$s2 + 100] Word from memory to register
store word sw $s1, 100($s2) Memory[$s2 + 100] = $s1 Word from register to memory
Data transfer load byte lb $s1, 100($s2) $s1 = Memory[$s2 + 100] Byte from memory to register
store byte sb $s1, 100($s2) Memory[$s2 + 100] = $s1 Byte from register to memory
load upper immediate lui $s1, 100 $s1 = 100 * 216 Loads constant in upper 16 bits
branch on equal beq $s1, $s2, 25 if ($s1 == $s2) go to PC + 4 + 100
Equal test; PC-relative branch
Conditional
branch on not equal bne $s1, $s2, 25 if ($s1 != $s2) go to PC + 4 + 100
Not equal test; PC-relative
branch set on less than slt $s1, $s2, $s3 if ($s2 < $s3) $s1 = 1; else $s1 = 0
Compare less than; for beq, bne
set less than immediate
slti $s1, $s2, 100 if ($s2 < 100) $s1 = 1; else $s1 = 0
Compare less than constant
jump j 2500 go to 10000 Jump to target address
Uncondi- jump register jr $ra go to $ra For switch, procedure return
tional jump jump and link jal 2500 $ra = PC + 4; go to 10000 For procedure call
Compilación, Ensamblage, Linkedición y Carga
Programa .c
Compilador
Programa .s
Ensamblador
Objeto .o Librerías de rutinas
Montador
Ejecutable (LM) Cargador
Memoria
Ensamblador• Traduce pseudoinstrucciones, por ejemplo
• Convierte el programa en lenguaje ensamblador en un programa objeto: – instrucciones en lenguaje máquina– datos– Información para situar las instrucciones en memoria
• El programa objeto está compuesto por 6 secciones:– Cabecera– Segmento de Texto– Segmento de Datos– Información de reubicación– Tabla de Símbolos– Información para depuración
move $t0, $t1Es traducida a:
add $t0,$zero, $t1
Montador, Linker• Une distintos programas objeto en un único ejecutable• Útil para reutilizar código ya ensamblado (por ejemplo, librerías de
rutinas standard) • Funciones:
– Sitúa simbólicamente en memoria los datos y el código– Determina las direcciones de los datos y de las etiquetas de instrucciones– Resuelve las referencias externas
• El archivo ejecutable consta de:– Cabecera: indica el tamaño de los sementos de código y datos– Segmento de código– Segmento de datos
• Datos estáticos• Datos dinámicos• Pila
Convención MIPS de distribución de memoria
Reservado
Código
Datos Estáticos
Datos Dinámicos
Pila
0040 0000
1000 00001000 8000
7fff ffff
pc
$gp
$sp
0000 0000
Cargador
• Para ejecutar el programa, el sistema operativo realiza las siguientes acciones:– Lee la cabecera del archivo ejecutable para determinar el
tamaño de los segmentos de código y de datos– Crea un espacio de direcciones para albergar el programa,
y copia las instrucciones y los datos a este espacio– Copia en el segmento de pila, los argumentos del programa– Inicializa los registros: el $sp, $gp– Salta a una rutina de inicio (start-up routine) que a su vez
llama al programa main y cuando este finaliza, llama a una rutina de salida (exit system call)
FIN MIPS
Recommended