Editing Content-addressable memory

{{Short description|Type of computer memory}}

[[File:Content-addressable-memory.png|thumb|Content addressable memory]]
{{Memory types}}

'''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''' or '''associative storage''' and compares input search data against a table of stored data, and returns the address of matching data.<ref>{{Cite web|title=K. Pagiamtzis* and A. Sheikholeslami, Content-addressable memory (CAM) circuits and architectures: A tutorial and survey, IEEE Journal of Solid-State Circuits, pp. 712-727, March 2006.|url=https://www.eecg.utoronto.ca/~ali/papers/jssc2006-03.pdf|url-status=live|archive-url=https://web.archive.org/web/20070315145626/http://www.eecg.utoronto.ca:80/~ali/papers/jssc2006-03.pdf |archive-date=2007-03-15 }}</ref> 

CAM is frequently used in [[networking device]]s where it speeds up [[forwarding information base]] and [[routing table]] 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''.<ref>TRW Computer Division. (1963). [https://web.archive.org/web/20110805004452/http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD408276&Location=U2&doc=GetTRDoc.pdf ''First interim report on optimum utilization of computers and computing techniques in shipboard weapons control systems'']. (BuWeps-Project RM1004 M88-3U1). Alexandria, Virginia:Defence Documentation Center for Scientific and Technical Information.</ref>

==Hardware associative array==
Unlike standard computer memory, [[random-access memory]] (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]].

A similar concept can be found in the ''data word recognition unit'', as proposed by [[Dudley Allen Buck]] in 1955.<ref>[http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD408276&Location=U2&doc=GetTRDoc.pdf TRW Computer Division] {{webarchive |url=https://web.archive.org/web/20110805004452/http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD408276&Location=U2&doc=GetTRDoc.pdf |date=August 5, 2011 }}, 1963, p.&nbsp;17.</ref>

==Standards==
A major interface definition for CAMs and other [[network search engine]]s was specified in an interoperability agreement called the [[Look-Aside Interface]] (LA-1 and LA-1B) developed by the [[Network Processing Forum]].<ref>{{citation |url=https://www.oiforum.com/wp-content/uploads/2019/01/LA-1B_Final_Published_IA.pdf |title=Look-Aside (LA-1B) Interface Implementation Agreement |date=2004-08-04}}</ref>  Numerous devices conforming to the interoperability agreement have been produced by [[Integrated Device Technology]], [[Cypress Semiconductor]], [[IBM]], [[Broadcom]] and others. On December 11, 2007, the OIF published the serial look-aside (SLA) interface agreement.{{cn|date=November 2020}}

==Semiconductor implementations==
[[File:Binary CAM cell schematic.jpg|thumb|CMOS binary CAM Cell consisting of a 6T SRAM cell plus 4 comparison transistors. When the data on the search lines (SL) differs from the data stored in the cell through the bit lines (BL), the match line (ML) will be pulled low to indicate a mismatch. If none of the cells on a match line indicate a mismatched bit, the match line will remain high at the precharge level to indicate a word match. Both search lines can be held at logic '0' as a don't care search condition. Search lines and bit lines can be merged into a single pair of data lines.]]
CAM is much faster than RAM in data search applications. There are cost disadvantages to CAM, however.  Unlike a RAM [[integrated circuit|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.<ref>{{Cite journal |title=A general-purpose CMOS associative processor IC and system |journal=IEEE Micro |date=December 1992 |volume=12 |issue=6 |pages=68–78 |doi=10.1109/40.180249|s2cid=206432751 |url=https://ieeexplore.ieee.org/document/180249 |last1=Stormon |first1=C. D. |last2=Troullinos |first2=N. B. |last3=Saleh |first3=E. M. |last4=Chavan |first4=A. V. |last5=Brule |first5=M. R. |last6=Oldfield |first6=J. V.|url-access=subscription }}</ref>

In the early 2000s several semiconductor companies including [[Cypress Semiconductor|Cypress]], [[Integrated Device Technology|IDT]], [[NetLogic Microsystems|Netlogic]], Sibercore,<ref>{{Cite web|title=Sibercore Technologies - Silicon Solutions for Cyberspace|url=http://sibercore.com/|archive-url=https://web.archive.org/web/20030419174703/http://sibercore.com/|archive-date=2003-04-19|url-status=live}}</ref> 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]] offers several families of KBPs.<ref>{{Cite web|title=16nm Heterogeneous Knowledge-Based Processors (KBPs)|url=https://www.broadcom.com/products/embedded-and-networking-processors/knowledge-based/bcm15k|url-status=live|archive-url=https://web.archive.org/web/20170519075444/https://www.broadcom.com/products/embedded-and-networking-processors/knowledge-based/bcm15k |archive-date=2017-05-19 }}</ref>

==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 [[Router (computing)|router]]s.{{Citation needed|date=April 2016}} The [[Luleå algorithm]] is an efficient implementation for longest prefix match searches as required in internet routing tables.

==Ternary CAMs==
[[File:Ternary CAM cell schematic.jpg|thumb|CMOS Ternary CAM cell consisting of two 6T SRAM cells plus 4 comparison transistors. Normally opposite logic levels, either '0' and '1' or '1' and '0' will be stored in the two cells. For a don't care condition '0' will be stored in both cells so that the match line ML will not be pulled low for any combination of search line (SL) data.]]
'''Binary CAM''' is the simplest type of CAM and uses data search words consisting entirely of [[boolean logic|1s and 0s]].  '''Ternary CAM''' ('''TCAM''')<ref>{{Cite book | url=https://books.google.com/books?id=-rnt_ik0mSYC&q=TCAM&pg=PA71 | title=CCNP BCMSN Exam Certification Guide: CCNP Self-study| isbn=9781587200779| last1=Hucaby| first1=David| year=2004| publisher=Cisco Press}}</ref> allows a [[ternary logic|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.
In 2013, [[IBM]]  fabricated a nonvolatile TCAM using 2-transistor/2-resistive-storage (2T-2R) cells.<ref>Jing Li, R. Montoye, M. Ishii, K. Stawiasz, T. Nishida, K. Maloney, G. Ditlow, S. Lewis, T. Maffitt, R. Jordan, Leland Chang, P. Song, "1Mb 0.41 μm2 2T-2R cell nonvolatile TCAM with two-bit encoding and clocked self-referenced sensing", [[IEEE]] Symposium on VLSI Technology, 2013.</ref> A design of TCAM using hybrid Ferroelectric [[FeFET]] was recently published by a group of International scientists.<ref>Xunzhao Yin, Yu Qian, M. Imani, K. Ni, Chao Li, Grace Li Zhang, Bing Li, Ulf Schlichtmann, Cheng Zhuo, "Ferroelectric Ternary Content Addressable Memories for Energy-Efficient Associative Search", [[IEEE]] Transactions on Computer-Aided Design of Integrated Circuits and Systems, April 2023.</ref>

==Example applications==
Content-addressable memory is often used in [[computer networking device]]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 [[router (computing)|router]]s, where each address has two parts: the [[network prefix]], 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 prefix 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 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]] 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.<ref>[[Varghese, George]], ''Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices'', Morgan Kaufmann, 2005</ref>

Other CAM applications include:
*[[Fully associative]] cache controllers and [[translation lookaside buffer]]s<ref>{{cite journal |last=Smith |first=Alan Jay |date=September 1982 |title=Cache Memories |url=https://www.engineering.iastate.edu/~zzhang/cpre581/reading/smith-csur82-cache.pdf |journal=Computing Surveys |volume=14 |issue=3 |pages= 473–530|doi=10.1145/356887.356892 |s2cid=6023466 |archive-url=https://web.archive.org/web/20220403214856/https://www.engineering.iastate.edu/~zzhang/cpre581/reading/smith-csur82-cache.pdf |access-date=April 3, 2022 |archive-date=2022-04-03 |quote=The TLB is a small associative memory which maps virtual to real addresses.}}</ref>
*[[Database]] engines
*[[Data compression]] hardware
*[[Artificial neural networks]]<ref name="Hinton, Geoffrey E 19842">{{Cite web|url=http://repository.cmu.edu/cgi/viewcontent.cgi?article=2841&context=compsci|title=Distributed representations|last=Hinton|first=Geoffrey E.|date=1984|access-date=2017-12-14|archive-date=2016-05-02|archive-url=https://web.archive.org/web/20160502213526/http://repository.cmu.edu/cgi/viewcontent.cgi?article=2841&context=compsci|url-status=dead}}</ref>
*[[Intrusion prevention system]]s
*[[Network processor]]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]], or file system
*[[Sparse distributed memory]]
*[[Tuple space]]

==References==
{{Reflist}}

== Bibliography ==
*Anargyros Krikelis, Charles C. Weems (editors) (1997). ''Associative Processing and Processors'', IEEE Computer Science Press. {{ISBN|0-8186-7661-2}}
*{{cite patent |inventor=Hannum et al. |pubdate=2004 |title=System and method for resetting and initializing a fully associative array to a known state at power on or through machine specific state |country=US |number=6823434}}
*{{cite journal | last1 = Pagiamtis | first1 = K. | last2 = Sheikholeslami | first2 = A. | year = 2006 | title = Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey | url = https://www.pagiamtzis.com/pubs/pagiamtzis-jssc2006.pdf | journal = IEEE Journal of Solid-State Circuits | volume = 41 | issue = 3| pages = 712–727 | doi = 10.1109/JSSC.2005.864128 | bibcode = 2006IJSSC..41..712P | s2cid = 11178331 }}
* 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==
*[http://www.pagiamtzis.com/cam/camintro/ CAM Primer]
*[https://web.archive.org/web/20100308145555/http://blog.wizzy.com/post/Arithmetic-Processing-using-Associative-memory Arithmetic Processing using Associative memory]

{{Authority control}}

[[Category:Associative arrays]]
[[Category:Computer memory]]
[[Category:Computer networking]]