S07 - myTeachingURJC/Arq-computadores-01 GitHub Wiki

Sesión de Teoría 7: Ordenación, alineamiento y Modos de direccionamiento

Tiempo: 2h
Objetivos de la sesión:
- Conocer todos los aspectos en el diseño de un repertorio de instrucciones
- Ordenación de los datos
- Alineamiento
- Modos de direccionamiento

Contenido

Introducción
Decisiones en el diseño de un repertorio de instrucciones
Ordenación
Alineamiento
Modos de direccionamiento
Estructuras de datos: Arrays
- Ejemplo: Array de palabras de 32 bits
Ejercicios
Autores
Licencia
Enlaces

Introducción

Para diseñar un repertorio de instrucciones hay varios aspectos a tener en cuenta. En esta sesión hablaremos sobre cómo se pueden ordenar los datos, cómo afecta la alineación de los datos al rendimiento, y qué maneras tenemos de acceder a los operandos: los modos de direccionamiento

Decisiones en el diseño de un repertorio de instrucciones

Para diseñar un repertorio de instrucciones, o estudiar los ya existentes, hay que tomar una serie de decisiones. Se resumen a continuación:

Tipo: CISC-RISC
Almacenamiento de los operandos: Pila, acumulador, registros de propósito general (registro-registro, registro-memoria, memoria-memoria)
Ordenación: Little endian, Big Endian
Alineamiento: En qué direcciones de memoria pueden estar los datos mayores de un byte: medias palabras, palabras o dobles palabras
Modos de direccionamiento: ¿Cómo se accede a los operandos?
Conjunto de de operaciones: aritmético-lógicas (ALU), de acceso a memoria, de control de flujo (saltos) y llamadas al sistema operativo
Codificación de las instrucciones: Formato de las instrucciones

En la sesión anterior ya vimos los repertorios CISC y RISC, el almacenamiento de los operandos y el formato de las instrucciones del RISC-V. En esta desarrollaremos las demás

Ordenación

La unidad mínima de información accesible en una memoria es 1 byte. Las memorias disponen de muchas posiciones de 1 byte, cada una con una dirección, empezando desde la 0 y terminando en la máxima. Así, en el RISC-V de 32 bits que usamos en el laboratorio, las direcciones van desde la 0x00000000 hasta la 0xFFFFFFFF. Cada una de ellas se refiere a 1 byte

En este ejemplo se muestran los bytes almacenados en un trozo de la memoria, cuyas direcciones van desde la 0x10010023 hasta la 0x10010027

¿Cuál es el byte almacenado en la dirección 0x10010025? 12. ¿Cual es el que está almacenado en la dirección 0x10010027? El 6F. Nos podemos referir a cada una de estas posiciones de memoria y conocer el valor allí guardado, o almacenar en cualquiera de ellas un byte nuevo

Almacenando un dato de 16 bits (media palabra)

Pero... ¿qué ocurre cuando queremos almacenar un dato mayor que un byte? Hay que utilizar varias posiciones de memoria. Así, para guardar la media palabra 0xBACA en la memoria, necesitaremos dos posiciones de memoria, una que contenga el byte de mayor peso (0xBA) y otra que contenga el byte de menor peso (0xCA)

Para almacenar la media palabra 0xBACA a partir de la dirección 0x10010023, tenemos dos posibilidades: Almacenar 0xBA en 0x10010023 y 0xCA en 0x10010024, ó hacerlo en el orden contrario: almacenar 0xCA en 0x10010023 y 0xBA en 0x10010024

La primera posibilidad se denomina BIG ENDIAN. El byte de mayor peso se almacena primero (dirección menor) y luego el de menor peso en la siguiente dirección (que es mayor)

La otra posiblidad es conocida como LITTLE ENDIAN y es la que usan los RISC-V y que ya conocemos del laboratorio: El byte de menor peso se almacena en la dirección menor (la primera dirección)

Almacenando un dato de 32 bits (palabra)

