Memory device search system and method

• US 20020133668A1
• Filed: 03/01/2002
• Published: 09/19/2002
• Est. Priority Date: 01/15/1999
• Status: Abandoned Application

• Current Assignee: David L. Sherman
• Original Assignee: David L. Sherman
• Inventors: Sherman, David L.
• Application Number:
  US10/087,725
• Publication Number:
  US 20020133668A1
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A search system and method is provided that may implemented in a content addressable memory (CAM) using various different memory technologies including SRAMs. DRAMs or Embedded DRAMs. The search system increases the density and efficiency of the CAM by using a search tree to reduce the total number of entries that must be matched against the key.

Claims

1. A memory device, comprising:

a main data memory for storing a plurality of entries in the memory device;

an address map and overflow data memory for storing an address map of the entries in the main data memory, 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;

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;

a comparator that compares each bit of an incoming piece of data with each bit of each entry in the memory device; and

the controller further comprising search tree logic unit that sorts through the entries in the memory device to reduce the number of bit-by-bit comparisons performed by the comparator;

2. The device of claim 1, wherein the search tree logic unit further comprises a first compare and branch logic unit that compares the incoming piece of data to one or more memory bins to determine the bin in which the key is located, each bin comprising a plurality of memory locations wherein the bin has a least value and a most value indicating the range of entry values in the memory locations encompassed by the bin so that the compare and branch logic unit compares the incoming piece of data to the least and most values for each bin simultaneously to generate a selected bin.

3. The device of claim 2, wherein the search tree logic unit further comprises a second compare and branch logic unit that compares the incoming piece of data to the entries in one or more sub-bins in the bin selected by the first branch and compare logic unit, each sub-bin comprising a plurality of memory locations wherein the sub-bin has a least value and a most value indicating the range of entry values in the memory locations encompassed by the sub-bin so that the second compare and branch logic unit compares the incoming piece of data to the least and most values for each sub-bin contained in the selected bin simultaneously to generate a selected sub-bin.

4. The device of claim 3, wherein the comparator compares each bit in the incoming piece of data with each bit in the entries contained in the selected sub-bin in order to determine if a match has occurred between the entries in the memory device and the incoming piece of data.

5. A memory device, comprising:

a main data memory for storing a plurality of entries in the memory device;

an address map and overflow data memory for storing an address map of the entries in the main data memory, 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;

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 store and retrieve data from the memory;

a comparator that compares each bit of an incoming piece of data with each bit of each entry in the memory device; and

the controller further comprising search tree logic unit that sorts through the entries in the memory device to reduce the number of bit-by-bit comparisons performed by the comparator.

6. The device of claim 5, wherein the search tree logic unit further comprises a first compare and branch logic unit that compares the incoming piece of data to one or more memory bins to determine the bin in which the key is located, each bin comprising a plurality of memory locations wherein the bin has a least value and a most value indicating the range of entry values in the memory locations encompassed by the bin so that the compare and branch logic unit compares the incoming piece of data to the least and most values for each bin simultaneously to generate a selected bin.

7. The device of claim 6, wherein the search tree logic unit further comprises a second compare and branch logic unit that compares the incoming piece of data to the entries in one or more sub-bins in the bin selected by the first branch and compare logic unit, each sub-bin comprising a plurality of memory locations wherein the sub-bin has a least value and a most value indicating the range of entry values in the memory locations encompassed by the sub-bin so that the second compare and branch logic unit compares the incoming piece of data to the least and most values for each sub-bin contained in the selected bin simultaneously to generate a selected sub-bin.

8. The device of claim 7, wherein the comparator compares each bit in the incoming piece of data with each bit in the entries contained in the selected sub-bin in order to determine if a match has occurred between the entries in the memory device and the incoming piece of data.

9. A memory device, comprising:

a main data memory for storing a plurality of entries in the memory device;

an address map and overflow data memory for storing an address map of the entries in the main data memory, 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; and

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 store and retrieve data from the memory, the controller further comprising an organizer that organizes the memory into a plurality of bins wherein each bin comprises a plurality of sub-bins and each sub-bin comprises a plurality of entries in the memory device, the bins and sub-bins having a least value and a most value associated with it that indicate a minimum value and a maximum value contained in the bin or sub-bin;

the controller further comprising a search tree logic unit that compares an incoming piece of data to the plurality of bins based on the least and most values to identify a bin in which the incoming piece of data is located and that compares the incoming piece of data to the sub-bins within the identified bin to determine the sub-bin that contains an entry matching the incoming piece of data.