PDF de programación - especificación algorítmica de sistemas secuenciales

INTRODUCCIN

Existen sistemas secuenciales demasiado complejos pa-
ra poder implementarlos con las tØcnicas vistas hasta
ahora, por ejemplo, el procesador MIPS posee 32 regis-
tros de 32 bits, lo que lleva a un total de 21024 estados.

En este tema veremos nuevas metodologas para imple-
mentar algoritmos o computaciones sobre conjuntos de
datos (vectores de n bits). En general constan de ope-
raciones combinacionales mÆs sencillas que se realizan
secuencialmente.

Ejemplos de dichos algoritmos son un sumador secuen-
cial con un œnico FA o un multiplicador a partir de un
sumador paralelo.

Esta metodologa es la que se emplea para la implemen-
tacin de los computadores digitales de propsito gene-
ral.

TambiØn se utiliza para implementar hardware espec-
co para la computacon de algoritmos concretos, sobre
todo en campos tales como el tratamiento de seæales,
procesamiento de imÆgenes, etc.

1

CONCEPTOS B`SICOS

La especicacin algortmica de sistemas secuenciales implementa
ecientemente algoritmos o computaciones que se realizan sobre
vectores de datos de n bits. Son los llamados algoritmos RT (’Regis-
ter Transfer’).

Una computacin es un conjunto de operaciones mÆs simples que
consiste en la transferencia de vectores entre registros. Durante las
transferencias se realizan las operaciones de suma, desplazamien-
to, comparacin, etc.

Esta nueva metodologa divide la implementacin en dos bloques
bÆsicos:

Camino de datos, el conjunto de elementos que implementa
el almacenamiento de datos y las funciones de transformacin
de los mismos.

Seccin de control, el sistema secuencial o autmata que
controla la transferencia y transformaciones de los datos as
como el secuenciamiento y la operacin de todo el sistema.

El esquema general se puede ver en la siguiente gura:

2

CONCEPTOS B`SICOS

El camino de datos recibe los datos del exterior (entra-
das o Data Input) y devuelve los resultados obtenidos
(salidas o Data Output).

La seccin de control recibe rdenes e informacin del
exterior (Control Input, por ejemplo, reset, begin, stop,
modo de operacin...) y enva informacin u rdenes al
exterior (Control Output, por ejemplo, end, done, over-
ow...).

Las condiciones son generadas por el camino de datos
y sirven para que la seccin de control pueda tomar de-
cisiones y realizar un control dependiente de los datos.

Ejemplos de condiciones son el signo de un operando, el
acarreo en una operacin, un desbordamiento, el valor
de un bit o una comparacin, etc.

Los puntos de control son las seæales necesarias para
realizar las transformaciones de los datos. Son genera-
das por la seccin de control e indican al camino de da-
tos el modo de operacin de todos y cada uno de sus
elementos.

Ejemplos de puntos de control son la carga de un regis-
tro, los bits de control de un MUX o de DEMUX, el tipo
de operacin de una ALU, el incremento de un contador,
el desplazamiento de un registro, el sentido del despla-
zamiento, la lectura o escritura en una memoria, etc.

3

