US 6,138,209 AGranted

Data processing system and multi-way set associative cache utilizing class predict data structure and method thereof

AssigneeInternational Business Machines Corporation

InventorsDavid John Krolak, Sheldon Bernard Levenstein

Life of this patent

Estimating the term…

Loading patent…

Abstract

A data processing system and method thereof utilize a unique cache architecture that performs class prediction in a multi-way set associative cache during either or both of handling a memory access request by an anterior cache and translating a memory access request to an addressing format compatible with the multi-way set associative cache. Class prediction may be performed using a class predict data structure with a plurality of predict array elements partitioned into sub-arrays that is accessed using a hashing algorithm to retrieve selected sub-arrays. In addition, a master/slave class predict architecture may be utilized to permit concurrent access to class predict information by multiple memory access request sources. Moreover, a cache may be configured to operate in multiple associativity modes by selectively utilizing either class predict information or address information related to a memory access request in the generation of an index into the cache data array.

Claims47

Dependent claims

A data processing system, comprising:

(a) a memory configured to store information at a plurality of memory addresses;
(b) a processor configured to issue a memory access request for information referenced by a selected memory address;
(c) a first cache coupled to the processor and the memory and configured to cache a first portion of information from the memory, the first cache including a first cache directory including a plurality of first cache directory entries;
(d) a second cache coupled to the processor and configured as a multi-way set associative cache that caches a second portion of information from the memory, the second cache including a second cache directory including a plurality of second cache directory entries, each of which is associated with one of a plurality of classes, wherein the selected memory address is related to a set of corresponding second cache directory entries respectively associated with the plurality of classes;
(e) a class predict data structure separate from the first cache directory and including a plurality of predict entries of predicted classes, at least one of the plurality of predict entries including a predicted class for the set of corresponding second cache directory entries related to the selected memory address, wherein the class predict data structure comprises a class predict table including a plurality of table entries, each including a plurality of array elements, each array element associated with a different one of the plurality predict entries;
(f) a first access unit configured to initiate an access to the class predict data structure during processing of the memory access request by the first cache to determine the predicted class for the set of corresponding second cache directory entries related to the selected memory address;
and
(g) a second access unit configured to access the corresponding second cache directory entry associated with the predicted class from the set of corresponding second cache directory entries to determine a cache hit or miss for the selected memory address.

5 more elements

An integrated circuit device, comprising:

(a) a processor configured to issue a memory access request for information referenced by a selected memory address;
(b) a memory port coupled to the processor and adapted to communicate with an external memory that stores information at a plurality of memory addresses;
(c) a first cache coupled to the processor and configured to cache a first portion of information from the external memory, the first cache including a first cache directory including a plurality of first cache directory entries;
(d) a second cache coupled to the processor and configured as a multi-way set associative cache that caches a second portion of information from the external memory, the second cache including a cache port adapted to communicate with an external second cache directory including a plurality of second cache directory entries, each of which is associated with one of a plurality of classes, wherein the selected memory address is related to a set of corresponding second cache directory entries respectively associated with the plurality of classes;
(e) a class predict data structure separate from the first cache directory and including a plurality of predict entries of predicted classes, at least one of the plurality of predict entries including a predicted class for the set of corresponding second cache directory entries related to the selected memory address, wherein the class predict data structure comprises a class predict table including a plurality of table entries, each including a plurality of array elements, each array element associated with a different one of the plurality of predict entries;
(f) a first access unit configured to initiate an access to the class predict data structure during processing of the memory access request by the first cache to determine the predicted class for the set of corresponding second cache directory entries related to the selected memory address;
and
(g) a second access unit configured to access the cache port to retrieve the corresponding second cache directory entry associated with the predicted class from the set of corresponding second cache directory entries to determine a cache hit or miss for the selected memory address.

5 more elements

A method of accessing information referenced by a selected memory address in a data processing system of the type including first and second caches coupled to a processor, the first cache including a first cache directory including a plurality of first cache directory entries, the second cache comprising a multi-way set associative cache of the type including a plurality of second cache directory entries, each of which is associated with one of a plurality of classes, wherein the selected memory address is related to a set of corresponding second cache directory entries respectively associated with the plurality of classes in the multi-way set associative cache, the method comprising;

(a) concurrently with accessing the first cache, initiating an access to a class predict data structure to determine a predicted class for the set of corresponding second cache directory entries related to the selected memory address, wherein the class predict data structure is separate from the first cache directory and includes a plurality of predict entries of predicted classes, and wherein the class predict data structure comprises a class predict table including a plurality of table entries, each including a plurality of array elements, each array element associated with a different one of the plurality of predict entries;
and
(b) in response to a cache miss in the first cache, determining a cache hit or miss in the second cache using the corresponding second cache directory entry associated with the predicted class for the set of corresponding second cache directory entries.

A data processing system, comprising:

