Address index recovery using hash-based exclusive or

• US 9,367,454 B2
• Filed: 08/15/2013
• Issued: 06/14/2016
• Est. Priority Date: 08/15/2013
• Status: Active Grant

• Current Assignee: Ampere Computing LLC
• Original Assignee: Applied Micro Circuits Corporation (MACOM Technology Solutions Holdings, Inc.)
• Inventors: Svendsen, Kjeld
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): Doan, Khoa D
• Application Number:
  US13/967,607
• Publication Number:
  US 20150052286A1
• Time in Patent Office: 1,034 Days
• Field of Search: 711/216, 711/E12.018
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Systems and methods are provided that facilitate retrieval of a hash index in an electronic device. The system contains an addressing component that generates a hash index as a function of an exclusive-or identity. The addressing component can retrieve the hash index as a function of a tag value. Accordingly, required storage area can be reduced and electronic devices can be more efficient.

Claims

1. A device configured for managing cache memory addressing, comprising:

a memory controller component configured for receiving data comprising an address that comprises tag data representing a first memory location and index data representing a second memory location;

an addressing component configured for hashing the tag data to generate a hashed tag and applying an exclusive-or operation to the hashed tag and the index data to generate identity data representing a logical identity between the tag data and the index data; and

a tag memory component configured for storing the identity data, and in response to the addressing component generating the identity data, discarding the index data.

2. The device of claim 1, wherein the addressing component is further configured for recovering the index data as a function of the identity data and the hashed tag.

3. The device of claim 1, wherein the memory controller component is configured for evicting an entry from a data memory component of the cache based on the index data recovered as a function of the identity data and the hashed tag data.

4. The device of claim 1, wherein the tag memory component is further configured for storing the tag data.

5. The device of claim 1, wherein the memory controller component is further configured for instructing the tag memory component to evict an entry from the tag memory component.

6. The device of claim 1, wherein the memory controller component is further configured for instructing the tag memory component to evict an entry from the tag memory component based on a predetermined criterion.

7. The device of claim 1, wherein the addressing component is further configured for generating compressed tag data based on the tag data and a defined hash function.

8. A method of managing cache addressing of a system, comprising:

receiving data comprising an address that comprises tag data representing a first memory location and index data representing a second memory location;

generating a hash identity by applying a hash function to the tag data to generate a hashed tag data and applying an exclusive-or operator to the hashed tag data and the index data, wherein the hash identity defines a logical relationship between the tag data and the index data;

storing at least one entry comprising the hash identity in response to releasing the index data; and

recovering a value of the index data as a function of the hash identity and the hashed tag data.

9. The method of claim 8, further comprising recovering the value of the index data in response to performing an exclusive-or operation on the hashed tag data and the hash identity.

10. The method of claim 8, further comprising evicting an entry from the system as a function of performing an exclusive-or operation on the hashed tag data and the hash identity.

11. The method of claim 8, further comprising compressing the tag data as a function of a predefined compressing function to generate compressed tag data.

12. The method of claim 11, wherein the generating of the hash identity is based on the compressed tag data and the index data.

13. A system for cache miss detection, comprising:

a processor; and

a memory that stores executable instructions, that when executed by the processor, perform operations, comprising;

receiving at least one request;

determining an address associated with the at least one request, wherein the address comprises tag data and index data;

applying a defined hashing function to the tag data to generate hashed tag data;

generating an identity defining a relationship between the tag data and the index data by performing a bit-wise exclusive-or operation on the hashed tag data and the index data;

storing the hashed tag data and the identity; and

in response to the generating of the identity, discarding the index data.

14. The system of claim 13, wherein the at least one request comprises type data representing a write type request, a read type request, or an eviction type request.

15. The system of claim 14, the operations further comprising:

in response to receiving the write type request, performing a storage operation to a computer addressable memory location as a function of the identity; and

in response to receiving the read type request, performing a memory lookup as a function of the identity.

16. The system of claim 13, the operations further comprising generating data identical to the index data based on applying the bit-wise exclusive-or operation on the identity to obtain the hashed tag data and the index data.

17. The system of claim 16, the operations further comprising evicting stored data as a function of the index data.

18. The system of claim 13, the operations further comprising recovering the index data as a function of the identity and the hashed tag data.