¿Y si el dato es todavía más grande, como por ejemplo una palabra (4 bytes)? ¿Cómo se ordenan en memoria? Exactamente igual. Se puede usar cualquiera de las dos posiblidades: BIG ENDIAN o LITTLE ENDIAN

Si queremos almacenar la palabra 0xCAFEBACA a partir de la dirección 0x10010023, podemos guardar en ella el byte de mayor peso (0xCA) y a continuación los demás (Ordenación BIG ENDIAN) o por el contrario podemos empezar por el byte de menor peso y luego el resto (Ordenación LITTLE ENDIAN)

Ordenaciones Little-Endian y Big-Endian

Cada fabricante elige un tipo de ordenación u otra. Los procesadores Intel utilizan ordenación Little Endian mientras que los ARM pueden utilizar cualquiera de las dos formas (es configurable). Los RISC-V también utilizan ordenación Little Endian

Conocer el tipo de ordenación es necesario para el diseñador del procesador, sin embargo es transparente para el programador. Cuando programamos en el laboratorio en lenguaje ensamblador y utilizar palabras, nos da igual cómo estén almacenadas en memoria. Lo importante es poder guardarlas y leerlas. El hardware y el ensamblador se ocupan de que esto sea transparente para los programadores

El tipo de ordenación es independiente del Alineamiento de la memoria. Esta es otra decisión de diseño que veremos a continuación

Alineamiento

Los bytes pueden estar en cualquier posición de memoria. Los referenciamos para leeerlos y escribirlos sin mayor problema. Sin embargo, cuando trabajamos con datos mayores que un byte, como las medias palabras (2 bytes), las palabras (4 bytes) o las dobles palabras (8 bytes) la dirección en la que se encuentren tiene un impacto directo en el número de accesos a memoria, y por tanto en el rendimiento del procesador

Para entender lo que ocurre, hay que conocer cómo están implementadas las memorias. El tipo más básico de memoria es el que físicamente sólo almacenan bytes. Decimos que son memorias con anchura de 1 byte. Estas son las memorias utilizadas en muchos de los ordenadores de 8 bits de los años 80: ZX-spectrum, amstrad, etc... En las memorias con anchura de 1 byte, si queremos leer o escribir un dato mayor, hay que hacer varios accesos. Por ejemplo, para leer un dato de 16 bits (media palabra) son necesarios dos accesos de lectura a la memoria. Físicamente la memoria sólo te puede devolver datos de 8 bits

Memorias de anchura de 16 bits

¿Cómo se podría mejorar el rendimiento? ¿Cómo podríamos leer de la memoria un dato de 16 bits usando sólo un acceso a memoria? Habría que utilizar una memoria de anchura de 16 bits. Esto es, una memoria que sea capaz de entregarme de golpe los 16 bits de una sola lectura. Pero la capacidad para leer un único byte la seguimos teniendo. Las direcciones de memoria siguen haciendo referencia a bytes pero los accesos son por pares de bytes

Como ejemplo veamos esta memoria, de 16 bits de anchura. En ella están almacenadas las medias palabras 0xCAFE, 0x0123 y 0xBACA. La ordenación puede ser cualquiera. Por ejemplo Little endian, que es la del RISC-V. Si ahora leemos el dato de la dirección 0x00000004, leemos de golpe los 16 bits ahí almacenados: 0xBACA.

Esa media palabra se ha leído de golpe y sólo se ha necesitado un único acceso a memoria (una única lectura).
Aunque los accesos sean siempre con datos de 16 bits, eso no nos impide acceder únicamente a bytes. Si leemos el byte de la dirección 0x00000003, en realidad la memoria nos devuelve en paralelo los dos bytes que están en las direcciones 0x00000002 y 0x00000003, pero el hardware se encarga de devolvernos sólo los 8 bits correspondientes al byte leido

Acceso a 16 bits NO alineados

