Way-predicting cache memory

• US 6,425,055 B1
• Filed: 02/24/1999
• Issued: 07/23/2002
• Est. Priority Date: 02/24/1999
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Sager, David J., Hinton, Glenn J.
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US09/256,846
• Time in Patent Office: 1,245 Days
• Field of Search: 711/128, 711/137, 711/140, 711/118, 712/222, 712/238, 714/7, 714/805, 714/763
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 2212/6082 Way prediction in set-associative cache

Abstract

An apparatus and method for accessing a cache memory. In a cache memory, an address is received that includes a set field and a partial tag field, the set field and the partial tag field together including fewer bits than necessary to uniquely identify a region of memory equal in size to a cache line of the cache memory. The set field is decoded to select one of a plurality of storage units within the cache memory, each of the plurality of storage units including a plurality of cache lines of the cache memory. The partial tag field is compared to a plurality of previously stored partial tags that correspond to the plurality of cache lines within the selected one of the plurality of storage units to determine if the partial tag field matches one of the plurality of previously stored partial tags. If the one of the previously stored partial tags matches the partial tag field, one of the plurality of cache lines that corresponds to the one of the plurality of previously stored partial tags is output.

Claims

1. A method comprising:

asserting a memory address that includes a set field and a tag field that together uniquely identify a region of system memory equal in size to a cache line in a cache memory;

decoding the set field;

comparing a partial tag field that includes less than all bits in the tag field against a plurality of previously stored partial tag entries in parallel with the decoding; and

outputting a cache line from the cache memory if the partial tag field matches a partial tag entry of the plurality of previously stored partial tag entries.

2. The method of claim 1, wherein the partial tag field includes a least significant bit of the tag field.

3. The method of claim 1, wherein outputting the cache line from the cache memory comprises outputting a cache line that has been obtained from a memory address that includes at least the set field and the partial tag field.

4. The method of claim 1, wherein comparing the partial tag field that includes less than all bits in the tag field against the plurality of previously stored partial tag entries comprises comparing a partial tag field that includes less than half the bits in the tag field against the plurality of previously stored partial tag entries.

5. The method of claim 1:

wherein the cache memory includes a plurality of data ways organized within cache words; and

wherein the partial tag field includes a number of bits sufficient to uniquely select one of the plurality of data ways within one of the cache words.

6. The method of claim 5, wherein each of the plurality of data ways is used to store a respective cache line.

7. The method of claim 1, further comprising generating a word select signal that corresponds to one of a plurality of cache words within the cache memory based on the decoding of the set field, each of the plurality of cache words including a plurality of cache lines.

8. The method of claim 7, wherein comparing the partial tag field against the plurality of previously stored partial tag entries comprises comparing the partial tag field against a plurality of previously stored partial tag entries that correspond to the selected one of the plurality of cache words.

9. The method of claim 7, wherein outputting a cache line from the cache memory if the partial tag field matches the partial tag entry comprises generating a way select signal that corresponds to a data way containing the cache line based on which of the plurality of partial tag entries matches the partial tag field.

10. The method of claim 9, wherein outputting the cache line from the cache memory comprises logically combining the word select signal and the way select signal to enable the cache line to be output.

11. A method comprising:

receiving an address that includes a set field and a partial tag field, the set field and the partial tag field together including fewer bits than necessary to uniquely identify a region of memory equal in size to a cache line of a cache memory;

decoding the set field to select one of a plurality of storage units within the cache memory, each of the plurality of storage units including a plurality of cache lines of the cache memory;

comparing the partial tag field to a plurality of previously stored partial tags that correspond to the plurality of storage units in parallel with said decoding to determine if the partial tag field matches one of the plurality of previously stored partial tags; and

outputting one of the plurality of cache lines that corresponds to one of the plurality of previously stored partial tags if the one of the previously stored partial tags matches the partial tag field.

12. The method of claim 11, wherein said decoding the set field is performed substantially concurrently with said comparing the partial tag field.

13. The method of claim 11, wherein comparing further comprises:

comparing the partial tag field to a plurality of previously stored partial tags that correspond to a first storage unit that is selectable by a first set field, the first storage unit having a plurality of cache lines; and

comparing the partial tag field to a plurality of previously stored partial tags that correspond to a second storage unit that is selectable by a second set field, the second storage unit having a plurality of cache lines.

14. An apparatus comprising:

an input path to receive an M-bit set field and a K-bit partial tag field of an address that includes an R-bit tag field, K being less that R;

a set field decoder coupled with the input path to receive the set field and to use the set field to select a plurality of cache lines;

a plurality of way predictors coupled with the input path to each store a plurality of partial tags, to each subsequently receive the partial tag field, and each comprising a plurality of comparators to compare the partial tag field with the plurality of stored partial tags and to select a cache line if the partial tag field matches a stored tag; and

selection circuitry coupled with the set field decoder, the plurality of way predictors, and a cache line to output the cache line if it is selected by the set field decoder and a way predictor of the plurality.

