Fundamentos de Ordenadores II - Examen Junio 02   Depto. de Ingeniería Telemática  Universidad Carlos III de Madrid

1. Nota en el examen >= 5.0 puntos
2. Suma de las notas de los problemas 1 y 2 >= 1.1 puntos
3. Suma de las notas de los problemas 3 y 4 >= 0.8 puntos

a) Escribir la secuencia de mensajes que aparecen en pantalla durante la ejecución del programa. (1.3 puntos)
Solución:

(0,0)
(1,0)
Obstáculo al este
(1,1)
(2,1) 
(3,1)

b) Suponiendo que este programa implemente un algoritmo para salir del laberinto descrito por las etiquetas fila1, fila2, fila3, fila 4 y fila 5 (donde los unos indican las casillas que son pared), ¿qué cero cambiarías por un uno para que siguiese habiendo un camino hasta la salida, pero de forma que el algoritmo no fuese capaz de encontrarlo? (La entrada al laberinto es la casilla (0,0), y llegar a la salida significa alcanzar una posición libre en la cuarta columna). Escribir la secuencia de mensajes que escribiría el programa en ese caso. (0.4 puntos)
Solución:

Dos casos posibles:

• Cambiar (2,1):

(0,0)
(1,0)
Obstáculo al este
(1,1) 
Obstáculo al este 
(1,2) 
Obstáculo al este 
Obstáculo al sur

• Cambiar (3,1):

(0,0)
(1,0)
Obstáculo al este
(1,1) 
(2,1) 
Obstáculo al este 
Obstáculo al sur

2^o PROBLEMA (2.7 puntos)

Se dispone de un programa que manipula el nombre y los apellidos de un conjunto de usuarios. Para ello se manipulan dos tablas que comienzan en las posiciones de memoria con etiquetas nombres y apellidos y que contienen las direcciones donde comienzan el nombre y los apellidos del usuario respectivamente. El tamaño de estas tablas es idéntico y está almacenado en un número de 32 bits en una posición de memoria con etiqueta tamaño. Este tamaño es distinto de cero.

Se pide escribir los siguientes fragmentos de código documentando detalladamente la solución propuesta:

1. Rutina cuenta que recibe dos parámetros por la pila. El primero que se deposita es la dirección de comienzo de una de las tablas, y el segundo un índice, de 32 bits. El primer elemento de las tablas se encuentra en la posición con índice 0, el segundo en la posición con índice 1, etc. La rutina devuelve el número de caracteres del string apuntado en la posición de la tabla indicada por el índice. El resultado se debe devolver en el registro %eax. (0.9 puntos)

   Solución

   cuenta: push %ebp
           mov %esp, %ebp
   
           push %ebx
           push %ecx
   
           mov $0, %eax
           mov 8(%ebp), %ebx
           mov 12(%ebp), %ecx
           mov (%ecx, %ebx, 4), %ebx
   
   cond:   cmpb $0, (%ebx, %eax)
           jz done
           inc %eax
           jmp cond  
         
   done:   pop %ecx
           pop %ebx
   
           mov %ebp, %esp
           pop %ebp
           ret
             

2. Rutina suma que no recibe parámetros y calcula la suma del tamaño de todos los strings de las dos tablas y devuelve el resultado a través de la pila. Se debe utilizar la rutina del apartado anterior. Recuerde que es la rutina que llama la que hace el hueco en la pila donde la rutina llamada deja los resultados. (0.9 puntos)

   Solución

   suma:   push %ebp
           mov %esp, %ebp
   
           push %eax
           push %ebx
           push %ecx
          
           mov $0, %ebx
           mov tamaño, %ecx
   cond:   dec %ecx
           jn done
   
           push $nombre,
           push %ecx
           call cuenta
           add %eax, %ebx
           mov $apellidos, 4(%esp)
           call cuenta
           add %eax, %ebx
           add $8, %esp
           jmp cond
   
   done:   mov %ebx, 8(%ebp)
   
           pop %ecx
           pop %ebx
           pop %eax
          
           mov %ebp, %esp     
           pop %ebp
           ret
             

