Data cache which speculatively updates a predicted data cache storage location with store data and subsequently corrects mispredicted updates

• US 5,860,104 A
• Filed: 08/31/1995
• Issued: 01/12/1999
• Est. Priority Date: 08/31/1995
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Witt, David B., Hattangadi, Rajiv M.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US08/521,627
• Time in Patent Office: 1,230 Days
• Field of Search: 395/403, 395/402, 395/394, 395/457, 395/465, 395/584, 395/586, 395/464, 395/455, 395/383, 395/185.06, 711/204, 711/213, 711/126
• US Class Current: 711/137
• CPC Class Codes: G06F 2212/6082 Way prediction in set-associative cache
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/30152 Determining start or end of instruction; determining instruction length
• CPC Class Codes: G06F 9/30163 with implied specifier, e.g. top of stack
• CPC Class Codes: G06F 9/30167 of immediate specifier, e.g. constants
• CPC Class Codes: G06F 9/3816 Instruction alignment, e.g. cache line crossing
• CPC Class Codes: G06F 9/382 Pipelined decoding, e.g. using predecoding
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3828 with global bypass, e.g. between pipelines, between clusters
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A data cache configured to perform store accesses in a single clock cycle is provided. The data cache speculatively stores data within a predicted way of the cache after capturing the data currently being stored in that predicted way. During a subsequent clock cycle, the cache hit information for the store access validates the way prediction. If the way prediction is correct, then the store is complete. If the way prediction is incorrect, then the captured data is restored to the predicted way. If the store access hits in an unpredicted way, the store data is transferred into the correct storage location within the data cache concurrently with the restoration of data in the predicted storage location. Each store for which the way prediction is correct utilizes a single clock cycle of data cache bandwidth. Additionally, the way prediction structure implemented within the data cache bypasses the tag comparisons of the data cache to select data bytes for the output. Therefore, the access time of the associative data cache may be substantially similar to a direct-mapped cache access time. The present data cache is therefore suitable for high frequency superscalar microprocessors.

Claims

1. A method for performing a store access to a data cache comprising:

receiving an address associated with said store access in said data cache;

reading a first data from a storage location within said data cache wherein said storage location is indexed by said address associated with said store access, said reading performed responsive to said receiving said address;

speculatively storing store data associated with said store access into said storage location subsequent to said reading said first data and prior to determining if said address is a hit in said storage location; and

restoring said first data to said storage location responsive to determining that said address is a miss in said storage location.

2. The method as recited in claim 1 further comprising selecting said storage location from a plurality of storage locations indexed by said address.

3. The method as recited in claim 2 wherein said selecting is performed according to a way prediction associated with said address.

4. The method as recited in claim 3, further comprising updating said way prediction in parallel with said restoring.

5. The method as recited in claim 1, further comprising storing said store data into another storage location within said data cache in parallel with said restoring.

6. The method as recited in claim 5 wherein said address is a hit in said another storage location.

7. A data cache comprising:

a data array coupled to receive a store address corresponding to a store access and a store data corresponding to said store access, said data array including a plurality of storage locations, wherein said data array is configured to select at least a first storage location from said plurality of storage locations in response to an index portion of said store address, and wherein said data array is configured to output a first data stored in said first storage location and to subsequently update said first storage location with said store data in response to said store access prior to said data cache determining if said store access is a hit in said first storage location;

a data register coupled to said data array, wherein said data register is configured to capture said first data output from said data array and to subsequently provide said first data as an input to said data array; and

a control unit coupled to said data array, wherein said control unit is configured to cause said data array to restore said first data, provided as said input to said data array by said data register, into said first storage location in response to determining that said store access is a miss in said first storage location.

8. The data cache as recited in claim 7 further comprising:

a tag array coupled to receive said store address, wherein said tag array is configured to store a plurality of tags corresponding to said plurality of storage locations, wherein said tag array is configured to output at least a first tag from said plurality of tags in response to said index portion of said store address, said first tag corresponding to said first storage location; and

a tag comparator block coupled to said tag array, wherein said tag comparator block is configured to compare said first tag to said store address to determine if said store access is a hit in said first storage location.

9. The data cache as recited in claim 8 wherein said data cache is organized as a set associative cache, and wherein said data array is configured to select at least a second storage location from said plurality of storage locations, and wherein said tag array is configured to select at least a second tag from said plurality of tags, and wherein said second tag corresponds to said second storage location, and wherein said tag comparator block is configured to compare said second tag to said store address to determine if said store access is a hit in said second storage location.

10. The data cache as recited in claim 9 wherein said control unit is configured to cause said data array to update said second storage location with said store data in response to said tag comparator block determining that said store access is a hit in said second storage location.

11. The data cache as recited in claim 10 wherein said control unit is configured to cause said data array to update said second storage location in parallel with causing said data array to restore said first data to said first storage location.

12. The data cache as recited in claim 9 further comprising a way prediction structure coupled to receive said store address and coupled to said data array, wherein said way prediction structure is configured to predict one of a plurality of ways of said data cache in which said store address hits.

13. The data cache as recited in claim 12 wherein said data array is configured to select said first storage location responsive to said index portion of said store address and said one of said plurality of ways.

14. The data cache as recited in claim 13 wherein said tag comparison block is configured to update said way prediction structure to predict another one of said plurality of ways corresponding to said second storage location upon determining that said store access is a hit in said second storage location.