Siempre que le pedimos a la memoria medias palabras situadas en direcciones pares, sólo tiene que realizar UN UNICO acceso a memoria. Sin embargo, si le pedimos que nos devuelva la media palabra que está situada a partir de la dirección 0x00000003, tendrá que acceder a esta dirección y a la siguiente (0x00000004). Tiene que leer los 16 bits situados en 0x00000002 y luego los 16 bits de 0x00000004. A patir de ellos ya puede componer el dato que se quería leer: 0xCA01

Es decir, que si metemos una memoria de 16 bits de anchura para reducir los accesos a memoria y mejorar el rendimiento, resulta que dependiendo de la dirección donde esté el dato serán necesarios uno o dos accesos. Si está en las direcciones pares sólo se necesita un acceso, pero si está en las direcciones impares se necesitan dos

En vez de direcciones pares o impares, hablamos de direcciones ALINEADAS o NO ALINEADAS. Si el dato al que acceder está en una dirección Alineada, sólo se necesita una operación de memoria, mientras que si está en direcciones NO alineadas serán necesarios dos accesos

Acceso a palabras (32 bits)

Estas mismas ideas se aplican también a datos mayores. ¿Qué ocurre si estamos trabajando con palabras (4 bytes)?. Habrá más o menos accesos a memoria dependiendo de la anchura que tenga la memoria física. Así, si la memoria es de 8 bits, para leer una palabra necesitamos 4 accesos. En este ejemplo estamos leyendo la palabra 0xBEBECAFE de la dirección 0x10010024

Si lo que hubiese es una memoria con una anchura de 16 bits, entonces para leer una palabra sólo se necesitarían dos accesos, por lo que el rendimiento es mejor

El mejor rendimiento se conseguiría usando una memoria de 32 bits de anchura. En ese caso, la palabra se obtiene con sólo un acceso a memoria. En este ejemplo estamos leyendo la palabra situada en la dirección 0x00000004

Pero... sólo se ha necesitado un acceso porque la palabra está contenida en una dirección ALINEADA, que en este caso significa que es múltiplos de 4. Sin embargo, si lo que se quiere es leer una palabra situada a partir de una dirección NO alineada, serán necesarios dos accesos. En este ejemplo la palabra 0xBEBECAFE está almacenada a partir de la dirección 0x00000007. Para obtenerla hay que leer los 4 bytes de la dirección 0x00000004 y los 4 de la dirección 0x00000008: dos accesos en total

La conclusión es que es muy importante la dirección en las que se almacena una palabra. Si están en direcciones NO alineadas, entonces se requieren dos accesos a memoria. Sin embargo si están en posiciones Alineadas, sólo se necesita un acceso a memoria

Procesadores con acceso alineado o NO alineado

Puesto que hay una penalización en el rendimiento por acceder a direcciones de memoria NO alineadas, los fabricantes deciden si sus procesadores pueden trabajar con datos siempre alineados o datos sin alinear. Asi por ejemplo, en los procesadores con arquitectura x86, está permitido el acceso a datos no alineados. En el RISC-V los datos deben estar alineados (aunque se puede acceder a datos no alineados gestionando la excepción que se produce en los accesos no alineados, pero es lento)

En esta figura se muestran las direcciones alineadas para los diferentes tipos de datos: byte, medias palabras, palabras y dobles palabras

En el caso de los bytes, TODAS las direcciones están alineadas. Esto significa que siempre podemos acceder a los bytes de forma individual y que sólo se requiere una operación de memoria

Las medias palabras (16 bits) ocupan 2 bytes, por lo que sólo están alineadas las que se encuentran en direcciones pares. Por tanto, su último dígito (en hexadecimal) siempre acaba en 0, 2, 4, 6, 8, A, C ó E

Las palabras (32 bits) ocupan 4 bytes. Sus direcciones alineadas son múltiplo de 4. En hexadecimal son las que terminan en 0, 4, 8 ó C

