The Rarely Seen, But Beautiful Content-Addressable Memory (CAM)

Although The Memory Guy spends more time writing about NAND and DRAM than almost anything else, several other memory types ship in high volume that many people have never heard of.  One of these is the Content-Addressable Memory, or CAM.

CAMs are kind of backwards.  In a normal memory chip you input the address to read or write its contents.  While CAMs also perform these functions, they do something else that other memory chips can’t do.  You can input a data word without an address, and the CAM will tell you whether or not that data appears somewhere within the memory.  Some CAMs even tell you the address whose contents match the data presented to them.

Is that even useful?  Surprisingly, yes!  They are used in all memory management units (MMUs) in those processors that support virtual memories.  They are also widely used in networking applications like high-end routers and are found in AI.  I’ll go into detail later on.

CAMs Are Nothing New

These devices aren’t new!  CAM chips have been mass-produced for at least five decades.  NEC presented one, which they called an “Associative Memory” at the IEEE International Solid State Circuit Conference (ISSCC) in 1966.  It’s featured on the Semiconductor History Museum of Japan website.  (See the last entry at the bottom of the page.)  Intel was selling their 3104 4×4-bit bipolar CAM in the early 1970s.   The image at the top of this post shows the 3104 in an Intel advertisement that ran in electronics magazines in 1973.  CAM chips are about as old as DRAMs, and they significantly pre-date NAND flash, NOR flash, and EEPROM.  I haven’t researched, but I would suspect that CAMs were assembled from discrete logic (chips, or even transistors) earlier than that.  Virtual memory was invented in the late 1950s, so it’s very likely that CAMs came into being around then.

Despite the Intel 3104 and some important networking CAMs introduced in the 1980s by AMD, a quick look at the Wikipedia page for CAMs (as of the writing of this post) would give you the impression that CAM chips have only been around since the 2000s.  (Although Wikipedia is a great resource which I really like and use a lot, readers must remain aware of its limitations, since it’s a crowd-sourced site.  In brief, it’s not always right!)

How Do CAMs Work?

The data sheet below is from Intel’s 1973 Memory Design Handbook.

If you take the time to understand the logic diagram at the bottom you will see that it’s pretty straightforward: Each of its sixteen bits is a flip flop.  Each of the four 4-bit words is a vertical set of four flip flops.  The true and complement outputs of each flip flop are compared to the true and complement renditions of the same bit of the data to be matched, which is input on the left side.  If a bit matches, its two AND gates that did the match both go high.  These are wire-ORed to each other, and these wire-ORs are in turn wire-ORed to the other bit compares of that word.  As long as all of the AND gate outputs for that word are high, a match signal for that word is output at the bottom.

Applications

What are they used for?  CAMs are surprisingly common.  Any microprocessor that supports virtual memory (in other words: most of them) uses a CAM in its memory management unit (MMU), the hardware behind virtual memory.  When a memory address is accessed, the CAM compares its own contents to the upper address bits and outputs a “Match” signal if those address bits are stored in the CAM.  The address of the matched location is sent from the CAM to another memory whose contents are the physical address that the virtual memory software has mapped to the requested virtual address range.  This application doesn’t need a lot of storage, but it must be enormously fast, since it’s in the processor’s critical address-data path.

A slower application that requires significantly larger CAM arrays is the CAM that is used for network traffic routing.  This kind of CAM doesn’t tell which address matches the input address – it simply tells the outside world whether or not a match has occurred.  A bridge or router can use this to adaptively understand what data to allow across the bridge and what data to block.  Let’s explore that.

Picture a single network that connects a large number of devices.  If too many devices are attached the messages keep colliding with each other and the network traffic slows down.  It would be good to split that network into two or more pieces, and only move data from one network to the other if the other network can actually use it.

So you split the network and insert a bridge that only passes traffic that addresses a device on the other side of the bridge.  How does the bridge know which devices are on the left side, and which are on the right?  The bridge uses two CAMs to do that.

Each CAM monitors the communications on its own side of the bridge.  The first time a device accesses the network it issues a message that contains its own address (which is like the return address on an envelope).  The CAM on that side captures that address.  The CAM then monitors the traffic on the OTHER side of the bridge, and if a device on that side has a message whose outgoing address matches one of the addresses in the CAM, then the bridge lets the message pass through.  Otherwise the bridge blocks the message.

This sort of CAM uses a less elaborate cell than the old Intel design, and is built of CMOS rather than fast Schottky TTL.  One enhancement that is now common is the introduction of a third state, where each input can be ignored.  This allows a single CAM location to match a number of inputs within a range of addresses, rather than only a single address.  These are called TCAMs or “Ternary CAMs”.  TCAMs today tend to be absorbed into more complex chips dubbed “Network Processing Units” or “Network Search Engines,” a few of which are offered by Renesas through its acquisition of IDT.

CAMs are also of interest to the AI community for pattern matching.  GSI Technology makes a specialized CAM called the Gemini APU (associative processing unit) that is tailored for AI applications.  I am not well-enough versed on this application to be able to explain exactly how it is used.

Suffice it to say that CAMs are used in everyday applications without being very visible.  They’re one of a number of very interesting specialty memory types that The Memory Guy hopes to find time to cover in future posts.