Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-11-02
2002-08-13
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S216000
Reexamination Certificate
active
06434662
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to associative memory systems, and more particularly to associative memory systems that use hash functions.
BACKGROUND OF THE INVENTION
Associative memory systems can typically receive a first set of data values (“keys”) as inputs. Each key maps to an associated data value of a second set (“associated data”). Keys and their associated data form a database. The database can then searched by applying a key value to the associative memory system.
Associative memory systems have a variety of applications. Some applications may be optimized to accommodate large data structures, others may be optimized for transaction accuracy or reliability, still others may be optimized for search speed or update speed.
A content addressable memory (CAM) is one type of associative memory. While CAMs can provide relatively fast search speeds, CAMs also have a relatively high component cost. Therefore we seek to achieve high associative memory throughput using denser, less expensive random access memories (RAMs).
One way to provide fast access times is to form an associative memory system in which a RAM memory location is provided for every possible input key. One example of such a system is shown in FIG.
7
. The system of
FIG. 7
can receive input key values having “n” bits. Three key values are shown as K
1
, K
2
and K
3
. Input key values can be applied to a memory
700
that includes 2
n
entries. Consequently, for each possible input key value, there is a corresponding memory
700
entry. In the particular arrangement of
FIG. 7
, a memory
700
is a random access memory, and key values can be applied to the memory
700
as addresses. Three entries corresponding to the key values K
1
, K
2
and K
3
are shown. Each entry is accessed by an address that is a key value, and stores data associated with the key value. For example, the application of key value K
1
results in the associated data value DATA Z being provided by memory
700
.
A system with direct mapping can be feasible when the number of possible input key values is small, as for example when the key is a binary number only a few bits wide. However, for wider key values (larger key domain), direct mapping is impractical, as the resulting memory size becomes undesirably large. Further, in most applications, a system stores only a tiny fraction of all possible key value permutations. In such a case, a direct mapping approach results in inefficient use of memory.
For larger key domains, hashing is another conventional approach. A hash function translates values in one address space to values in a smaller address space. For example, if a system received 128-bit key values, such key values could be translated by a hash function into a set of 16-bit hash bucket addresses.
“Collisions” present the major practical challenge in using hash functions for associative data systems. In our 128-bit key example, if a hash function h(x):{0,1}
128→{0,1}
16
maps 128-bit keys to 16-bit hash bucket indices, a simple counting argument shows that many different possible 128-bit keys must hash to each of the 64K different addressable locations (“buckets”). If the keys stored in the associative memory system include multiple keys that hash to the same bucket b, then when an input search key hashes to bucket b, some further “collision resolution” method is required to determine which of the keys stored in bucket b—if any—matches the search key. Further, even if a bucket b holds only one key, and a search key hashes to the same bucket b, it is possible that the search key is not the same as the key stored in the table, but is an “alias” to that key, that just happens to hash to the same bucket. Therefore, even when a single candidate search result is found, the key stored in the table must be compared against the input search key to resolve such aliases.
Mathematics has proven that there does exist, for any particular static set of keys and any table size larger than the number of keys, one or more “perfect” hash functions for which no two keys in the set collide. However, mathematical results have also shown that for large key sets (thousands to millions of keys), the computational complexity of finding such perfect hash functions is extremely high; and further, the storage complexity of describing a hash function that has been found is also high. These results make perfect hashing impractical for large, dynamic data sets.
A number of conventional approaches have been proposed for addressing hash collisions. One possible approach would be to select a new hashing function, and then re-translate the entire current data structure into a new data structure without a collision. Such an approach is undesirable as it can consume considerable time and consume considerable computing resources.
Other conventional approaches for addressing hash function collisions include using a “linked-list.” A linked list can access a number of memory entries in series. An example of a system having a linked-list is shown FIG.
8
.
A key value K
21
is applied to a hash function
800
. The output of hash function
800
is an address to a memory
802
. In
FIG. 8
, three different table entries (for keys K
01
, K
97
and K
21
) map to the same memory location or hash bucket. Thus, the address for one entry
804
is shown as (H(K
01
)=H(K
97
)=H(K
21
)). The entry
804
includes one of the key values K
01
and its associated data. Further, the entry
804
is linked with a linked-list “next” pointer
806
to a second entry
808
that includes the key value K
97
and its associated data. Entry
808
is linked with a linked-list “next” pointer to a third entry
810
having the key value K
21
and its associated data. The “next” pointer of this third entry is null, indicating that there are no more entries in the list.
In the arrangement of
FIG. 8
, when the key value K
21
is applied, hash function
800
accesses entry
804
. The applied key value K
21
is compared to the stored key value K
01
. Because the key values are different, the next entry
808
at the linked-list pointer
806
is accessed. The applied key value K
21
is compared once again to the stored key value K
97
. Because the key values are again different, accesses continue according to the linked list pointer
806
. Entry
810
is then accessed. The applied key value K
21
is once again compared to the stored key value K
21
. Because the key values are the same, the corresponding associated data DATA can be provided as an output value.
A drawback to the above-described arrangement is that multiple memory read accesses and compare operations may be required, up to the length of the longest linked-list in the table in a worst case search. The length of the longest linked list depends on the table contents and can grow large.
Another conventional approach for addressing hashing function collisions includes a search tree. In one particular case, a search tree uses a number of search criteria to arrive at the desired associated data. An example of a collision resolution system having a binary search tree shown FIG.
9
.
The example of
FIG. 9
includes some of the same general items as
FIG. 8. A
key value K
31
is applied to a hash function
900
. The output of hash function
900
is an address to a memory
902
. In
FIG. 9
, four different key values (K
62
, K
45
, K
72
and K
31
) hash to the same memory entry. Thus, the address for one entry
904
is shown as (H(K
62
)=H(K
45
)=H(K
72
)=H(K
31
)). The entry
904
can activate a binary search operation to select among the data associated with the four possible key values (K
62
, K
45
, K
72
and K
31
). As just one example, a particular pointer value SEARCH can be stored in entry
904
. The output of this value SEARCH can cause a particular binary tree search to be performed.
One particular binary search arrangement is illustrated by search steps
906
-
1
to
906
-
3
d.
In search step
906
-
1
, the applied key value is compared to a predetermined value
Greene Spencer
Kedem Gershon
Gossage Glenn
Juniper Networks, Inc.
LandOfFree
System and method for searching an associative memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for searching an associative memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for searching an associative memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2892406