Memory device search system and method

• US 6,389,507 B1
• Filed: 01/14/2000
• Issued: 05/14/2002
• Est. Priority Date: 01/15/1999
• Status: Expired due to Fees

• Current Assignee: Gigabus Incorporated
• Original Assignee: Gigabus Incorporated
• Inventors: Sherman, David L.
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US09/483,206
• Time in Patent Office: 851 Days
• Field of Search: 711/108, 707/6
• 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 the 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 device as one or more of a CAM and a RAM, the controller further comprising a comparator that compares each bit of an incoming piece of data with each bit of each entry of a bin in the memory device and 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 by selecting a bin of the memory device.

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 a 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 first 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 the 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 device, the controller further comprising a comparator that compares each bit of an incoming piece of data with each bit of each entry in a bin of the memory device and 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 by selecting a bin of the memory device.

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 a 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 first 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 the 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 device, 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.