Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-01-14
2002-05-14
Bragdon, Reginald G. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C707S793000
Reexamination Certificate
active
06389507
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to a system and method for performing rapid searches in a memory and in particular to a searching method and system for a content addressable memory device that permits rapid searches to be performed for data contained in the memory.
A content addressable memory (CAM) device is a memory storage device that accelerates any application that requires fast searches of data stored in the memory. For example, searching a database, a list, or for a particular pattern in database machines, image or voice recognition or computer and communication networks may be particularly well suited to using a CAM. A CAM operates by simultaneously comparing the desired information provided by the user against a list of pre-stored entries. The CAM gives an order of magnitude reduction in search time as compared to a typical random access memory (RAM).
A RAM is an integrated circuit that temporarily stores data. The data is stored in various different storage locations (addresses) and the user may specify a particular memory location to retrieve a particular piece of data. In other words, the user supplies the address and receives that data back from the RAM. In contrast, a traditional CAM stores data in random memory locations wherein each memory location has logic associated with each bit which permits comparison to a datum being searched for, commonly called a “KEY”. Each word of data also has a pair of status bits associated with it. The status bits keep track of whether the memory location has valid information or is empty and may be rewritten with new information.
Thus, the CAM stores a list of data in the memory locations. Once data is stored in the CAM, it is found by the user specifying a desired piece of data. The desired piece of data is fed into a compare register and is compared, to each bit in each memory word location simultaneously. If there is a match with a memory location, the address of that memory location, commonly called the “ASSOCIATION”, is returned to the user. In other words, with a CAM, the user may supply a desired piece of data or pattern and the CAM may return an address or addresses if that pattern or piece of data was located in the CAM. Thus, the CAM may be used to rapidly compare the desired data to the list of data in the CAM since the comparisons are done in parallel. This feature makes the CAMs particularly suited at performing different searching operations. A CAM may be generated from any number of different typical memory device technologies including dynamic RAMs (DRAMs), static RAMs (SRAMs) or embedded DRAMs.
The key problems with typical CAMs is that compare logic, that performs the comparison of the desired data to each memory location in the CAM, must be located at every memory cell location which significantly increases the number of transistors that must be dedicated to the compare logic and correspondingly decreases the amount of storage the CAM (since fewer transistors may be used for storage) assuming a fixed number of transistors on an integrated circuit. (This ratio for traditional CAM to traditional SRAM may be calculated as at least a 3× ratio of area, due to the extra compare logic. And traditional SRAM has approximately a density ratio of 7×-10× to DRAM. This leads to a 21× to 30× advantage for DRAM compared to traditional CAM.) In addition, there is a large amount of power dissipation associated with every word having a dynamic match line that cycles during every compare operation. These problems severely limit the potential size of the CAM both in terms of the silicon area and not being able to economically package the die due to the heat generated.
Thus, it is desirable to provide a novel search system and method for memory devices that overcomes the limitations and problems with typical CAM and it is to this end that the present invention is directed.
SUMMARY OF THE INVENTION
A new tree search architecture in accordance with the invention is provided that is suitable for accelerating associative searches for data stored in any memory. In a preferred embodiment, the search architecture in accordance with the invention may be implemented as a new Content Addressable Memory (CAM) in accordance with the invention. The CAM in accordance with the invention may be produced using typical commodity dynamic random access memory (DRAM) technology process or using a static random access memory (SRAM) technology process for smaller, faster memory devices. In alternative embodiments of the device in accordance with the invention, a modified DRAM technology process with improved transistors in the branching logic for speed (typically known as Embedded Dram) may be used. Thus, the invention may be implemented using various different memory technologies including DRAM, SRAM or Embedded DRAM.
The search system and method in accordance with the invention permits a very large memory (suitably arranged as described below) to be addressed as a random access memory (RAM) and then data stored in the device may be searched using a content addressable memory (CAM) technique. This arrangement in accordance with the invention will permit at least a twenty times (20×) density (size) increase compared to other typical CAM memory organizations. The size/density increase in accordance with the invention greatly increases the utility of the memory device in accordance with the invention for a broad class of applications ranging from pattern recognition, data sorting & look-up and Internet traffic routing. When the memory device in accordance with the invention is used with suitable software, this architecture will greatly speed up Internet search engines and data base servers.
The combination of a novel search method and commodity RAM in accordance with the invention constitutes a new approach that permits the CAM to achieve a lower commodity cost similar to standard DRAM organizations by eliminating match logic completely in the memory cell. Thus, standard, typical well known RAM processing technology may be used for producing these memory devices in accordance with the invention. In accordance with another aspect of the invention, portions of the RAM arrays may be configured as RAM only so that the density available as RAM when using the device in accordance with the invention is doubled compared to it's use as a CAM, which makes the device used as a RAM more flexible.
In more detail, the search system and method in accordance with the invention may add additional pointers to a B
+
-tree search algorithm/method so that the tree structure looks like a conventional CAM, but may be accessed by typical RAM addressing. When the method in accordance with the invention is implemented in an efficient hardware solution in a preferred embodiment, a commodity priced, DRAM-density CAM is produced. In more detail, the CAM in accordance with the invention may include a controller/comparator and two RAM memory blocks. The controller may organize the two RAM memory blocks and accesses them accordingly to achieve the desired CAM operation. The functions in accordance with the invention as described below may be implemented on a single silicon die or as several silicon die in a multi-chip package.
Thus, in accordance with the invention, a memory device is provided, comprising a main data memory for storing a plurality of entries in the memory device and an address map and overflow data memory for storing an address map of the entries in the main data memory wherein the address map comprising an intended address location (IAL) and an actual physical location (APL) wherein the IAL indicates the external memory address of each entry and the APL indicates that actual memory locations for each entry within the memory device. The memory device further comprises a controller for controlling the operation of the main data memory and the address map and overflow data memory using the IAL and APL in order to operate the memory as one or more of a CAM and a RAM and a comparator that compares e
Bragdon Reginald G.
Gigabus, Inc.
Gray Cary Ware & Freidenrich LLP
LandOfFree
Memory device search system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory device search system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory device search system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2842461