15. The apparatus of claim 14, further comprising:

a processor to perform at least one operation on a speculative data value of the output cache line, and concurrently with said step of performing at least one operation, comparing] and to concurrently compare the R-bit tag field to a plurality of R-bit tag fields that have been previously stored in a tag memory to determine whether the speculative data value is a data value indicated by an address including the R-bit tag field and M-bit set field.

16. The apparatus of claim 14, wherein the set field decoder is a set field decoder to decode the set field concurrently with the comparators comparing the partial tag field with the stored partial tags.

17. The apparatus of claim 14, wherein the K-bit partial tag field includes less than half the bits in the R-bit tag field.

18. The apparatus of claim 14, contained within a processor to assert the set field and the partial tag field on the input path and to process data of the output cache line.

19. The apparatus of claim 14, contained within a processor means.

20. The apparatus of claim 14, wherein the plurality of way predictors comprises a way predictor means.

21. The apparatus of claim 14, further comprising:

a processor core coupled with the input path to provide the set field and the partial tag field, to receive data from the output cache line, and to concurrently execute an operation on the data; and

tag comparison circuitry to determine whether the data corresponds to the R-bit tag field by comparing at least a portion of the R-bit tag field that is not included in the K-bit tag field with previously stored tag data.

22. The apparatus of claim 14, wherein the partial tag field includes a number of bits sufficient to uniquely select one of the plurality of cache lines selected by the set field decoder.

23. The apparatus of claim 14:

wherein the select circuitry includes a plurality of logic gates that each have a first input line coupled with the set field decoder, a second input line coupled with a way predictor of the plurality of way predictors, and an output line coupled with a cache line; and

wherein the plurality of logic gates includes a logic gate to assert a signal on the output line indicating to output the cache line when the logic gate receives a signal on the first input line indicating the plurality of cache lines selected by the set field decoder and receives a signal on the second input indicating a cache line selected by the way predictor.

24. An apparatus comprising:

a cache memory comprising a first plurality of cache lines operable to be selected by a first set field and a second plurality of cache lines operable to be selected by a second different set field;

set decode circuitry to select the first plurality of the cache lines by decoding an input set field and by determining that the set field matches the first set field; and

way prediction circuitry to select one cache line of the first plurality of the cache lines by comparing a partial tag field to a first plurality of previously stored partial tags corresponding to the first plurality of cache lines and a second plurality of previously stored partial tags corresponding to the second plurality of cache lines and by determining that the partial tag field matches a partial tag of the first plurality.

25. The apparatus of claim 24, wherein the partial tag field includes a least significant bit of a full tag field.

26. The apparatus of claim 24:

wherein the cache memory comprises a plurality of cache words including a first cache word comprising the first plurality of cache lines and a second cache word comprising the second plurality of cache lines; and

wherein the set decode circuitry is coupled with a plurality of word select lines, each word select line to select a respective one of the plurality of cache words according to the decode of the set field by the set decode circuitry.

27. The apparatus of claim 24, wherein the way prediction circuitry includes a first way predictor coupled with the first plurality of cache lines by a corresponding plurality of way select lines and a second way predictor coupled with the second plurality of cache lines by a corresponding second plurality of way select lines.

28. The apparatus of claim 27:

wherein the first way predictor comprises a plurality of partial tag storage elements that correspond to the plurality of way select signal lines; and

wherein the first way predictor is a predictor to assert a way select signal on a way select line if the corresponding partial tag storage element contains a partial tag that matches the partial tag field.

29. The apparatus of claim 24, wherein the set decode circuitry and the way prediction circuitry are operable to select substantially concurrently and in parallel.

30. The apparatus of claim 24, wherein the way prediction circuitry comprises way prediction circuitry to select based on a partial tag field that includes less than half the bits in a full tag field.

31. The apparatus of claim 24, contained within a processor to assert the set field and the partial tag field and to process data of the selected one cache line.

32. The apparatus of claim 24, contained within a processor means.

33. The apparatus of claim 24, wherein the way prediction circuitry comprises a way predictor means.

34. The apparatus of claim 24, further comprising:

a processor core to provide the set field and the partial tag field, to receive data from the selected one cache line, and to execute an operation based on the data; and

tag comparison circuitry to determine whether the data corresponds to a full cache address containing the set field and a full tag field that contains the partial tag field by comparing at least a portion of the full tag field that is not included in the received partial tag field with previously stored tag data.

35. The apparatus of claim 24, wherein the partial tag field includes a number of bits sufficient to uniquely select one of the first plurality of cache lines.

36. The apparatus of claim 24, further comprising selection circuitry containing a plurality of logic gates that each have a first input line coupled with the set decode circuitry, a second input line coupled with a way prediction on circuitry, and an output line coupled with a cache line, wherein the plurality of logic gates includes a logic gate to assert a signal on an output line indicating to output a cache line when a logic gate receives a signal on the first input line indicating the first plurality of cache lines selected by the set decode circuitry and receives a signal on a second input line indicating the cache line selected by the way prediction circuitry.