Content-addressable memory
Encyclopedia
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 array, although the last term is more often used for a programming data structure. (Hannum et al., 2004) Several custom computers, like the Goodyear STARAN
, were built to implement CAM, and were referred to as associative computers.
.
The data word recognition unit was proposed by Dudley Allen Buck
in 1955.
(LA-1 and LA-1B) developed by the Network Processing Forum
, which later merged with the Optical Internetworking Forum
(OIF). Numerous devices have been produced by Integrated Device Technology
, Cypress Semiconductor
, IBM
, Netlogic Micro Systems and others to the LA interface agreement. On December 11, 2007, the OIF published the serial lookaside (SLA) interface agreement.
, which has simple storage cells, each individual memory bit
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.
Holographic associative memory
provides a mathematical model for "Don't Care" integrated associative recollection using complex valued representation.
s. For example, when a network switch
receives a data frame
from one of its ports, it updates an internal table with the frame'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 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 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:
Goodyear MPP
The Goodyear Massively Parallel Processor was amassively parallel processing supercomputer built by Goodyear Aerospacefor the NASA Goddard Space Flight Center.It was designed to deliver enormous computational power at lower cost than...
, were built to implement CAM, and were referred to as associative computers.
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 arrayAssociative array
In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....
.
The data word recognition unit was proposed by Dudley Allen Buck
Dudley Allen Buck
Dr. Dudley Allen Buck was an electrical engineer and inventor of components for high-speed computing devices in the 1950s. He is best known for invention of the cryotron, a superconductive computer component that is operated in liquid helium at a temperature near absolute 0...
in 1955.
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 InterfaceLook-Aside Interface
The 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 Forum
Network Processing Forum
The 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 Forum
Optical Internetworking Forum
The Optical Internetworking Forum is a non-profit, member-driven organization founded in 1998. It promotes the development and deployment of interoperable networking solutions and services through the creation of Implementation Agreements for optical networking products, network processing...
(OIF). Numerous devices have been produced by Integrated Device Technology
Integrated Device Technology
Integrated Device Technology, Inc. is a publicly traded corporation headquartered in San Jose, California, that designs, manufactures, and markets low-power, high-performance mixed-signal semiconductor solutions for the advanced communications, computing, and consumer industries. The company...
, Cypress Semiconductor
Cypress Semiconductor
Cypress 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...
, IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
, 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 chipIntegrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
, which has simple storage cells, each individual memory bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible 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 routers.Ternary CAMs
Binary CAM is the simplest type of CAM which uses data search words consisting entirely of 1s and 0s. Ternary CAM (TCAM) 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
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 deviceComputer networking device
'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 switch
Network switch
A network switch or switching hub is a computer networking device that connects network segments.The term commonly refers to a multi-port network bridge that processes and routes data at the data link layer of the OSI model...
receives a data frame
Data frame
In computer networking and telecommunication, a frame is a digital data transmission unit or data packet that includes frame synchronization, i.e. a sequence of bits or symbols making it possible for the receiver to detect the beginning and end of the packet in the stream of symbols or bits...
from one of its ports, it updates an internal table with the frame's source MAC address
MAC address
A Media Access Control address is a unique identifier assigned to network interfaces for communications on the physical network segment. MAC addresses are used for numerous network technologies and most IEEE 802 network technologies, including Ethernet...
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 routers, where each address has two parts: the network address, which can vary in size depending on the subnet
Subnetwork
A subnetwork, or subnet, is a logically visible subdivision of an IP network. The practice of dividing a network into subnetworks is called subnetting....
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
Routing
Routing 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 AND
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
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:
- CPUCentral processing unitThe central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
cache controllersCPU cacheA 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 BufferTranslation Lookaside BufferA translation lookaside buffer is a CPU cache that memory management hardware uses to improve virtual address translation speed. All current desktop and server processors use a TLB to map virtual and physical address spaces, and it is ubiquitous in any hardware which utilizes virtual memory.The...
s - DatabaseDatabaseA database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
engines - Data compressionData compressionIn computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
hardware - Artificial neural networksNeural networkThe term neural network was traditionally 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
See also
- Associative arrayAssociative arrayIn computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....
- Content addressable networkContent addressable networkThe Content Addressable Network is a distributed, decentralized P2P infrastructure that provides hash table functionality on an Internet-like scale...
- Content Addressable Parallel ProcessorContent Addressable Parallel ProcessorA Content Addressable Parallel Processor is a type of parallel processor which uses content-addressing memory principles. CAPPs are intended for bulk computation. The syntactic structure of their computing algorithm are simple, whereas the number of concurrent processes may be very large, only...
- Content Addressable storageContent-addressable storageContent-addressable storage, also referred to as associative storage or abbreviated CAS, is a mechanism for storing information that can be retrieved based on its content, not its storage location. It is typically used for high-speed storage and retrieval of fixed content, such as documents stored...
, or file system - Tuple spaceTuple spaceA tuple space is an implementation of the associative memory paradigm for parallel/distributed computing. It provides a repository of tuples that can be accessed concurrently. As an illustrative example, consider that there are a group of processors that produce pieces of data and a group of...
External links
- CAM Primer
- Content-addressable memory (CAM) circuits and architectures: A tutorial and survey
- Aspex - Computer architecture built around associative memory
- Initiation of Serial Lookaside specification effort (near bottom of page 1)
- OIF Serial Lookaside interface agreement
- Arithmetic Processing using Associative memory