Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2000-02-07
2002-03-05
Robertson, David L. (Department: 2187)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C716S030000, C716S030000, C365S049130
Reexamination Certificate
active
06353332
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to Content Addressable Memory (CAM) circuits. The invention particularly relates to methods for implementing CAM functions using dual-port Random Access Memory (RAM) circuits.
BACKGROUND OF THE INVENTION
RAM circuits are well-known data storage devices that store data values in an array of addressed memory locations. To determine whether a particular data value is stored in a RAM, an address-based data searching method is performed in which data values are sequentially read out from the RAM and compared with the particular data value. Specifically, a series of addresses are transmitted to an address port of the RAM, thereby causing data values to be read out from the memory locations associated with the addresses and transmitted to an output port of the RAM. A separate comparator circuit is then used to compare each of the output data values with the searched-for data value, and to generate a signal when a match occurs. When a large number of data values is searched, such address-based search operations are very time consuming because only one data value is searched/compared each clock cycle.
CAM circuits are a second type of data storage device in which a data value is searched for by its content, rather than by its address. Data values are stored (pre-loaded) in CAM circuits such that each data value is assigned to a row or column of an array of CAM cells. To determine whether a particular data value is stored in the CAM circuit, a content-based data match operation is performed in which the searched-for data value is simultaneously compared with the rows/columns containing the pre-loaded data values. When one or more of the pre-loaded data value matches the searched-for data value, a “match” signal is generated by the CAM circuit, along with an address indicating the storage location (i.e., row or column) of the pre-loaded data value. By simultaneously comparing the searched-for data value with several pre-loaded data values, a CAM circuit is able to perform compare-and-match (hereafter “match”) operations involving several pre-loaded data values in a single clock cycle. Therefore, when compared with RAM circuits, CAM circuits significantly reduce the search time needed to locate a particular data value from a large number of data values.
PLDs are integrated circuits that typically include user-configurable circuitry that is controlled by configuration data to implement a user's logic function. The user-configurable circuitry typically includes general-purpose logic resources (e.g., look-up tables), special-purpose logic resources (e.g., RAM circuits), and interconnect resources that are connected between the general-purpose and special purpose logic resources. To program a PLD, a user typically enters a desired logic function into a Personal Computer (PC) or workstation that is configured to run one or more place-and-route software programs. These place-and-route software programs then generate a configuration solution by assigning portions of the logic function to specific logic resources of the PLD, and allocating sections of the interconnect resources to form signal paths between the logic resources, thereby causing the PLD to emulate the desired logic function. The configuration solution generated by the place-and-route software is then converted into a bitstream that is transmitted into the configuration memory of the PLD.
Early PLDs could not support on-chip CAM functions, and external dedicated CAM circuits were required. These dedicated CAM circuits were connected to the input/output (I/O) terminals of the PLDs, and CAM functions were performed in conjunction with PLD operations by transmitting information between the PLD and the dedicated CAM circuit. A problem with this arrangement is that it results in relatively slow operation speeds, and requires the use of precious PLD I/O resources that typically limits the complexity of other logic functions implemented in the PLD. Therefore, there is a demand for PLDs that perform on-chip CAM functions in order to speed up CAM operations and free-up PLD I/O resources.
More recently, advanced PLDs have been produced with dedicated CAM circuits that provide on-chip PLD CAM functions. For example, APEX™ 20KE devices, produced by Altera® Corporation, include special-purpose CAM circuits in addition to general-purpose logic resources and other special-purpose logic resources (e.g., RAM circuits).
A problem with including dedicated CAM circuitry on PLDs is that the CAM circuitry is essentially useless unless a user's logic function implements a CAM function. That is, unlike general-purpose logic circuitry, dedicated conventional CAM circuitry typically cannot be used for non-CAM logic functions. Therefore, the dedicated CAM circuitry remains idle when a user's logic function does not include a CAM function, and takes up die space on the PLD that could otherwise be used for logic operations.
Another problem with including dedicated CAM circuitry on PLDs is the conflict between the amount of die space required for the CAM circuitry and the range of CAM functions that can be implemented by the CAM circuitry (i.e., the flexibility of the CAM circuitry). A relatively simple CAM circuit requires relatively little die space, but is less likely to support a wide range of CAM functions (i.e., has little flexibility). On the other hand, a sophisticated CAM circuit is more likely to support a wide range of CAM functions, but requires a large amount of die space, thereby reducing the number of general-purpose logic resources provided on the PLD. Therefore, a PLD manufacturer must balance the flexibility of the CAM circuit with the amount of die space occupied by the CAM circuitry. Typically, such choices result in CAM features that are less than optimal. For example, the dedicated CAM circuitry provided in APEX™ 20KE devices only supports single clock cycle CAM operations to data words having widths of 32-bits or less.
What is needed is a method of implementing CAM functions without requiring dedicated, special-purpose CAM circuitry, thereby overcoming the problems described above.
SUMMARY OF THE INVENTION
The present invention provides methods for implementing a CAM function in one or more dual-port RAM circuits (referred to herein as “dual-port RAMs”). In effect, the present invention extends the range of functions that can be implemented by a dual-port RAM to include CAM functions. The methods are particularly useful when implemented in PLDs because they eliminate the need for dedicated CAM circuitry that is provided in some PLDS, thereby freeing more IC area for general purpose logic circuitry. Further, the methods described herein can be applied to multiple dual-port RAMs, thereby providing very wide and deep CAM functions that can be performed in a single clock cycle. Also provided is a PLD including a dual-port RAM that is configured in accordance with the present invention to implement CAM functions.
Dual-port RAMs, which are utilized to perform the methods of the present invention, typically include an array of memory cells arranged in rows and columns, and first and second input ports that independently access the memory array through a row decoder and a column decoder (which can be functionally combined to form a single decoder). In one embodiment, the first input port is used during CAM write and erase operations, and the second input port is used during CAM data match operations.
According to a first main aspect of the present invention, a dual-port RAM is utilized to implement CAM functions by storing decoded “one hot” data words in the columns of the RAM memory array, and then performing data match operations by reading selected rows of the RAM memory array. As used herein, each decoded “one hot” data word includes only one logic “1” bit (all other bits are logic “0”), and the decimal value of each decoded “one hot” data word is defined by the bit position of the logic “1” bit. For example, an eight-bit decoded “one hot” data word can have a decimal value between “0
Bever Patrick T.
Robertson David L.
Xilinx , Inc.
LandOfFree
Methods for implementing CAM functions using dual-port RAM does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for implementing CAM functions using dual-port RAM, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for implementing CAM functions using dual-port RAM will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2868211