Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Algorithm and Hardware for Searching on a Key in a Content Addressable Memory

IP.com Disclosure Number: IPCOM000080412D
Original Publication Date: 1973-Dec-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 62K

Publishing Venue

IBM

Related People

Ouchi, NK: AUTHOR

Abstract

Fig. 1 shows the algorithm for searching on a key in a contents addressable memory. The algorithm will search through the memory on the key to obtain the address of the information having that key. A content addressable memory is organized such that the same bit in each data word is located in a column, where the bits of the same word are located at the same position in each column. Therefore, if the data words have a length of twenty bits and the memory is capable of storing 100 data words, each column will have 100 location addresses and the data word will be stored with one bit in each column, that bit having the same address in each column across all columns.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Algorithm and Hardware for Searching on a Key in a Content Addressable Memory

Fig. 1 shows the algorithm for searching on a key in a contents addressable memory. The algorithm will search through the memory on the key to obtain the address of the information having that key. A content addressable memory is organized such that the same bit in each data word is located in a column, where the bits of the same word are located at the same position in each column. Therefore, if the data words have a length of twenty bits and the memory is capable of storing 100 data words, each column will have 100 location addresses and the data word will be stored with one bit in each column, that bit having the same address in each column across all columns.

It is desirable to be able to search the data word on a key field made up of a plurality of key bits. The purpose of this algorithm is to perform that search such that the address of the first data word having the key field will be found and the address of that data word presented.

The algorithm shown in Fig. 1 is clearly shown in the flow chart. Basically, the limit address is first set to zero and then the key bits are compared to the bits in each address of the associated data columns for each key bit. The address of the first successful comparison is indicated for each column, where the address found is greater than the limit address. If the address of all the columns is equal, then the key has been found and the address presented. If all the columns are not equal but all the column addresses less than the maximum address are being inhibited, then the key was not found and the scan was not successful.

Where all the column addresses less than the largest address are not inhibited, then the limit address is changed to indicate the highest data column address that was found during the last set of comparisons. This will basically allow those columns indicating addresses which were less than the highest indicating address, to further search for the next compare at an address greater than the new limit address. By following this routine, either the key will be found or the search will be unsuccessful, because the key is not present.

Fig. 2 shows a hardware system for carrying out the algorithm of Fig. 1. Fig. 2 shows a contents addressable storage having three data words, where each word consists of two bits. The circuitry associated with each column is included in block number 1.

Within block number 1, there exists flip-flops 2, 3 and 4 for storing the three data bits associated with the firs...