Tema 2 Definiciones y conceptos básicos



Descargar 424.76 Kb.
Página6/8
Fecha de conversión12.11.2017
Tamaño424.76 Kb.
1   2   3   4   5   6   7   8

Memorias asociativas

Tal como se indicó en la sección 2-1 al comentar los diferentes métodos de acceso, una memoria asociativa se caracteriza por el hecho de que la identificación de la posición de memoria a la que se desea acceder se realiza especificando su contenido o parte de él. Por este motivo se denominan también memorias direccionables por contenido o memorias CAM (Content Addressable Memory).

La operación básica de recuperación de información en una memoria asociativa, consiste en seleccionar las palabras de memoria que contienen una cierta información denominada clave y extraer la información asociada a dicha clave en las palabras seleccionadas.

2.5.1 Ejemplo: Concepto de memoria asociativa

Sea una memoria asociativa de 4 palabras cuyo contenido es el que se muestra en la Figura 2.48.


Figura 2.48: Ejemplo de memoria asociativa
La memoria contiene el nombre y la altura, expresada en cms, de un conjunto de personas. Si se desea conocer el nombre de las personas que miden 190 cm, se utilizará este valor como clave de acceso y el hardware de la memoria se encargará de actualizar un registro que se conoce como registro de marca. Este registro contiene un bit por cada palabra de la memoria y cada vez que se realiza una operación de búsqueda en la memoria mediante una clave de acceso determinada, se ponen a 1 los bits correspondientes a las palabras de memoria que contienen la clave especificada.
2.5.2 Estructura de una memoria asociativa

En la Figura 2.49 se muestra el diagrama de bloques de una memoria asociativa. Consiste en una matriz de celdas de memoria, con su lógica asociada, organizada en n palabras con m bits/palabra. El registro argumento A y el registro de máscara K tienen m bits cada uno y el registro de marca M consta de n bits.





Figura 2.49: Diagrama de bloques de una memoria asociativa

Cada palabra de la memoria se compara en paralelo con el contenido del registro argumento, y se pone a 1 el bit del registro de marca asociado a aquellas palabras cuyo contenido coincide con el del registro argumento. A1 final de este proceso, aquellos bits del registro de marca que están a 1 indican la coincidencia de las correspondientes palabras de la memoria asociativa y del registro argumento. El proceso de lectura se realiza mediante un acceso secuencial a las palabras de memoria cuyos bits en el registro de marca están a 1.

El registro de máscara proporciona la clave para seleccionar la parte que se desee en la palabra argumento. Si en el registro de máscara se ponen todos sus bits a 1, se comparan todas las palabras de la memoria asociativa con el registro argumento. En caso contrario, solamente se comparan aquellos bits del registro argumento cuya posición se corresponde con los bits que son 1 en el registro de máscara. En la Figura 2.50 se presenta un ejemplo.



Figura 2.50: Ejemplo de utilización de los registros

La relación entre las celdas de almacenamiento y los registros externos en una memoria asociativa se muestra en la Figura 2.51. La celda Cij corresponde al bit j de la palabra i.





Figura 2.51: Memoria asociativa de n palabras x m bits

El bit Aj (j = 1, 2, .., m) del registro argumento se compara con todos los bits de la columna j si Kj = 1. Si existe coincidencia entre todos los bits sin máscara del registro argumento y los bits de la palabra i, se hace Mi = 1. En caso contrario Mi = 0. En la Figura 2.52 se da la estructura interna de una celda Cij. Está formada por un elemento de memoria Qij y la circuitería lógica adecuada para hacer las funciones siguientes:





Figura 2.52: a) Celda básica de una memoria asociativa b) Esquema de la celda básica
a) La celda se selecciona con la señal Selección = 1 cada vez que se quiere leer o actualizar su contenido.

b) Leer el bit almacenado en la celda durante una operación de lectura (Selección = 1, Lectura/Escritura = 0)

