Content-addressable memory (CAM) is a special type of computer memory used in certain very high speed searching applications. It is also known as
associative memory,
associative storage, or
associative arrayAn associative array is an abstract data type composed of a collection of unique keys and a collection of values, where each key is associated with one value...
, although the last term is more often used for a programming data structure. (Hannum et al., 2004)
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.
Content-addressable memory (CAM) is a special type of computer memory used in certain very high speed searching applications. It is also known as
associative memory,
associative storage, or
associative arrayAn associative array is an abstract data type composed of a collection of unique keys and a collection of values, where each key is associated with one value...
, although the last term is more often used for a programming data structure. (Hannum et al., 2004)
Hardware associative array
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 an
associative arrayAn associative array is an abstract data type composed of a collection of unique keys and a collection of values, where each key is associated with one value...
.
Standards for content-addressable memories
A major interface definition for CAMs and other Network Search Elements (NSEs) was specified in an Interoperability Agreement called the
Look-Aside InterfaceThe Look-Aside Interface is a computer interface that was specified by an interface interoperability agreement produced by the Network Processing Forum. It specifies the method to interface a Network Processing Element to a Network Search Element...
(LA-1 and LA-1B) developed by the
Network Processing ForumThe Network Processing Forum was organized to facilitate and accelerate the development of next-generation networking and telecommunications products based on network processing technologies. The NPF was merged into the Optical Internetworking Forum in June 2006. The NPF produces Hardware,...
, which later merged with the
Optical Internetworking ForumThe Optical Internetworking Forum was organized to facilitate and accelerate the development of next-generation optical internetworking products. The OIF produces Electrical, Tunable Laser, Very Short Reach Hardware Interfaces. It also has produced a UNI and NNI software interface...
(OIF). Numerous devices have been produced by
Integrated Device TechnologyIDT was founded in 1980 as a semiconductor vendor. Employing approximately 2500 people worldwide, headquartered in San Jose, California, and operating a fab in Hillsboro, Oregon, the company both designs and fabricates semiconductor components. IDT operates in two business segments:...
,
Cypress SemiconductorCypress Semiconductor Corporation is a Silicon Valley-based semiconductor design and manufacturing company founded by T. J. Rodgers and others from Advanced Micro Devices. It was formed in 1982 with backing by Sevin Rosen and went public in 1986. The company initially focused on the design and...
,
IBMInternational Business Machines Corporation, abbreviated IBM, is a multinational computer technology and IT consulting corporation headquartered in Armonk, Town of North Castle, New York, United States. The company is one of the few information technology companies with a continuous history dating...
, Netlogic Micro Systems and others to the LA interface agreement. On December 11 2007, the OIF published the serial lookaside (SLA) interface agreement.
Semiconductor implementations
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 RAM
chipIn electronics, an integrated circuit is a miniaturized electronic circuit that has been manufactured in the surface of a thin substrate of semiconductor material...
, which has simple storage cells, each individual memory
bitIn computing and telecommunications a bit is a basic unit of information storage and communication . It is the maximum amount of information that can be stored by a device or other physical system that can normally exist in only two distinct states...
in a fully parallel CAM must have its own associated comparison circuit to detect a match between the stored bit and the input bit. Additionally, match outputs from each cell in the data word must be combined to yield a complete data word match signal. The additional circuitry increases the physical size of the CAM chip which increases manufacturing cost. The extra circuitry also increases power dissipation since every comparison circuit is active on every clock cycle. Consequently, CAM is only used in specialized applications where searching speed cannot be accomplished using a less costly method.
Alternative implementations
To achieve a different balance between speed, memory size and cost, some implementations emulate the function of CAM by using standard tree search or hashing designs in hardware, using hardware tricks like replication or pipelining to speed up effective performance. These designs are often used in
routerA router is a networking device whose software and hardware are usually tailored to the tasks of routing and forwarding information. For example, on the Internet, information is directed to various paths by routers....
s.
Ternary CAMs
Binary CAM is the simplest type of CAM which uses data search words comprised entirely of 1s and 0s.
Ternary CAM 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.
Holographic associative memory Holographic Associative Memory is part of the family of analog, correlation-based, associative, stimulus-response memories, where information is mapped onto the phase orientation of complex numbers operating. It can be considered as a complex valued artificial neural network. The holographic...
provides a mathematical model for "Don't Care" integrated associative recollection using complex valued representation.
Example applications
Content-addressable memory is often used in
computer networking deviceA full list of Computer networking devices are units that mediate data in a computer network. Computer networking devices are also called network equipment, Intermediate Systems or InterWorking Unit...
s. For example, when a
network switchA network switch is a computer networking device that connects network segments.The term commonly refers to a Network bridge that processes and routes data at the Data link layer of the OSI model...
receives a
data frameIn computer networking, a frame is a digital data transmission unit on the Layer 2 of the OSI model.RFC 1122 defines a frame as: "the unit of transmission in a link layer protocol, and consists of a link-layer header followed by a packet."...
from one of its ports, it updates an internal table with the frame's source
MAC addressIn computer networking, a Media Access Control address is a unique identifier assigned to most network adapters or network interface cards by the manufacturer for identification, and used in the Media Access Control protocol sublayer. If assigned by the manufacturer, a MAC address usually...
and the port it was received on. It then looks up the destination MAC address in the table to determine what port the frame needs to be forwarded to, and sends it out on 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 often used in network
routerA router is a networking device whose software and hardware are usually tailored to the tasks of routing and forwarding information. For example, on the Internet, information is directed to various paths by routers....
s, where each address has two parts: the network address, which can vary in size depending on the
subnetA subnetwork, or subnet, describes a logically visible sub-section of a single Internet network. This division groups networked computers and devices that have a common, designated IP address routing prefix into a separate network....
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.
RoutingRouting is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network, electronic data networks , and transportation networks...
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 ANDIn logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
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
The Central Processing Unit or processor is the portion of a computer system that carries out the instructions of a computer program, and is the primary element carrying out the computer's functions. This term has been in use in the computer industry at least since the early 1960s...
cache controllersA CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations...
and Translation Lookaside BufferA Translation lookaside buffer is a CPU cache that memory management hardware uses to improve virtual address translation speed. It was the first cache introduced in processors. All current desktop and server processors use a TLB. A TLB has a fixed number of slots that contain page table entries,...
s
- Database
A database is an integrated collection of logically related records or files consolidated into a common pool that provides data for one or more multiple uses....
engines
- Data compression
In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits than an unencoded representation would use, through use of specific encoding schemes.As with any communication, compressed data communication only works when both...
hardware
- Artificial neural networks
Traditionally, the term neural network had been used to refer to a network or circuit of biological neurons. The modern usage of the term often refers to artificial neural networks, which are composed of artificial neurons or nodes...
- Intrusion Prevention System
External links