Content-addressable memory
|
|
Content addressable memory, or CAM, is a special type of computer memory used in certain very high speed searching applications.
Unlike standard computer memory (random access memory or RAM) in which the user supplies a memory address and the RAM returns the data word stored at that address, a CAM is designed such that the user supplies a data word and the CAM searches its entire memory to see if that data word is stored anywhere in it. If the data word is found, the CAM returns a list of one or more storage addresses where the word was found (and in some architectures, it also returns the data word, or other associated pieces of data). Thus, a CAM is the hardware embodiment of what in software terms would be called as associative array.
Because a CAM is designed to search its entire memory in a single operation, it is much faster than RAM in virtually all search applications. There are cost disadvantages to CAM however. Unlike a normal RAM chip which has simple storage cells, each individual memory bit in a fully parallel CAM must have its own embedded "match circuit". Additionally the match outputs from each cell in the data word must be cascaded together with additional circuitry to yield a complete data word match signal. These additional circuits increase the physical size of the CAM chip which exponentially adds to manufacturing cost. Power dissipation is also considerably greater. Thus CAM is only used in specialized applications where searching speed cannot be achieved in any other way.
Some CAM designs compromise on the balance between speed, memory size and cost by effectively implementing standard tree search or hashing designs in hardware, using hardware tricks like replication or pipelining to speed up effective performance. These sorts of CAM design are often used in routers.
A major interface definition for CAMs and other Network Search Elements was specified in an Interoperability Agreement called the Look-Aside Interface (LA-1 and LA-1B) developed by the Network Processing Forum. Numerous devices have been produced by Integrated Device Technology, Cypress Semiconductor, and others to the LA interface agreement.
| Contents |
Architectural Variants
Binary CAM is the simplest type of CAM which uses data search words comprised entirely of 1s and 0s. Ternary CAM is a more advanced type which allows a third matching state of "X" or "Don't Care" for one or more bits in the stored dataword, thus adding flexibility to the search. For example, a ternary CAM might have a stored word of "10XX0" which will match any of the four search words "10000", "10010", "10100", or "10110". The added search flexibility comes at an additional cost over binary CAM as the internal memory cell must now encode three possible states instead of the two of binary CAM. This additional state is typically implemented by adding a mask bit ("care" or "don't care" bit) to every memory cell.
Example Applications
Content addressable memory is often used in computer networking devices. For example, when a network switch receives a packet from one of its ports, it updates an internal table with the packet's source MAC address and the port it was received on. It then looks up the destination MAC address in the table to determine what port the packet needs to be forwarded to, and sends it out that port. The MAC address table is usually implemented with a binary CAM so the destination port can be found very quickly, reducing the switch's latency.
Ternary CAMs are used in network routers, where each address has two parts: the network address, which can vary in size depending on the subnet configuration, and the host address, which occupies the remaining bits. Each subnet has a network mask that specifies which bits of the address are the network address and which bits are the host address. Routing is done by consulting a routing table maintained by the router which contains each known destination network address, the associated network mask, and the information needed to route packets to that destination. Without CAM, the router compares the destination address of the packet to be routed with each entry in the routing table, performing a logical AND with the network mask and comparing it with the network address. If they are equal, the corresponding routing information is used to forward the packet. Using a ternary CAM for the routing table makes the lookup process very efficient. The addresses are stored using "don't care" for the host part of the address, so looking up the destination address in the CAM immediately retrieves the correct routing entry; both the masking and comparison are done by the CAM hardware.
Other CAM applications include:
- CPU cache controllers and Translation Lookaside Buffers
- Database engines
- Data compression hardware
- Artificial neural networks
See also
External links
- CAM Primer (http://www.eecg.toronto.edu/~pagiamt/cam/camintro.html)