Content-addressable memory implemented using programmable logic

Details Content-addressable memory implemented using programmable logic Content-addressable memory implemented using programmable logic

2000-05-01

2001-08-21

Tokar, Michael (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Array

C326S039000, C326S041000

Reexamination Certificate

active

06278289

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to content-addressable memory (CAM), and in particular to CAM implementations on programmable logic devices.
BACKGROUND
Programmable logic devices (PLDs) are a well-known type of digital integrated circuit that may be programmed by a user (e.g., a logic designer) to perform specified logic functions. PLDs are becoming ever more popular, largely because they require less time to implement than semi-custom and custom integrated circuits.
FIG. 1
is a block diagram of one type of PLD, a field-programmable gate array (FPGA)
100
. FPGA
100
includes an array of configurable logic blocks (CLBs)
105
that are programmably interconnected to each other and to programmable input/output blocks (IOBs)
110
. The interconnections are provided by configurable horizontal and vertical interconnect lines
115
and
120
, which may be connected to one another using programmable interconnect points (PIPs)
125
. This collection of configurable elements may be customized by loading configuration data into internal configuration memory cells (not shown) that define how the CLBs, PIPS, and IOBs are configured. The configuration data may be read from memory (e.g., an external PROM) or written into FPGA
100
from an external device. The collective states of the individual memory cells then determine the function of FPGA
100
. Some FPGAs also include block RAMS
130
that may be connected to other resources using interconnect lines.
FIG. 2
is a schematic diagram of a “slice”
200
, one of two identical slices that make up an exemplary CLB in the Virtex™ family of devices available from Xilinx, Inc. All of the terminals to and from slice
200
are connected to horizontal or vertical interconnect lines (see
FIG. 1
) through which they can be programmably connected to various other components within the FPGA.
Slice
200
includes two 4-input look-up tables (LUTS)
205
A and
205
B. LUTs
205
A and
205
B are each capable of implementing any arbitrarily defined Boolean function of up to four inputs. In addition, each of LUTs
205
A and
205
B can provide a 16×1-bit synchronous RAM. Furthermore, the two LUTs can be combined to create a 16×2-bit or 32×1-bit synchronous RAM, or a 16×1-bit dual-port synchronous RAM.
Slice
200
also includes a pair of sequential storage elements
210
A and
210
B that can be configured either as edge-triggered D-type flip-flops or as level-sensitive latches. The D inputs can be driven either by LUTs
205
A and
205
B or directly from input terminals, bypassing LUTs
205
A and
205
B. Each storage element includes an initialization terminal INIT, a reverse-initialization terminal R, an enable-clock terminal EC, and a clock terminal conventionally designated using the symbol “>”. The INIT terminal forces the associated storage element into an initialization state specified during configuration; the reverse-initialization terminal R forces the storage element in the opposite state as the INIT terminal. Terminals INIT and R can be configured to be synchronous or asynchronous, and the sense of each control input can be independently inverted.
As discussed above in connection with
FIG. 1
, configuration memory cells define the functions of the various configurable elements of slice
200
. An exemplary two-input multiplexer
225
includes a pair of MOS transistors having gate terminals controlled by inverting and non-inverting terminals of configuration memory cell
230
. Other configuration memory cells used to define the functions of the remaining programmable elements of slice
200
are omitted for brevity. The use of configuration memory cells to define the function of programmable logic devices is well understood in the art.
A detailed discussion of slice
200
is not necessary for understanding the present invention, and is therefore omitted for brevity. For a more detailed treatment of the operation of many components within slice
200
, see the following U.S. patents and applications:
1. Ser. No. 08/786,818 entitled “Configurable Logic Block with AND Gate for Efficient Multiplication in FPGAs,” by Chapman et al.,
2. Ser. No. 08/754,421, now U.S. Pat. No. 5,889,413 entitled “Lookup Tables Which Double as Shift Registers,” by Bauer; and
3. Ser. No. 08/806,997, now U.S. Pat. No. 5,914,616 entitled “FPGA Repeatable Interconnect Structure with Hierarchical Interconnect Lines,” by Young, et al.
Each of the foregoing documents is incorporated herein by reference.
Content Addressable Memories (CAMs) are a class of parallel matching circuits. CAMs are traditionally employed in cache controllers for central processing units (CPUs). More recently, CAMs have become popular for use in telecommunications and networking. For example, as data packets arrive into a network router, processing of these packets typically depends on the network destination address of the packet. Because of the large number of potential addresses, and increasing performance demands, CAMs are used to retrieve the destination addresses of packets to speed data access.
CAM circuits are similar in structure to traditional random-access memory (RAM) circuits. Like RAM, CAM may be used to store binary data. Unlike RAM, however, CAM provides a “match mode” that permits all of the data in CAM to be searched in parallel. In the match mode, each memory location in the CAM is compared in parallel with some value; if the value is found in one of the memory locations, the CAM produces a “match” signal.
In some CAM implementations, it is desirable to know the address of the memory location in which data is found. Thus, rather than producing a simple match signal, some CAM implementations supply the address of the matching data. In a sense, this is functionally opposite to that of a typical RAM: that is, RAM supplies data in response to an address, whereas CAM supplies an address in response to data.
FIGS. 3A and 3B
respectively depict a RAM
300
and a CAM
310
to illustrate the relative functionality of RAM and CAM.
CAM is a type of digital circuit, and may therefore be implemented in a programmable logic device, such as FPGA
100
of FIG.
1
. The general approach is to provide an array of registers for data storage. A collection of comparators then determines whether a given input sample matches data in the registers.
FIG. 4
depicts an illustrative CAM circuit
400
implemented on an FPGA. CAM circuit
400
includes N registers R(
1
) through R(N) connected to N respective comparators C(
1
) through C(N). Registers R(
1
)-R(N) are typically made up of flip-flops, and comparators C(
1
)-C(N) are typically combinatorial logic. The flip-flops and combinatorial logic are generally located within the CLBs of an FPGA. For those implementations that require an address in addition to match notification, a decoder
410
connected to each match line M(
1
)-M(N) decodes the match-line signals to produce a unique address for each match. For a more detailed discussion of CAM designs for use in programmable logic devices, see:
1. “An Overview of Multiple CAM Designs in Virtex Family Devices,” by Jean-Louis Brelet, XAPP 201, Sep. 23, 1999 (Version 1.1);
2. “Content Addressable Memory (CAM) in ATM Applications,” by Marc Defossez, XAPP202, Sep. 23, 1999 (Version 1.1);
3. “Designing Flexible, Fast CAMs with Virtex Family FPGAs,” by Jean-Louis Brelet & Bernie New, XAPP203, Sep. 23, 1999 (Version 1.1); and
4. “Using Block SelectRAM+ for High-Performance Read/Write CAMS,” by Jean-Louis Brelet, XAPP204 (Version 1.1) Oct. 1, 1999.
The above documents are incorporated herein by reference.
Conventional FPGA CAM circuits are viable. However, implementing comparators using programmable logic produces circuits that are too large for some applications. Furthermore, FPGA CAMs that rely on flip-flops for data storage are restricted by the number of flip-flops in the FPGA. While this is adequate for small designs, larger CAMs quickly deplete the resources of even the largest FPGAS. There is therefore a need for a more space efficient means of implementing

Affiliated with

Also associated with

Rating

Content-addressable memory implemented using programmable logic does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Content-addressable memory implemented using programmable logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content-addressable memory implemented using programmable logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2466353