HOME

TheInfoList



OR:

Content-addressable memory (CAM) is a special type of
computer memory In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term ''memory'' is often synonymous with the term '' primary storag ...
used in certain very-high-speed searching applications. It is also known as associative memory or associative storage and compares input search data against a table of stored data, and returns the address of matching data. CAM is frequently used in
networking device Networking hardware, also known as network equipment or computer networking devices, are electronic devices which are required for communication and interaction between devices on a computer network. Specifically, they mediate data transmission i ...
s where it speeds up forwarding information base and
routing table In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with th ...
operations. This kind of associative memory is also used in cache memory. In associative cache memory, both address and content is stored side by side. When the address matches, the corresponding content is fetched from cache memory.


History

Dudley Allen Buck invented the concept of content-addressable memory in 1955. Buck is credited with the idea of ''recognition unit''.


Hardware associative array

Unlike standard computer memory,
random-access memory Random-access memory (RAM; ) is a form of computer memory that can be read and changed in any order, typically used to store working data and machine code. A random-access memory device allows data items to be read or written in almost the ...
(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. Thus, a CAM is the hardware embodiment of what in software terms would be called an
associative array In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an ...
. A similar concept can be found in the ''data word recognition unit'', as proposed by Dudley Allen Buck in 1955.


Standards

A major interface definition for CAMs and other network search engines was specified in an interoperability agreement called the
Look-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 (of which an NPU is an exa ...
(LA-1 and LA-1B) developed by the
Network Processing Forum The Network Processing Forum (NPF) is an industry forum that 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 ...
. Numerous devices conforming to the interoperability agreement have been produced by
Integrated Device Technology Integrated Device Technology, Inc., is an American corporation headquartered in San Jose, California, that designs, manufactures, and markets low-power, high-performance mixed-signal semiconductor solutions for the advanced communications, com ...
,
Cypress Semiconductor Cypress Semiconductor was an American semiconductor design and manufacturing company. It offered NOR flash memories, F-RAM and SRAM Traveo microcontrollers, PSoC programmable system-on-chip solutions, analog and PMIC Power Management ICs, Ca ...
, IBM,
Broadcom Broadcom Inc. is an American designer, developer, manufacturer and global supplier of a wide range of semiconductor and infrastructure software products. Broadcom's product offerings serve the data center, networking, software, broadband, wirel ...
and others. On December 11, 2007, the OIF published the serial lookaside (SLA) interface agreement.


Semiconductor implementations

CAM is much faster than RAM in data search applications. There are cost disadvantages to CAM however. Unlike a RAM chip, 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 and manufacturing cost of the CAM chip. The extra circuitry also increases power dissipation since every comparison circuit is active on every clock cycle. Consequently, CAM is used only in specialized applications where searching speed cannot be accomplished using a less costly method. One successful early implementation was a General Purpose Associative Processor IC and System. In the early 2000s several semiconductor companies including
Cypress Cypress is a common name for various coniferous trees or shrubs of northern temperate regions that belong to the family Cupressaceae. The word ''cypress'' is derived from Old French ''cipres'', which was imported from Latin ''cypressus'', the l ...
, IDT, Netlogic, Sibercore, and MOSAID introduced CAM products targeting networking applications. These products were labelled Network Search Engines (NSE), Network Search Accelerators (NSA), and Knowledge-based Processors (KBP) but were essentially CAM with specialized interfaces and features optimized for networking. Currently
Broadcom Broadcom Inc. is an American designer, developer, manufacturer and global supplier of a wide range of semiconductor and infrastructure software products. Broadcom's product offerings serve the data center, networking, software, broadband, wirel ...
offers several families of KBPs.


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. The Lulea algorithm is an efficient implementation for longest prefix match searches as required in internet routing tables.


Ternary CAMs

Binary CAM is the simplest type of CAM and 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 word, thus adding flexibility to the search. For example, a stored word of "10XX0" in a ternary CAM 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 for the 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 device Networking hardware, also known as network equipment or computer networking devices, are electronic devices which are required for communication and interaction between devices on a computer network. Specifically, they mediate data transmission in ...
s. For example, when a
network switch A network switch (also called switching hub, bridging hub, and, by the IEEE, MAC bridge) is networking hardware that connects devices on a computer network by using packet switching to receive and forward data to the destination device. A ...
receives a
data frame A frame is a digital data transmission unit in computer networking and telecommunication. In packet switched systems, a frame is a simple container for a single network packet. In other telecommunications systems, a frame is a repeating structu ...
from one of its ports, it updates an internal table with the frame's source
MAC address A media access control address (MAC address) is a unique identifier assigned to a network interface controller (NIC) for use as a network address in communications within a network segment. This use is common in most IEEE 802 networking te ...
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 prefix, which can vary in size depending on the
subnet A subnetwork or subnet is a logical subdivision of an IP network. Updated by RFC 6918. The practice of dividing a network into two or more networks is called subnetting. Computers that belong to the same subnet are addressed with an identical ...
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 prefix and which bits are the host address.
Routing Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone netw ...
is done by consulting a routing table maintained by the router which contains each known destination network prefix, the associated network mask, and the information needed to route packets to that destination. In a simple software implementation, the router compares the destination address of the packet to be routed with each entry in the routing table, performing a
bitwise AND In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic oper ...
with the network mask and comparing it with the network prefix. 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. This works if (a) the entries are stored in order of decreasing network mask length, and (b) the hardware returns only the first matching entry; thus, the match with the longest network mask ( longest prefix match) is used. Other CAM applications include: *
Fully associative A CPU cache is a memory which holds the recently utilized data by the processor. A block of memory cannot necessarily be placed randomly in the cache and may be restricted to a single cache line or a set of cache lines by the cache placement polic ...
cache controllers and
translation lookaside buffer A translation lookaside buffer (TLB) is a memory cache that stores the recent translations of virtual memory to physical memory. It is used to reduce the time taken to access a user memory location. It can be called an address-translation cache ...
s *
Database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases ...
engines *
Data compression In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressio ...
hardware *
Artificial neural networks Artificial neural networks (ANNs), usually simply called neural networks (NNs) or neural nets, are computing systems inspired by the biological neural networks that constitute animal brains. An ANN is based on a collection of connected units ...
*
Intrusion prevention system An intrusion detection system (IDS; also intrusion prevention system or IPS) is a device or software application that monitors a network or systems for malicious activity or policy violations. Any intrusion activity or violation is typically rep ...
s *
Network processor A network processor is an integrated circuit which has a feature set specifically targeted at the networking application domain. Network processors are typically software programmable devices and would have generic characteristics similar to gen ...
s *Several custom computers, like the Goodyear STARAN, were built to implement CAM.


See also

* Content-addressable network * Content-addressable parallel processor *
Content-addressable storage Content-addressable storage (CAS), also referred to as content-addressed storage or fixed-content storage, is a way to store information so it can be retrieved based on its content, not its name or location. It has been used for high-speed storage ...
, or file system * Sparse distributed memory * Tuple space


References


Bibliography

*Anargyros Krikelis, Charles C. Weems (editors) (1997). ''Associative Processing and Processors'', IEEE Computer Science Press. * * * Stormon, C.D.; Troullinos, N.B.; Saleh, E.M.; Chavan, A.V.; Brule, M.R.; Oldfield, J.V.; A general-purpose CMOS associative processor IC and system, Coherent Research Inc., East Syracuse, NY, USA, IEEE Micro, Dec. 1992, Volume: 12 Issue:6.


External links


CAM PrimerArithmetic Processing using Associative memory
{{Authority control Associative arrays Computer memory Computer networking