CONCEPTOS B`SICOS

El resultado de aplicar o activar cada uno de los puntos
de control se denomina microoperacin.

El conjunto de microoperaciones que se pueden reali-
zar de forma concurrente (en paralelo) se denomina mi-
croinstruccin. Cada microinstruccin determina o equi-
vale a un estado del autmata de la seccin de control.

Cada estado debe indicar que puntos de control hay que
activar en ese momento y cual es su estado (microins-
truccin) siguiente, que en general dependerÆ de las con-
diciones actuales del camino de datos.

El conjunto o secuencia de todas las microinstrucciones
constituye un microprograma y su objetivo es imple-
mentar el algoritmo o computacin requerido.

4

CAMINO DE DATOS

Se encarga de almacenar y transformar los datos.

Consta de:

Elementos de almacenamiento.

Operadores.

Buses.

Elementos de almacenamiento: almacenan la informa-
cin. El componente bÆsico es el registro de N bits.

Registro de N bits con LOAD y CLEAR.

Operacin: if LOAD then y x
if CLEAR then y 0

5

CAMINO DE DATOS

RAM = conjunto de 2k registros de N bits que slo pue-
den accederse de uno en uno.

Operacin: if READ then y M[#(A)] else y 0

if WRITE then M[#(A)] x

siendo #(A) = Pk1

i=0

Ai 2i

Fichero de registros.

Operacin: if READ then y R[#(A)] else y 0

if WRITE then R[#(A)] x

6

CAMINO DE DATOS

Otros elementos de almacenamiento: FIFO y LIFO

Operadores: se encargan de transformar los datos.

donde OP: ADD, SUB, MAX, MIN, ...
AND, OR, NOR, EXOR, ...
SHIFT, ...

OP tambiØn puede representar una funcin mÆs compleja imple-
mentada con sistemas secuenciales (multiplicadores, divisores, ...).

Los operadores generan algunas condiciones: >, <, =, carry, over-
ow, ...

7

CAMINO DE DATOS

Buses: son las conexiones, junto con los switches necesarios, que
comunican los distintos elementos del camino de datos (registros y
operadores).

Se clasican en:

Paralelos/Serie

Unidireccionales/Bidireccionales

Dedicados/Compartidos

Directos/Indirectos

8

CAMINO DE DATOS

Switches: establecen o cortan el acceso al bus.

Unidireccionales

Bidireccionales

9

CAMINO DE DATOS

Selector: selecciona una de entre varias fuentes de da-
tos (MUX).

Distribuidor: selecciona uno de entre varios destinos de
datos (DEMUX).

10

CAMINO DE DATOS

Ejemplos de buses:

Crossbar

Bus compartido

Usando un selector.

Usando registros con salida triestado.

11

SECCIN DE CONTROL

Es el sistema secuencial o autmata que al activar los puntos de
control en el orden adecuado controla las transferencias y transfor-
maciones de los datos que tienen lugar en el camino de datos y que
implementan un algoritmo especco.

Cada estado o microinstruccin de la seccin de control indica quØ
puntos de control se activan en cada momento (salidas del autma-
ta) y, en funcin de las condiciones (entradas del autmata), cual es
el estado o microinstruccin siguiente.

La seccin de control tambiØn se puede representar mediante un
diagrama de ujo.

Existen diversos mØtodos para implementar una seccin de control:

Tablas de estado.

1.
2.
3. Microprogramacin.

Elementos de retardo.

Tablas de Estado

Es la metodologa que ya se ha explicado.

Es compleja, dicil de depurar, no es modular ni exible y es
dicil realizar modicaciones (no hai una relacin evidente entre
la implementacin y el algoritmo).

Su uso es poco frecuente.

Se denomina Lgica Aleatoria.

12

SECCIN DE CONTROL

Elementos de retardo

Implementacin sencilla y directa.

Alta velocidad pero con un alto coste hardware.

Se utiliza en sistemas relativamente pequeæos.

Cada estado se implementa con un biestable tipo D.

Exiten equivalencias entre un autmata, un diagrama de ujo y

la implementacin mediante elementos de retardo.

,

,

,

,

13

SECCIN DE CONTROL

Los puntos de control que se activan en cada estado se sacan de la
salida del biestable correspondiente.

Para activar un punto de control en dos o mÆs estados:

14

SECCIN DE CONTROL

Ejemplo: implementacin con elementos de retardo

Autmata

Diagrama de Flujo

15

SECCIN DE CONTROL

Ejemplo (cont.): implem. con elementos de retardo

16

SECCIN DE CONTROL

Ejemplo (cont.): implem. con elementos de retardo

17

SECCIN DE CONTROL

Microprogramacin

La implementacin es sencilla y estÆndar.

El hardware es casi independiente de la implemen-

tacin.

Es muy exible y versÆtil.

FÆcil de depurar, modicar y ampliar.

Su funcionamiento es relativamente lento debido a

los accesos a la memoria de control.

Apta para sistemas grandes y/o complejos.

18

SECCIN DE CONTROL

Microprogramacin

Una de las implementaciones mÆs sencillas:

19

SECCIN DE CONTROL

Memoria de control

Almacena la informacin de control necesaria para

ejecutar el algoritmo.

Su tamaæo viene dado por el nœmero de microins-
trucciones (2k) del microprograma por el nœmero de
bits por microinstruccin (m).

Se puede implementar con una ROM, PROM o RAM.

Contador de microprograma (P C)

Direcciona la memoria de control para seleccionar la

siguiente microinstruccin (I).

20

SECCIN DE CONTROL

Registro de microinstrucciones (MIR)

Almacena la I que se estÆ ejecutando actualmente.

Ejemplo de formato doble para codicar las I:
1.

Para instrucciones de salto:

El bit mÆs signicativo a cero.

El campo condicin indica la condicin a vericar.

El campo direccin de salto codica la direccin de la

siguiente I a ejecutar si la condicin es cierta.

2.

Para puntos de control:

El bit mÆs signicativo a uno.

Los puntos de control pueden estar codicados (micro-
programacin vertical) o no (microprogramacin