previous | contents | next


KEYWORDS: Content addressable memory\CAM, entry name search, hash code, linked list.

With array memories, each item is accessed with an explicit address which is an index that must lie in a specific range of values, i.e., zero to n-1 where n is the number of words in the memory. With queues and stacks, items were accessed at the front and rear or at the top of the memory. Another type of memory is the content addressable memory which is a type of associative memory. The content addressable memory, as its name implies, is addressed by content rather than by an implicit or explicit address. Each cell of a content addressable memory has two parts: the entry name by which the cell is addressed, and the data associated with the entry name. With such a memory, there is no restriction on the address range and the entry names need not appear in any specific order.

A telephone directory is an example of a read-only content addressable memory\CAM, (ignoring the fact that some people often write in telephone books). The entry names are persons' names and the associated data are their telephone numbers and addresses. In one, sense, the telephone directory is organized as a conventional, linearly addressed memory; there are explicitly numbered pages with columns and lines and alphabetic keys at the tops of the pages. Various search strategies that take advantage of the alphabetic order of the entry names may be 'used to locate a particular entry name. If, however, someone were searching for a name associated with a particular telephone number, on the average, half of the directory would have to be searched to find the name associated with the given number.

There are numerous applications for content addressable memories both in hardware and software. For example, the symbol table of a compiler or assembler is such a memory. Some of the entry names are the operation codes (e.g., ADD); associated with each entry name (op code) is data used by the compiler or assembler. Consider a hardware character converter which translates character sets. The source characters would be the entry names into a CAM and the target characters would be the associated data.

Another type of organization for a CAM is by entry name and attribute; each entry name has an associated set of attributes in addition to the data (the data"' may be just the attributes). This allows multiple instances of the same entry name with different attributes for the different cases; whole classes of data could be accessed by providing an entry name and desired attributes. The data might also be processed as a function of its entry name and attributes.


Design an M(content addressable) using an M(array).


The principle design issues are memory organization, search strategy and available operations.

The following is a set of useful operations:


previous | contents | next