Por último, las dobles palabras (64 bits) ocupan 8 bytes. Sus direcciones alineadas son múltiplos de 8. En hexadecimal acaban en 0 ó 8

Modos de direccionamiento

Las intrucciones de los procesadores son números binarios que tienen un formato. En estos campos se codifica qué tipo de instrucción es y cómo se accede a los operandos. La manera en la que se codifican el acceso a los operandos se denomina modos de direccionamiento. En las instrucciones puede haber referencias a varios operandos, con modos de direccionamiento diferentes

Direccionamiento inmediato

El operando se encuentra directamente en uno de los campos de la instrucción, de forma que al leer la instrucción para ejecutarla, el operando ya se encuentra ahí (no hay que acceder otra vez a memoria ni a ningún registro)

Ejemplo: Este es el modo de direccionamiento usado con la instrucción addi del RISCV. Al ejecutarse la instrucción addi x1, x0, 245, el operando 245 está dentro de la propia instrucción. No hay que leer ni la memoria ni ningún otro registro para acceder a su valor

En los computadores iniciales, como el EDSAC o el AGC (Apolo XI), todas las constantes están almacenadas en memoria. Para cargar un valor en un registro, había que leerlo desde memoria. En los computadores modernos, el uso de constantes para inicializar registros es tan común que se incluyen instrucciones con direccionamiento inmediato. Es un ejemplo de mejora del rendimiento aplicando el principio de acelerar el caso más frecuente

Direccionamiento a registro

El operando se encuentra en un registro. En la instrucción hay un campo donde se indica explícitamente el número del registro

Ejemplo: Siguiendo con el ejemplo anterior, la instrucción addi x1, x0, 245 también usa direccionamiento a registro. En la instrucción hay dos campos con los números de los registros x1 y x0 (que son el 1 y el 0 respectivamente)

Acceso a operandos en memoria

Cuando los operandos se encuentran en memoria, hay varios modos de direccionamiento para referirse a ellos

Direccionamiento Directo

Es cuando referenciamos el operando que está en la memoria utilizando la dirección en la que está almacenado. Este es el modo de direccionamiendo usado en los primeros ordenadores, como el EDSAC o el AGC. Dentro de la instrucción hay un campo que contiene la dirección de memoria donde se encuentra el dato

En los computadores modernos apenas se usa, ya que permite un acceso a memoria muy limitado (para acceder a un mapa de memoria de 4GB necesitamos un campo de 32 bits para guardar la dirección, y necesitaríamos muchos bits para las instrucciones)

Direccionamiento indirecto

En la instrucción se especifica el número del registro que apunta al dato. Es decir, el registro que contiene la dirección del dato. Esto se expresa típicamente usando un registro entre paréntesis, para distinguirlo del direccionamiento a registro. Así, esta instrucción: load x1, (x2) carga en el registro x1 el valor de memoria apuntado por el registro x2 (x2 contiene la dirección del dato a cargar)

Direccionamiento Indirecto con desplazamiento

En la instrucción hay que especificar el número del registro con la dirección del dato, y un desplazamiento (offset) que se suma al registro anterior para obtener la dirección final de donde acceder al operando. Este es el único modo de direccionamiento que permite acceder a memoria en los RISC-V

El direccionamiento indirecto con desplazamiento se indica con la notación off(reg). Por ejemplo la instrucción load x2, 4(x1) carga en el registro x2 el dato almacenado en la posición de memoria indicada por x1 + 4

Estructuras de datos: Arrays

Un Array es una secuencia de datos del mismo tipo almacenados consecutivamente en memoria. Es la estructura de datos más básica que hay, y se utiliza muchísimo en programación

Por ejemplo, en el lenguaje python, un array que contiene los números enteros 3,5,7,9,11 se define así

A = [3,5,7,9,11]

Para acceder a los elementos de este array utilizamos índices, comenzando desde 0. Así A[0] es el primer elemento (3 en este ejemplo), A[1] el segundo (5),.... y A[4] el quinto (11)