3. Rutina swap que recibe como parámetros a través de la pila dos índices y que intercambia la posición de los datos de dos usuarios en las tablas. No devuelve resultado. Por ejemplo, si en la posicion i están los datos "nombre1" y "apellidos1", y en la posición j los datos "nombre2" y "apellidos2" en sus respectivas tablas, tras ejecutar esta rutina con parámetros (i, j) los datos se han intercambiado de posición ("nombre1"y "apellidos1" en posición j y "nombre2" y "apellidos2" en posición i). (0.9 puntos)

   Solución

   La observación clave a realizar es que cambiar los strings de posición tan solo requiere intercambiar las direcciones en las tablas. No es necesario mover los strings de un lugar a otro de memoria.

   swap:   push %ebp                       /* Guardar y asignar ebp */
           mov %esp, %ebp
   
           push %eax
           push %ebx
           push %ecx
           push %edx
          
           mov 8(%ebp), %eax               /* Almacena el indice i en eax */
           mov 12(%ebp), %ebx              /* Almacena el indice j en ebx */
   
           mov nombre(, %eax, 4), %ecx     /* Mover el primer nombre a ecx */
           mov nombre(, %ebx, 4), %edx     /* Mover el segundo nombre a edx */
         
           mov %ecx, nombre(, %ebx, 4)     /* Mover %ecx a la posicion j */
           mov %edx, nombre(, %eax, 4)     /* Mover %edx a la posicion i */
   
           mov apellidos(, %eax, 4), %ecx  /* Mover el primer apellido a ecx */
           mov apellidos(, %ebx, 4), %edx  /* Mover el segundo apellido a edx */
   
           mov %ecx, apellidos(, %ebx, 4)  /* Mover %ecx a la posicion j */
           mov %edx, apellidos(, %eax, 4)  /* Mover %edx a la posicion i */
   
           pop %edx
           pop %ecx
           pop %ebx
           pop %eax
          
           mov %ebp, %esp
           pop %ebp                        /* Restaurar EBP */
           ret	
             

Se desea modificar el comportamiento de la instrucción ADD de Símplez. El comportamiento que se desea que tenga esta nueva versión es el siguiente. Suma dos palabras de MP, dejando el resultado en el acumulador. Para  poder indicar las direcciones de las dos palabras de MP que se desea sumar, la instrucción ADD se codifica ahora por medio de dos palabras consecutivas de MP. La primera tiene en los tres bits más significativos el código de operación (010) y en los 9 bits restantes la dirección de la primera palabra de MP que se desea sumar. Los tres bits más significativos de la segunda palabra de la instrucción valen 000. Los 9 bits menos significativos de la segunda palabra de la instrucción contienen la dirección de la segunda palabra de MP a sumar. La ruta de datos no cambia.    

Se pide:

1. Escriba un microprograma que implemente esta nueva versión de la instrucción ADD.  (0.6 puntos)
2. Se desea diseñar un secuenciador cableado para esta nueva versión de Símplez. Se realiza un diseño con biestables que permite conocer el estado de ejecución. Dicho estado de ejecución indica exclusivamente el número de orden del ciclo de reloj de la instrucción (primer ciclo de reloj de la instrucción, segundo ciclo de reloj, etc.), independientemente de la instrucción que se está ejecutando. El secuenciador no contiene ningún elemento de memoria adicional. ¿Sería posible en estas condiciones realizar dicho secuenciador cableado? Razone la respuesta. (0.6 puntos)
   

Solución:

APARTADO 1

El microprograma a realizar esencialmente consiste en el microprograma de la instrucción LD seguido del microprograma de la instrucción ADD.

APARTADO 2

