Associative Memory | Computer Architecture

Associative Memory – In general, a search procedure is followed in a sequence of addresses; it takes a lot of time. In this, it first chooses the address, then reads the stored content and compares it with the required data. This sequence is followed until a match occurs.

Many search algorithms are developed to reduce the searching time and are used in various types of memories discussed in the previous section. The time required to find a data word stored in memory can be minimized if the stored data can be identified for access by the content of the data itself, rather than by an address. This logic is applied in associative memory.

Associative Memory

A memory unit that is accessed by the content of data itself, rather than by an address, is called associative memory. It is also known as content-addressable memory (CAM). In this type of memory, when data is stored, no address is provided. The memory itself finds the empty location to store the data. In a similar way, there is no need to give the address for the reading operation. For reading, the content of data or a part of data is specified only.

The memory locates all words that match the specified content and marks them for reading. Associative memory can be categorized into two basic types: (i) Exact match and (ii) Comparison. The first type describes the associative memory in terms of an exact match. Whereas the second type is an enhancement of the exact match. In this, the search is based on a general comparison 

Logic and Hardware Structure

The associative memory is the only memory that is suitable for parallel searches by data association. Moreover, searches can be completed on the entire word or on a specific field within a word. The figure shows the general structure of an associative memory. Each unit of stored information is a fixed-length word. Any part of the data word can be chosen as the key. Here, the desired key is specified by a mask register.

The content of the mask register identifies the bit positions, which need not be adjacent, that define the key. The current key is compared simultaneously with all stored words, and those that match the key, output a match signal. It is applied to the select logic, which indicates a match has occurred and enables the data field to be accessed. If several entries have the same key, then the select circuit determines which data field is to be read out.

In associative memory, each memory cell must have storage capability as well as logic circuits for matching the content. For this reason, this type of memory is expensive and used in applications where the search time is very critical and must be very short.

To illustrate with the numerical example, suppose that the input register and mask register have the following bit configuration. Also consider the memory array with four memory words.

Input Register	110	10101
Mask Register	111	00000
Word 1	101	01010	No match
Word 2	100	10101	No match
Word 3	110	11100	match
Word 4	111	00010	No match

In the above example, the input register contains (11010101), and the mask register contains (111000000). Since only the three left-most bits of the mask register are 1, the corresponding three bits of the input register are compared with the memory words. Word 3 matches the unmasked input register field because the three left-most bits of the input register and the memory word are equal. The unmasked field of the input register is named the key. In this example key is 110. Here it is important to note that the memory words are scanned with respect of key only. If the key of any word is matched, the match logic is generated.

Memory Cell (1-bit)

The figure below shows the logic circuit for a 1-bit associative memory cell. The memory cell comprises a D flip-flop for data storage, a match circuit (Ex-NOR gate) to compare the flip-flop stored content with input data, and a circuit for reading and writing operations. The result of the comparison appears on the match output M. If M = 1, it denotes a match, and M = 0 denotes no match.

The memory cell is activated for both reading and writing operations by setting the select line S to 1. Writing operation is enabled through the write enable (WE) line. The stored data is read out via the Q line. When the mask control (K) line is activated (K= 1), it forces the match line to 0 and also disables the input circuits of the flip-flop by forcing the clock to 0.

Match Logic

The match logic circuit is based on the comparison algorithm of two binary numbers. To derive the match logic, first neglect the mask register key bits and compare the input register data directly with the stored data in the cells of the words. Let the word size of each word in the stored data be n, and there are m total number of words in the associative memory array, as shown in the figure below.

Two bits are equal if both are 0 or 1. The equivality of two bits can be checked through the Ex-NOR gate. The equality of two bits can be expressed logically by the Boolean function.

x_j = D_jW_ij + D_jW_ij

The above logic shows the equality of the j^th bit of the i^th word with the jth bit of the input. xj = 1 represents that the pair of bits in the j position are equal, and x_j = 0 means that the bits are unequal.

