24-06-2013, 03:52 PM
Content-Addressable memory (CAM) and its network applications
Content-Addressable.PDF (Size: 86.26 KB / Downloads: 83)
Introduction
Most memory devices store and retrieve data by addressing
specific memory locations. As a result, this path often becomes
the limiting factor for systems that rely on fast memory accesses.
The time required to find an item stored in memory can
be reduced considerably if the item can be identified for access
by its content rather than by its address. A memory that is accessed
in this way is called content-addressable memory or
CAM. CAM provides a performance advantage over other
memory search algorithms, such as binary or tree-based searches
or look-aside tag buffers, by comparing the desired information
against the entire list of pre-stored entries simultaneously,
often resulting in an order-of-magnitude reduction in the search
time.
CAM is ideally suited for several functions, including
Ethernet address lookup, data compression, pattern-recognition,
cache tags, high-bandwidth address filtering, and fast lookup
of routing, user privilege, security or encryption information
on a packet-by-packet basis for high-performance data switches,
firewalls, bridges and routers. This article discusses several of
these applications as well as hardware options for using CAM.
Basics of CAM
Since CAM is an outgrowth of Random Access Memory (RAM)
technology, in order to understand CAM, it helps to contrast it
with RAM. A RAM is an integrated circuit that stores data
temporarily. Data is stored in a RAM at a particular location,
called an address. In a RAM, the user supplies the address, and
gets back the data. The number of address line limits the depth
of a memory using RAM, but the width of the memory can be
extended as far as desired. With CAM, the user supplies the
data and gets back the address. The CAM searches through the
memory in one clock cycle and returns the address where the
data is found. The CAM can be preloaded at device startup and
also be rewritten during device operation. Because the CAM
does not need address lines to find data, the depth of a memory
system using CAM can be extended as far as desired, but the
width is limited by the physical size of the memory.
Applications
CAM can be used to accelerate any applications ranging from
local-area networks, database management, file-storage management,
pattern recognition, artificial intelligence, fully associative
and processor-specific cache memories, and disk cache
memories. Although CAM has many applications, it is particularly
well suited to perform any kind of search operations.
Following is a discussion of some of these applications.
Data Compression
Data compression removes redundancy that resides in a given
piece of information, producing an equivalent but shorter message.
CAM is well suited for data compression because the
movement of packets through local- or wide-area networks require
some form of address translation. Since a good portion
of a compression algorithm’s time is spent searching and maintaining
these data structures, replacing them with a hardware
search engine can greatly increase the throughput of the algorithm.
Network Switch
CAM is used in switch applications to extract and process the
address information from incoming data packets. In order to
switch the packet to the correct outgoing port, CAM compares
the destination address with a table of addresses stored within.
For example, a CAM might store Ethernet address and switch
port numbers. The CAM compares the received data against
the table that has been stored within, and if the comparison
yields a match, then the port identification is given and routing
control forwards the packet to the correct port or address (see
figure 2).
Memory Mapping
In a system that utilizes a dynamic memory map, CAM can be
used to store memory addresses for quicker access. For example,
in a PCI system, a single PCI device may contain up to
six memory spaces allocated in system memory. The exact location
of these spaces is determined on power-up, and their starting
locations are written into the PCI interface’s six Base Address
Registers (BAR). When a master interface requests access
a PCI device’s memory or I/O location, a CAM can be
used to quickly match the request to the address in memory, as
shown in Figure 5.
Hardware Solutions for CAM
Two types of hardware solutions exits for CAM: individual (or
discrete) components and on-chip implementations. Individual
CAM components have been available since the late 1980s as
relatively specialized memory devices. Typically, whenever
CAM was required, a designer would add the component to the
PCB board. This approach allows a designer to take advantage
of the features of the CAM, but takes additional board space.
Furthermore, the overall system performance is reduced by on/
off-chip delays of the CAM and the system device. Performance
is also affected by board delays.
On-chip implementations of CAM in the form of embedded
functions have only recently been made available. One
such example is the CAM capability offered in the latest highdensity
programmable logic devices (PLDs). The advantage of
this type of CAM is not only the board space efficiency, but
also it is the increase in performance. This performance increase
is due to elimination of On/ Off -chip delay along with
the smaller process on On-chip CAMs. In these CAM-capable
PLDs, an on-board structure called the Embedded System Block
(ESB) can implement CAM. Figure 6 shows the CAM block
diagram in one such PLD.
Conclusion
For any application that requires a fast memory search, CAM
can provide a solution. There are many manufacturers that provide
discrete CAM components, such as Music Semiconductor,
Kawasaki LSI, Netlogic Microsystems Inc and Lara Technology.
As CAM becomes more popular and system-on-a-chip
design becomes more common, intellectual property and embedded
versions of CAM such as that offered in the most advanced
PLDs have also become available. In the coming
months, CAM will enjoy increased popularity, particularly with
the growing number of communications applications that can
utilize its capabilities.