Estos elementos del array los podemos usar en expresiones. Este ejemplo devuelve el resultado de sumar 200 al elemento de la posición 2 del array

a = A[2] + 200

cuyo resultado sería 207

En las prácticas del laboratorio ya hemos hecho ejemplos de cómo implementar expresiones sencillas en ensamblador... pero ¿cómo implementamos el acceso a un Array?

Esto depende del tipo de dato que estemos usando. Siempre necesitaremos un puntero al primer elemento del array. Se denomina dirección base y lo representaremos en los ejemplos por A. Veremos un ejemplo de arrays de palabras (32 bits)

Ejemplo: Array de palabras de 32 bits

Cada elemento del array ocupa 4 bytes. Si en A tenemos la dirección base, la primera palabra está en la dirección A + 0, la segunda palabra en A + 4, la tercera en A + 8, etc...

De manera genérica, para acceder a la palabra situada en la posición i (A[i]), hay que realizar la operación A + 4*i. Se multiplica por 4 porque cada palabra ocupa 4 bytes

El siguiente programa es un ejemplo de implementación en el RV32 de la expresión a = A[2] + 200. Supondremos que la dirección base está en el registro s0 y el resultado lo almacenamos en el registro t5 (que sería nuestra variable a)


	.data
	
	#-- Array de palabras en memoria
A:	.word 3, 5, 7, 9, 11

	.text
	
	#-- Obtener la dirección base del array
	#-- s0 = A
	la s0, A
	
	#-- Leer el elemento A[2] de memoria
	#-- Está en la direccion A + 8
	lw t0, 8(s0)  #-- t0 = A[2]
	
	#-- Calcular la expresion
	addi t1, t0, 200  #-- t1 = A[2] + 200
	
	#-- Terminar
	li a7, 10
	ecall

Lecturas del libro de referencia

Libro de referencia: "Computer Organization and Design. Hardware/Software interface. Risc-V"

Apartado 2.10: RISC-V Addressing for Wide Inmmediates and Addresses (Pag 113-121)

Ejercicios

Ejerccios para practicas y asimilar los conceptos más importantes

Ejercicio 1

El computador A utiliza ordenación little-endian. Dispone de registros de propósito general de 64-bits (x1, x2, x3....). Para leer datos de la memoria se usa direccionamiento directo. Estas son las instrucciones de carga (load) disponibles:

load_byte reg, dir : Carga del byte almacenado en la dirección dir en el registro reg
load_half reg, dir : Carga de la media palabra (16-bits) almacenada en la dirección dir en el registro reg
load_word reg, dir : Carga de la palabra (32-bits) almacenada en la dirección dir en el regisgtro reg
load_dword reg, dir : Carga de la doble palabra (64-bits) almacenada en la dirección dir en el registro reg

Se ha realizado un volcado de la memoria (en bytes) a partir de la dirección 0x10010000. Esto es lo obtenido:

Inidicar el valor (en hexadecimal) del dato que se almacena en el registro x1 al ejecutar las siguientes instrucciones:

a) load_byte x1, 0x10010003
b) load_byte x1, 0x10010005
c) load_half x1, 0x10010003
d) load_half x1, 0x10010005
e) load_word x1, 0x10010002
f) load_word x1, 0x10010005
g) load_dword x1, 0x10010001

Ejercicio 2

El computador B es igual que el computador A del ejercicio 1, pero su ordenación es de tipo Big Endian. Si el volcado de memoria es el mismo que el del ejercicio 1, inidicar el valor (en hexadecimal) del dato que se almacena en el registro x1 al ejecutar las mismas instrucciones de los apartados a-g del ejercicio 1

Ejercicio 3

El computador C tiene una arquitectura de 32-bits. La memoria que usa tiene por tanto una anchura de 32-bits, lo que le permite leer o escribir palabras de 32-bits con un único acceso. Dispone de instrucciones de load y store para acceder a datos de tipo byte, media palabra y palabra. Estas instrucciones usan direccionamiento directo. Las instrucciones de load son las siguientes:

load_byte reg, dir : Carga del byte almacenado en la dirección dir en el registro reg
load_half reg, dir : Carga de la media palabra (16-bits) almacenada en la dirección dir en el registro reg
load_word reg, dir : Carga de la palabra (32-bits) almacenada en la dirección dir en el regisgtro reg

El computador C permite acceso tanto a datos alineados como no alineados. Indica la cantidad de accesos a memoria para la lectura de los datos que se realizan al ejecutarse estas instrucciones

a) load_byte x1, 0x2003
b) load_byte x1, 0x2000
c) load_half x1, 0x2000
d) load_half x1, 0x2007
e) load_half x1, 0x200A
f) load_word x1, 0x2000
g) load_word x1, 0x2004
h) load_word x1, 0x2007
i) load_word x1, 0x200A

Ejercicio 4

El computador D es de 32 bits. La anchura de su memoria es de 32-bits. Utiliza ordenación Little-endian y puede acceder a datos situados en direcciones alineadas y no alineadas. Utiliza direccionmiento directo para el acceso a memoria. Estas son las instrucciones de almacenamiento (store) disponibles:

store_byte reg, dir : Almacenar el byte del registro reg en la dirección dir
store_half reg, dir : Almacenar la media palabra (16-bits) del registro reg en la dirección dir
store_word reg, dir : Almacenar la palabra (32-bits) del registro reg en la dirección dir

Inicialmente, los registros del procesador contienen estos valores:

Registro	Valor
x1	0xFF
x2	0x00
x3	0xCAFE
x4	0xBEBA
x5	0xD0D1
x6	0xFEDEDABA
x7	0x01020304
x8	0xABCDEF12

Tras ejecutarse este programa:

store_byte x1, 0xBA05
store_byte x1, 0xBA1F
store_byte x2, 0xBA10
store_half x3, 0xBA07
store_half x4, 0xBA0A
store_half x5, 0xBA1D
store_word x6, 0xBA01
store_word x7, 0xBA0F
store_word x8, 0xBA18

Indicar:

a) Los valores que se han almacenado en cada posición de memoria (Rellena el dibujo)

b) ¿Cuantos accesos de escritura a memoria se han realizado en total?

Ejercicio 5

En un computador con arquitectura base RV64I (Risc-V de 64 bits) se ha definido un array de dobles palabras en un lenguaje de alto nivel. Implementar en ensamblador de ese computador las instrucciones que permite calculas las siguientes expresiones. Supón que la dirección base del array A se encuentra en el registro s0, y la variable h en el registro s1

a) a = h + A[8]. Utiliza el registro t0 para la variable a
b) A[12] = h + A[8]. El resultado de h + A[8] se almacena en el propio array A, en el índice 12

Ejercicio 6

En un computador con arquitectura base RV64IM (Risc-V de 64 bits) se han definido un array A en un lenguaje de alto nivel. Se quiere implementar la siguiente expresión

A[12] = h + A[i]

Supón que la dirección base del array A se encuentra en el registro s3, la variable h en el registro s2 y la variable i en el registro s1

Implementar en ensamblador de ese computador las instrucciones que permite calcular esa expresión para los siguientes tipos de datos almacenados en el array:

a) Los elementos del array son dobles palabras
b) Los elementos del array son palabras
c) Los elementos del array son medias palabras
d) Los elementos del array son bytes

Ejercicio 7

En un computador con arquitectura base RV64IM (Risc-V de 64 bits con la extensión de multiplicación y división de enteros) se han definido dos Arrays: A y B en un lenguaje de alto nivel. Se quiere implementar la siguiente expresión

B[12] = h - A[i]

Supón que la dirección base del array B se encuentra en el registro s4, la dirección base del array A en el registro s3, la variable h en el registro s2 y la variable i en el registro s1