c) Transferir al elemento de memoria el bit Aj del registro argumento durante una operación de escritura (Selección = 1, Lectura/Escritura = 1 )

d) Comparar el contenido de la celda con el correspondiente bit sin enmascarar del registro argumento, y proporcionar una salida mij para la lógica de decisión que actualiza el bit Mi del registro de marca


2.5.3 Determinación de la función lógica del registro de máscara

En la celda básica de memoria de la Figura 2.52 falta por calcular la función lógica del circuito de coincidencia entre los bits correspondientes de los registros argumento (A) y máscara (K). Se determina a partir del algoritmo de comparación de dos números binarios. Consta de dos etapas:

En la primera, no se consideran los bits del registro de máscara y se compara el contenido del registro A con los bits almacenados en las diferentes palabras de memoria. La palabra i-ésima es igual al contenido de A, si Aj = Qij, j = 1, 2, ..., m. La igualdad de dos bits se puede expresar mediante la siguiente función booleana:

Para que una palabra i sea igual a A, se tiene que cumplir que mij = 1 para j = 1, 2, ..., m. Ésta es la condición para poner a 1 el bit Mi del registro de marca. La función booleana para esta condición es:



que corresponde a la operación AND de todos los bits que se comprueban en una palabra.

En la segunda etapa, se incluye el bit Kj del registro de máscara. El requisito es que si Kj = 0  Aj y Qij no necesitan comparación. Únicamente deben compararse cuando Kj = 1. Esto se consigue haciendo la operación OR de cada término con Kj. Finalmente el bit Mi del registro de marca se puede expresar mediante la siguiente función booleana:

donde Π representa el producto lógico de los m términos. Cada término producto en la expresión anterior será igual a 1 si se verifica que su correspondiente Kj = 0. Se necesitan n de estas funciones, una para cada palabra i=1,2, ..,n.

En la Figura 2.53 se muestra el circuito de la lógica de coincidencia para una palabra de la memoria asociativa. Cada celda requiere dos puertas AND y una puerta OR. Para Aj y Kj (j = 1 .... m) sólo se necesita un inversor por columna. La salida de todas las puertas OR en las celdas de la misma palabra van a la entrada de una puerta AND común para generar la señal Mi.



Figura 2.53: Estructura de una palabra de una memoria asociativa

Mi es igual a uno si se produce coincidencia y cero en caso contrario. Si el registro de máscara contiene sólo ceros, la salida de Mi valdrá 1 independiente del valor de A o de la palabra que hay en la memoria. En el funcionamiento normal de la memoria debe evitarse esta situación.


2.5.4 Operación de lectura

Si hay más de una palabra de la memoria que concuerda con los bits sin enmascarar del registro A, todas ellas tendrán un 1 en la posición correspondiente del registro de marca. Para la operación de lectura es necesario examinar uno a uno los bits del registro de marca. Si se conectan las salidas Mi del registro de marca M directamente a las líneas de selección de la palabra correspondiente (con la señal R/W = 0) se tendrá de forma automática en las líneas de salida de la memoria asociativa el contenido de la palabra que coincide.

En la mayoría de las aplicaciones la memoria asociativa almacena una tabla que no tiene, para una máscara dada, dos filas idénticas. En este caso, solamente puede coincidir una palabra con los bits sin enmascarar del registro A. Aún más, si se excluyen de la memoria las palabras cuyo contenido sea cero, una salida de todos ceros indicará que no se ha producido coincidencia y que en consecuencia el elemento buscado no está disponible en la memoria.
2.5.5 Operación de escritura

Una memoria asociativa debe poder almacenar la información que se desee. Dependiendo de la aplicación, la escritura en este tipo de memorias puede adoptar diferentes formas.





