Methods for caching cache tags

A method for storing information in a computer memory system, comprising the steps of:

• maintaining an Mth level storage system including an Mth level data store for storing data, an Mth level full directory store for storing a set of tags corresponding to the data stored in the data store, an Mth level partial directory for storing a subset of the tags stored in the full directory store, each of the tags in the subset having N-bits, wherein N is less than a total number of bits corresponding to each tag in the set, and the partial directory is accessible faster than the full-directory;
• upon an M-1 level storage system miss corresponding to a request for data, the request including a request tag corresponding to the requested data, determining whether N-bits of the request tag match N-bits of a tag in the partial directory;
• fetching the requested data and a tag corresponding to the matching tag from the data store and the full directory store, respectively, when the N-bits of the request tag match the N-bits of the tag in the partial directory;
• and
• providing the fetched data to an object requesting the data, when all of the bits of the fetched tag match all of the bits of the request tag.

A method for storing information in a computer memory system, comprising the steps of:

• maintaining an Mth level storage system including an Mth level data store for storing data, an Mth level full directory store for storing a set of full tags corresponding to the data stored in the data store, an Mth level partial directory for storing a subset of the tags stored in the full directory store, wherein the subset includes at least some of the full tags of the set and at least some partial tags having N-bits, N being less than a total number of bits corresponding to each tag in the set, and the partial directory is accessible faster than the full directory;
• upon an M-1 level storage system miss corresponding to a request for data, the request including a request tag corresponding to the requested data, determining whether the request tag matches one of a full tag and N-bits of a partial tag in the partial directory;
• retrieving the requested data from the data store, when the request tag matches the full tag;
• fetching the requested data and a full tag corresponding to the partial tag from the data store and the full directory store, respectively, when the request tag matches the N-bits of the partial tag;
• and
• providing the fetched data to an object requesting the data, when all of the bits of the fetched full tag match all of the bits of the request.

A method for storing information in a computer memory system, comprising the steps of:

• maintaining an Mth level storage system including an Mth level data store for storing data, an Mth level full directory store for storing a set of tags corresponding to the data stored in the data store, an Mth level partial directory for storing a subset of the tags stored in the full directory store, wherein the partial directory is accessible faster than the full directory;
• upon an M-1 level storage system miss corresponding to a request for data, determining whether the request matches a tag in a congruence class in the partial directory;
• fetching, from the full directory store, other tags in the congruence class, when the request does not match the tag in the congruence class in the partial directory;
• determining whether the request matches any of the other tags in the congruence class in the full directory store;
• and
• fetching the requested data from the data store when the request matches one of the tag in the partial directory and any of the other tags in the full directory store, and from a next level of the memory system, when the request does not match the tag in the partial directory and any of the other tags in the full directory store.