Si sería posible realizar el secuenciador cableado en las condiciones indicadas. Recuérdese que los circuitos combinacionales que generan las microórdenes toman como entradas el código de operación de la instrucción, el estado de ejecución y el biestable Z. Estas informaciones estarían disponibles, salvo en el caso de la nueva instrucción ADD, en la cuál a partir del sexto ciclo de reloj (inmediatamente después del ciclo de reloj en el que se lee la microinstrucción de dirección d+10) el código de operación desaparece, ya que la nueva lectura de MP escribe 000 en CO. Pero como no hay ninguna otra instrucción con más de 4 ciclos de reloj, una vez superado el quinto ciclo sabemos que se trata de la instrucción ADD aunque haya 000 en CO.

4º PROBLEMA (2 puntos)

Se desea diseñar una versión de Símplez, que llamaremos Símplez-SIMD, en la que se modifica el repertorio de instrucciones de Símplez, añadiendo tres instrucciones SIMD (Single Instruction Multiple Data). Las instrucciones SIMD se caracterizan porque la ejecución de una única instrucción se realiza sobre varios datos. En nuestro caso, se sustituye el registro AC de Símplez por 16 registros de próposito general de 16 bits (identificados por R[0] a R[15]), encapsulados en una Memoria Local, que llamaremos ML. Las nuevas instrucciones STS, LDS y ADDS, que sustituyen a ST, LD y ADD realizan operaciones sobre 1 a 16 datos de 16 bits. La nueva Memoria Principal, MP, tiene una capacidad de 65536 palabras de 16 bits, es decir, utiliza direcciones y datos de 16 bits. Por lo tanto, tanto el bus de direcciones como el bus de datos son de 16 bits.

Concretamente la funcionalidad y la sintaxis en ensamblador de las instrucciones STS, LDS y ADDS es la siguiente:

- Instrucción STS(m) .n, /p. Copia el contenido del registro R[n] en la palabra de MP de dirección p; copia el contenido del registro R[n+1] en la palabra de MP de dirección p+1; ...;copia el contenido del registro R[n+m-1] en la palabra de MP de dirección p+m-1. Por ejemplo la instrucción:
 

STS(4) .3, /67

- Instrucción LDS(m) .n, /p. Copia el contenido de la palabra de MP de dirección p en el registro R[n]; copia el contenido de la palabra de MP de dirección p+1 en el registro R[n+1]; ...; copia el contenido de la palabra de MP de dirección p+m-1 en el registro R[n+m-1]. Por ejemplo la instrucción:
 

LDS(4) .3, /67

- Instrucción ADDS(m) .n, /p. Suma el contenido de la palabra de MP de dirección p con el contenido del registro R[n], dejando el resultado en R[n]; suma el contenido de la palabra de MP de dirección p+1 con el contenido del registro R[n+1], dejando el resultado en R[n+1]; ...;suma el contenido de la palabra de MP de dirección p+m-1 con el contenido del registro R[n+m-1], dejando el resultado en R[n+m-1]. Por ejemplo la instrucción:

ADDS(4) .3, /67

El formato de instrucciones es el siguiente. Las instrucciones pueden ocupar una o dos palabras (16 o 32 bits). Las instrucciones CLR, DEC y HALT, cuya funcionalidad es la misma que en Símplez (en el caso de CLR y DEC, ahora hace falta especificar el registro de ML sobre el que operan), ocupan una sóla palabra. Las demás instrucciones ocupan dos palabras. Los campos del formato de instrucciones vienen presentados en la figura 1.
 

LD /400
ADD /408
ST /416
LD /401
ADD /409
ST /417
LD /402
ADD /410
ST /418
LD /403
ADD /411
ST /419
LD /404
ADD /412
ST /420
LD /405
ADD /413
ST /421
HALT