Figura 2.54: Diagrama de bloques de un array de memoria asociativa 4 x 2
Si previamente a las operaciones de búsqueda se carga la memoria con nueva información, su escritura se puede realizar direccionando secuencialmente cada posición. Esto convierte al dispositivo en una memoria de acceso aleatorio para su escritura y en una memoria direccionable por contenido para su lectura. La ventaja en este caso es que la dirección para la entrada se puede decodificar como si fuese una memoria de acceso aleatorio. Así, en lugar de tener un bus de dirección de n líneas (una por cada palabra en memoria), se puede reducir por el decodificador a p líneas, donde n = 2n.

Si se tienen que borrar las palabras que no se necesitan e insertar nuevas palabras una a una, es necesario un registro especial para distinguir entre palabras activas e inactivas. Este registro, denominado registro etiqueta, tendrá tantos bits como palabras hay en la memoria. Para cada palabra activa (es decir, que no se desea eliminar) almacenada en la memoria, el bit correspondiente del registro etiqueta se pone a 1. Una palabra se borra de memoria poniendo a 0 su bit del registro etiqueta. Las palabras se almacenan en memoria examinando el registro etiqueta hasta que se encuentra el primer bit igual a 0; esto indica la primera palabra inactiva y una posición para escribir una nueva palabra. Cuando se almacena en memoria la nueva palabra, se transforma en palabra activa y se pone a 1 su bit en el registro etiqueta. Cuando se suprime de memoria una palabra que no se necesita, se puede poner a 0 su bit correspondiente en el registro etiqueta. Las palabras con su bit del registro etiqueta a 0 deben enmascararse con los registros A y K, de forma que sólo se comparen palabras activas.


2.5.6 Ejemplo: Diseño de una memoria asociativa

Diseñar una memoria asociativa 4 x 2. En la Figura 2.54 se muestra el diagrama de bloques de la memoria asociativa de 4 palabras con 2 bits por palabra. Cuando se selecciona la operación de lectura R/W = 0, se compara el contenido del registro argumento con las palabras cuyas líneas de selección están a 1. Las salidas de coincidencia de cada celda (mij) se aplican por filas a una puerta AND para generar así el bit de marca Mi para esa palabra. Si la operación es de escritura R/W = 1, los bits del registro argumento se almacenan en la palabra seleccionada.


Memorias compartidas

Hay ocasiones en las que el diseño de un sistema plantea la necesidad de que diferentes elementos tengan acceso a una misma unidad de memoria. Ejemplos característicos de esta situación son los accesos directos a memoria o el diseño de sistemas multiprocesadores.

En esta sección se examinan brevemente las técnicas fundamentales para compartir la utilización de una misma unidad de memoria entre varios elementos. En la Figura 2.55 se muestra la estructura general de un sistema de memoria compartida.



Figura 2.55: Diagrama de bloques de un sistema de memoria compartida
La unidad básica de estos sistemas es el árbitro, que es el elemento encargado de permitir el acceso a la unidad de memoria, en un instante dado, a cada uno de los procesadores que solicitan dicho recurso.

El árbitro se diseña de forma que asigne un tiempo de servicio, en promedio, análogo a todas las unidades que solicitan el recurso. Así, por ejemplo, en un conflicto entre los procesadores 1 y 2, el árbitro podría autorizar el acceso a la memoria al procesador I y la siguiente vez que suceda el mismo problema el acceso sería dado al procesador 2. Este criterio supone lo siguiente:

a) El árbitro tiene que guardar internamente información sobre las prioridades de servicio en caso de conflicto.

b) Esta prioridad se modifica cada vez que el árbitro atiende una petición de servicio.

El problema que se plantea es establecer la estrategia de asignación de prioridades a la petición de servicios de los distintos elementos. Los dos procedimientos más utilizados son:

• Asignación de la menor prioridad al elemento servido.

• Rotación de prioridades.
2.6.1 Asignación de la menor prioridad al elemento servido

La Tabla 2.14 muestra esta forma de reasignar las prioridades en el caso de tres procesadores que comparten una misma memoria.