The complete input data will be considered equal to the stored data if all the x_j variables (for each cell) are equal to 1. This condition can be checked through ANDing operation. The Boolean function for this condition is given as follows:

M_i = x_ix₂x₃…………x_n

where M_i is the match logic for the i^th word in the associative memory.

Now include the key bit K_j from the mask register in the comparison logic. According to this, a comparison between the j^th bit of the input register and the j^th bit of word i must be performed if K =1, and there is no need for comparison if K = 0. This requirement is achieved by ORing each term with Kj; thus 

x_j + K_j = { x_j if K_j=1
x_j + K_j = { 1 if K_j=0

A term (x_j+K_j) will be in the 1 state if its pair of bits is not compared. This is necessary because each term is ANDed with all other terms, so that an output of 1 will have no effect. The comparison of the bits has an effect only when K_j = 1. Hence, the match logic for word i in an associative memory can now be expressed by the following Boolean expression. 

M_i = (x₁+K₁) (x₂+K₂)…………..(x_n+K_n)

The above expression shows that if the key bit (K) of any term is set to 0, then this term will not affect the match logic terms. This is because x_₂+0=x₂+1=1. However, if the key bit is 1, then the term will be either 0 or 1, depending on the value of x_j. A match will occur, and M_i will be equal to 1 if all terms are equal to 1. 

The term x_i had already been defined as D_jW_ij + D_jW_ij. Substituting this in the expression of match logic, we get 

M_i = (D₁W_i1+D₁ W_i1+K₁) (D₂W_i2+D₂ W_i2+K₂)……..(D_nW_in+D_n W_in+K_n)

M_i = Π (D_jW_ij+D_j W_ij+K_j) where j = 1 to n

Where Π is a product symbol designating the AND operation of all terms. Since there are m number of words in associative memory, the complete match logic needs m such functions, one for each word i = 1,2 m. The figure below shows the match logic for one word of associative memory. Each cell requires two NAND gates and one OR gate. Two inverters are also needed for data input and key input. The output line M will be logic 1 if a match occurs and 0 if no match occurs.

Note: If the mask register contains all 0’s. The output M will be 1 irrespective of the value of the input register or the stored word. This situation must be avoided in normal operation. 

Memory Operation

An associative memory is an array of similar cells. There is a select line to choose the particular cell for reading or writing. There are two basic operations that are performed with memory. 

Read Operation

The read operation starts with the scanning operation of the match register. The data from the associative memory word corresponding to the set bit of the match register is copied to the output register and then read by the processor. If there is more than one word in memory which matched with the input data. All the matched words will have 1’s in the corresponding bit position of the match register. Now, the matched words are read in sequence by applying a read signal to each word line whose corresponding match logic bit is set. However, in most of the applications, the associative memory chooses a key in such a way that no two identical data under a given key. In such a case, only one word may match the unmasked argument field.

Note: An all-zero output in the match register indicates that a no-match occurred and the searched data is not available in memory.

Write Operation

Write Operation shows the capability of storing the information in the associative memory. There are various modes to write in an associative memory according to the application. If the complete memory is to be loaded with new information, then writing can be done by addressing cach location in sequence. In this mode, the memory behaves as random access memory. The advantage of this is that the address for input can be decoded as in random access memory. Thus, the number of address lines can be reduced by the decoder to d lines instead of m lines. The relation between m and d is m=2^d.

In another mode, a new word is written into memory in place of the unwanted word. For this case, a special register is needed to keep a record of active and inactive words. This register is named the tag register. For every active word stored in memory, the corresponding bit in the tag register is set to 1. When the delete command is issued for a data word, the corresponding bit of that data word in the tag register is reset. Words are stored in memory by scanning the tag register until the first 0 bit is encountered. This indicates the first available inactive word and a position for writing a new word. Once the new word is stored, the corresponding bit in the tag register is set.