Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
2002-04-15
2004-10-12
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C711S102000, C711S103000, C365S185010, C365S185100, C365S189011
Reexamination Certificate
active
06804768
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to electronic circuits. More particularly, this invention relates to integrated electronic circuits and cache memory.
BACKGROUND OF THE INVENTION
Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string. Hashing may be used to index and retrieve items in a database or a memory hierarchy because it is usually faster to find the item using the shorter hashed key than to find it using the original value. It may also be used in many encryption algorithms.
The hashing algorithm is called a hash function. The hash function is used to index the original value or key and then used later each time the data associated with the value or key is to be retrieved. A good hash function also should not produce the same hash value from two different inputs. If it does, this is known as a “collision”. A hash function that offers an extremely low risk of collision may be considered acceptable.
If a collision occurs, another function may be used. This function is commonly called a “collision rule.” The collision rule generates a succession of locations until one is found that is not in use already.
It is desirable, for efficiency reasons, to have as few collisions as possible. To achieve this, the hash function should not be pre-disposed to favor any one particular location or set of locations. In other words, it should spread the potential keys around the table as evenly as possible. This is normally done by making the hash function depend on all parts of the key, computing a large integer from the key, dividing this integer by the table size, and using the remainder as the hash function value. Other commonly used hash functions are the “folding” method, the “radix transformation” method, and “digit rearrangement” method. The type of hash function used is dependent on the application it is designed for.
A hashing function may be designed for indexing memory addresses to cache memory. Designing such a hashing function requires considerable insight into the memory access behavior of the applications that will access the cache. It is not realistically feasible to simulate all possible programs to find an optimal hashing function before the CPU is fabricated. As a result, the hashing function used for indexing memory addresses to cache memory is most likely not optimal for any one application. Having a programmable hashing function would allow the flexibility of index calculation “tuning” after the CPU has been designed and implemented. A “tuned” hashing function would then allow the cache to operate more efficiently.
This invention allows for many different possible index mappings by programming the hashing function after the CPU has been designed and implemented. By running an application many times, information may be obtained about the application cache memory behavior. With this information, a more optimal hashing function may be derived and implemented for cache indexing. In turn, this results in significant improvement in cache memory performance.
SUMMARY OF THE INVENTION
An embodiment of the invention provides a circuit and method for optimizing an index hashing function in a cache memory on a microprocessor. A programmable index hashing function is designed that allows the index hashing function to be programmed after a microprocessor has been fabricated. The index hashing function may be “tuned” by running an application on the microprocessor and observing the performance of the cache memory based on the type of index hashing function used. The index hashing function may be programmed by several methods.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawing, illustrating by way of example the principles of the invention.
REFERENCES:
patent: 5117133 (1992-05-01), Luebs
patent: 5530958 (1996-06-01), Agarwal et al.
patent: 5920900 (1999-07-01), Poole et al.
patent: 6173384 (2001-01-01), Weaver
patent: 6253285 (2001-06-01), Razdan et al.
patent: 6275919 (2001-08-01), Johnson
patent: 6449613 (2002-09-01), Egolf et al.
patent: 6560599 (2003-05-01), Boa et al.
patent: 6690667 (2004-02-01), Warren
patent: 2003/0182608 (2003-09-01), Hill et al.
Hewlett--Packard Development Company, L.P.
Kim Matthew
Li Zhuo H.
Pessetto John
LandOfFree
Programmable microprocessor cache index hashing function does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programmable microprocessor cache index hashing function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable microprocessor cache index hashing function will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3329693