(a) a memory configured to store information at a plurality of memory addresses;
(b) a processor configured to issue a memory access request for information referenced by a selected memory address defined by a plurality of address bits;
(c) a cache coupled to the processor and configured as a multi-way set associative cache that caches a portion of information from the memory, the cache including a cache directory including a plurality of cache directory entries, each of which is associated with one of a plurality of classes, wherein the selected memory address is related to a set of corresponding cache directory entries respectively associated with the plurality of classes;
(d) a class predict array including a plurality of predict array elements storing predicted classes, the class predict array partitioned into a plurality of sub-arrays, each of which including a portion of the plurality of predict array elements, wherein one of the predict array elements includes a predicted class for the set of corresponding cache directory entries related to the selected memory address;
and
(e) an access unit configured to initiate an access to the class predict array to determine the predicted class for the set of corresponding cache directory entries related to the selected memory address, the access unit configured to apply a hashing algorithm to a first set of the plurality of address bits for the selected memory address to select a matching one of the plurality of sub-arrays, and to select a matching one of the predict array elements from the matching sub-array using a second set of the plurality of address bits for the selected memory address.

3 more elements

A data processing system, comprising:

(a) a memory configured to store information at a plurality of memory addresses;
(b) at least one memory access request source configured to issue a memory access request for information referenced by a selected memory address;
(c) a cache coupled to the memory access request source and configured as a multi-way set associative cache that caches a portion of information from the memory, the cache including a cache directory including a plurality of cache directory entries, each of which is associated with one of a plurality of classes, wherein the selected memory address is related to a set of corresponding cache directory entries respectively associated with the plurality of classes;
(d) a master class predict data structure including a plurality of predict entries of predicted classes, one of which including a predicted class for the set of corresponding cache directory entries related to the selected memory address;
(e) at least one slave class predict data structure associated with the memory access request source, the slave class predict data structure including an access port permitting read access thereto, the slave class predict data structure maintaining a copy of at least a portion of the plurality of predict entries in the master data structure;
and
(f) an access unit configured to initiate an access to the slave class predict data structure through the access port to determine the predicted class for the set of corresponding cache directory entries related to the selected memory address.

4 more elements

A data processing system, comprising:

(a) a memory configured to store information at a plurality of memory addresses;
(b) a processor configured to issue a memory access request for information referenced by a selected memory address defined by a plurality of bits;
(c) a cache coupled to the processor and configured to cache a portion of information from the memory, the cache further configurable to operate in one of first and second modes, the cache configured to operate as an n-way set associative cache in the first mode and as an m-way set associative cache in the second mode;
(d) a class predict data structure including a plurality of predict entries of predicted classes, one of which including a predicted class for the selected memory address, the class predict data structuring outputting at least one class predict bit;
(e) a cache data array including a plurality of cache lines accessed via an index, the index defined by a plurality of bits, wherein, in the first mode, each cache line is associated with one of n classes, and, in the second mode, each cache line is associated with one of m classes;
(f) a first access unit configured to initiate an access to the class predict data structure to retrieve the class predict bit for the selected memory address;
and
(g) a second access unit configured to generate the index to the cache data array for the selected memory address, wherein, in the first mode, the second access unit generates the index with a selected bit in the plurality of bits set to the value of the class predict bit, and in the second mode, the second access unit generates the index with the selected bit set to the value of a predetermined one of the plurality of bits in the selected memory address.

5 more elements

A data processing system, comprising:

(a) a memory configured to store information at a plurality of memory addresses;
(b) a processor configured to issue a memory access request for information referenced by a selected memory address;
(c) a first cache coupled to the processor and the memory and configured to cache a first portion of information from the memory, the first cache including a first cache directory including a plurality of first cache directory entries;
(d) a second cache coupled to the processor and configured as a multi-way set associative cache that caches a second portion of information from the memory, the second cache including a second cache directory including a plurality of second cache directory entries, each of which is associated with one of a plurality of classes, wherein the selected memory address is related to a set of corresponding second cache directory entries respectively associated with the plurality of classes;
(e) a class predict data structure separate from the first cache directory and including a plurality of predict entries of predicted classes, at least one of the plurality of predict entries including a predicted class for the set of corresponding second cache directory entries related to the selected memory address, wherein the number of predict entries in the class predict data structure is greater than the number of first cache directory entries in the first cache directory, and wherein the class predict data structure comprises a class predict table including a plurality of table entries, each including a plurality of array elements, each array element associated with a different one of the plurality of predict entries;
(f) a first access unit configured to initiate an access to the class predict data structure during processing of the memory access request by the first cache to determine the predicted class for the set of corresponding second cache directory entries related to the selected memory address;
and
(g) a second access unit configured to access the corresponding second cache directory entry associated with the predicted class from the set of corresponding second cache directory entries to determine a cache hit or miss for the selected memory address.

5 more elements

Dependencies are inferred from the claim text.