• Registro CO, de 3 bits en el que se almacena el campo CO de la instrucción. Toma su entrada de las líneas D13 a D15 del bus de datos (numeramos las 16 líneas del bus de datos de la D0 a la D15, siguiendo el convenio extremista menor). Dispone de una entrada de habilitación (microorden eco), que cuando está activa hace que se cargue en el registro CO el dato disponible en su entrada. Su salida está conectada al secuenciador.
• Registro CR, de 4 bits en el que se almacena el campo CR de la instrucción. Toma su entrada de las líneas D9 a D12 del bus de datos. Dispone de una entrada de habilitación (microorden ecr), que cuando está activa hace que se cargue en el registro CR el dato disponible en su entrada. Asimismo, dispone de una entrada de control (microorden incr), que cuando está activa hace que se incremente el contenido del registro CR. Su salida está conectada a la entrada dirml de ML, para poder seleccionar un registro de ML.
• Registro N, de 4 bits en el que se almacena el campo NR de la instrucción. Toma su entrada de las líneas D5 a D8 del bus de datos. Dispone de una entrada de habilitación (microorden enn), que cuando está activa hace que se cargue en el registro N el dato disponible en su entrada. Asimismo, dispone de una entrada de control (microorden decn), que cuando está activa hace que se decremente el contenido del registro N.
• Registro CD, de 16 bits en el que se almacena el campo CD de la instrucción. Toma su entrada del bus de datos. Dispone de una entrada de habilitación (microorden ecd), que cuando está activa hace que se cargue en el registro CD el dato disponible en su entrada. Su salida está conectada al bus Ai a través de una puerta triestado controlada por la microorden scd.

Para completar el diseño, debemos pensar en las operaciones que se realizarán en la ruta de datos para ejecutar cada instrucción. Para las instrucciones no SIMD el proceso es el mismo que en Símplez, salvo que, cuando sea necesario utilizar un registro de ML se utilizará el valor del registro CR para seleccionarlo.

En el caso de las instrucciones SIMD se plantea su ejecución siguiendo los siguientes pasos:

1. Si (N) + (CR) > 15 la instrucción termina sin hacer nada.
2. Se lleva el contenido de CD a RA.
3. Se realiza una copia o suma. La dirección de MP está en RA. La dirección de ML está en CR. Hay que poder llevar la salida de ML (sal) al bus de datos, controlada por una puerta triestado, para el caso de STS. En el caso de ADDS o LDS, el dato a guardar en ML se toma de la UAL y el dato leído de MP es transfiere a la entrada 2 de la UAL (esto ya venía en el enunciado). En el caso de ADDS, la salida de ML debe de estar conectada a la entrada 1 de la UAL para poder efectuar la suma.
4. Si (N)=0 hemos terminado. En caso contrario se decrementa N, se incrementa CR, se incrementa RA y se vuelve al punto 3.

Para poder realizar estas operaciones es necesario añadir lo siguiente a la ruta de datos:

• Entradas adicionales al secuenciador que le permitan saber que microórdenas generar en cada momento. Lo que tiene que saber el secuenciador es: de que instrucción se trata y el valor del biestable Z. Además, para las instrucciones SIMD hace falta saber 1) si (N) + (CR) > 15 (la instrucción no hace nada) y 2) si (N)=0 para saber si terminar la instrucción o continuar. Por lo tanto se añaden al secuenciador dos entradas. Una de ellas es la generada por el bloque llamado "N=0". Se obtiene por medio de una puerta nor con 4 entradas que están conectadas a los 4 bits del registro N. La seguna es la generada por el bloque llamado "N + CR > 15". Este bloque esta formado por un sumador de 4 bits; las entradas al sumador se toman de N y CR; la salida del bloque es el bit de acarreo del sumador.
• Conectar la salida de ML a la entrada 1 de la UAL.
• Conectar la salida de ML al bus D a través de una puerta triestado controlada por la microorden sml.
• Añadir una entrada de control al registro RA (microorden inra) para poder incrementar el registro RA.

Las figuras a continuación muestran los circuitos de los bloques "N=0" y "N + CR > 15".