En cualquier fila de la Tabla 2.14 la primera columna indica el estado presente de prioridades del árbitro, es decir, el orden actual de prioridades en el servicio a los tres procesadores que comparten la memoria. Las restantes columnas muestran, en función de las peticiones de servicio existentes, el procesador al que se le asigna el recurso y el nuevo orden de prioridades que reasigna el árbitro.

Para cualquier estado presente, la transición al próximo estado se obtiene asignando la menor prioridad al elemento servido. Resulta inmediato ver que con esta estrategia de cálculo de prioridades, la complejidad del árbitro crece de forma factorial con el número de procesadores a servir.

Así, en el caso de tres procesadores el árbitro tendrá 6 estados, y para seis procesadores se pasarán a 720 estados. Esta explosión en la complejidad del árbitro hace poco aconsejable la implantación de este método de reasignación de prioridades cuando el número de procesadores es elevado.


Estado

presente

Peticiones simultáneas de servicio




1

2

3

1,2

1,3

2,3

1,2,3































1-2-3

1

2-3-1


2

1-3-2


3

1-2-3


1

2-3-1


1

2-3-1


2

1-3-2


1

2-3-I


elemento servido

nuevo orden de prioridades



1-3-2

1

3-2-1


2

1-3-2


3

1-2-3


1

3-2-1


1

3-2-1


3

1-2-3


1

3-2-1





2-1-3

1

2-3-1


2

1-3-2


3

2-1-3


2

1-3-2


1

2-3-1


2

1-3-2


2

1-3-2





2-3-1

1

2-3-1


2

3-1-2


3

2-1-3


2

3-1-2


3

2-1-3


2

3-1-2


2

3-1-2





3-1-2

1

3-2-1


2

3-1-2


3

1-2-3


1

3-2-1


3

1-2-3


3

1-2-3


3

1-2-3





3-2-1

1

3-2-1


2

3-1-2


3

2-1-3


2

3-1-2


3

2-1-3


3

2-1-3


3

2-1-3





Tabla 2.14: Asignación de la menor prioridad al elemento servido
2.6.2 Rotación de prioridades

Con este procedimiento se intenta reducir el número de estados del árbitro y en consecuencia simplificar su diseño. En un estado cualquiera, el próximo estado se calcula rotando el orden de prioridades actual hasta que el procesador al que se acaba de dar servicio tiene la menor prioridad.

En la Tabla 2.15 se dan las transiciones de estados con esta estrategia para el mismo caso de la tabla anterior. Es fácil verificar que ahora el número de estados del árbitro coincide con el número de elementos a servir. Sin embargo, el reparto de los tiempos de servicio ya no es tan óptimo como en el caso previo.

La razón es que ahora, en general, no tiene por qué cumplirse que disminuya sólo la prioridad del procesador al que se acaba de dar servicio. Véase por ejemplo la casilla marcada con asterisco en la Tabla 2.15. (Al pasar del estado presente (1-2-3) al próximo estado (3-1-2), además de reducirse la prioridad del elemento 2, que es el procesador servido, disminuye también la del elemento 1).



Estado

presente

Peticiones simultáneas de servicio




1

2

3

1,2

1,3

2,3

1,2,3































1-2-3

1

2-3-1


2

3-1-2


3

1-2-3


1

2-3-1


1

2-3-1


(*) 2

3-1-2


1

2-3-1


elemento servido

nuevo orden de prioridades



2-3-1

1

2-3-1


2

3-1-2


3

1-2-3


2

3-1-2


3

1-2-3


2

3-1-2


2

3-1-2





3-1-2

1

2-3-1


2

3-1-2


3

1-2-3


1

2-3-1


3

1-2-3


3

1-2-3


3

1-2-3






Compartir con tus amigos:
1   2   3   4   5   6   7   8


La base de datos está protegida por derechos de autor ©composi.info 2017
enviar mensaje

    Página principal