System and method for performing a speculative cache fill

• US 6,775,749 B1
• Filed: 01/29/2002
• Issued: 08/10/2004
• Est. Priority Date: 01/29/2002
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Mudgett, Dan S., Fox, Mark T.
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US10/059,934
• Time in Patent Office: 924 Days
• Field of Search: 711/122, 711/124, 711/119, 711/146, 711/204, 711/213
• US Class Current: 711/146
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 2212/507 using speculative control

Abstract

A computer system may include several caches that are each coupled to receive data from a shared memory. A cache coherency mechanism may be configured to receive a cache fill request, and in response, to send a probe to determine whether any of the other caches contain a copy of the requested data. Some time after sending the probe, the cache controller may provide a speculative response to the cache fill request to the requesting device. By delaying providing the speculative response until some time after the probes are sent, it may become more likely that the responses to the probes will be received in time to validate the speculative response.

Claims

1. A computer system comprising:

a plurality of caches;

a plurality of cache controllers, wherein each cache controller is coupled to control a respective one of the caches;

a memory coupled to provide data to each of the caches; and

a cache coherency mechanism coupled to the cache controllers and the memory, wherein the cache coherency mechanism is configured to receive a request to provide a copy of data from the memory to a first cache;

wherein in response to receiving the request, the cache coherency mechanism is configured to send a probe to a first set of the cache controllers, wherein each of the first set of cache controllers is configured to determine whether its cache contains the data in response to receiving the probe;

wherein if a first number of clock cycles have elapsed after the probe was sent, the cache coherency mechanism is configured to provide a speculative response to the request before all of the first set of cache controllers have responded to the probe.

2. The computer system of claim 1, wherein each cache controller in a first portion of the cache controllers is integrated with a respective processor.

3. The computer system of claim 1, wherein the cache coherency mechanism is configured to provide the speculative response if at least one of the first set of cache controllers has not yet responded to the probe.

4. The computer system of claim 1, wherein if one of the first set of cache controllers responds to the probe with an indication that one of the caches has a modified copy of the data, the cache coherency mechanism is configured to invalidate the speculative response.

5. The computer system of claim 1, wherein the cache coherency mechanism is configured to validate the speculative response by providing a validation signal to the first cache'"'"'s cache controller as the memory'"'"'s copy of the requested data is being provided to the first cache.

6. The computer system of claim 5, wherein if fewer than all of the first set of cache controllers have responded to the probe, the cache coherency mechanism is configured to not provide the validation signal.

7. A computer system comprising:

a first cache controller configured to control a first cache;

a second cache controller configured to control a second cache;

a memory coupled to provide data to the first cache and the second cache; and

a cache coherency mechanism coupled to the first cache, the second cache, and the memory and configured to receive a first request to provide a copy of data to the first cache;

wherein in response to receiving the first request, the cache coherency mechanism is configured to send a probe to the second cache controller;

wherein in response to receiving the probe, the second cache controller is configured to determine whether the second cache contains the data;

wherein if a first amount of time has elapsed since the probe was sent and the second cache controller has not yet provided a response to the probe to the cache coherency mechanism, the cache coherency mechanism is configured to provide a speculative response to the first request to the first cache.

8. The computer system of claim 7, wherein the first amount of time is measured in clock cycles.

9. The computer system of claim 7, wherein each of the first and second cache controllers is integrated with a respective processor.

10. The computer system of claim 7, wherein the cache coherency mechanism is comprised in a chipset configured to couple the first and second cache to the memory.

11. The computer system of claim 7, wherein the cache coherency mechanism is configured to receive the first request from a first processor, wherein the first processor is configured to generate the first request in response to a cache miss in the first cache.

12. The computer system of claim 7, wherein if the first amount of time has elapsed and a non-speculative response is pending, the cache coherency mechanism is configured to provide the non-speculative response to the first cache before providing the speculative response to the first cache.

13. The computer system of claim 7, wherein the cache coherency mechanism is configured to provide the speculative response to the first cache if the first amount of time has elapsed and a second amount of time has not elapsed since the probe was sent, wherein the second amount of time is greater than the first amount of time.

14. The computer system of claim 7, wherein the first amount of time is tracked by a counter comprised in the cache coherency mechanism.

15. The computer system of claim 14, wherein the counter is configured to begin counting when the probe is sent.

16. The computer system of claim 14, wherein the counter is configured to begin counting when an entry corresponding to the speculative response is allocated in a response queue comprised in the cache coherency mechanism.

17. The computer system of claim 7, wherein if the response to the probe indicates that the memory contains a most recent copy of the data requested in the first request, the cache coherency mechanism is configured to validate the speculative response.

18. The computer system of claim 7, wherein if the cache coherency mechanism receives the response to the probe from the second cache controller, the cache controller is configured to generate an indication that the speculative response has become a non-speculative response.

19. The computer system of claim 7, wherein if the response to the probe indicates that the second cache contains a most recent copy of the data requested in the first request, the cache coherency mechanism is configured to invalidate the speculative response.

20. The computer system of claim 19, wherein if the response to the probe indicates that the second cache contains a most recent copy of the data requested in the first request, the cache coherency mechanism is configured to provide a non-speculative response to the first cache in response to obtaining the most recent copy of the data from the second cache.

21. The computer system of claim 7, wherein the cache coherency mechanism is configured to invalidate the speculative response if the response to the probe is not received.

22. The computer system of claim 21, wherein if the cache coherency mechanism invalidates the speculative response, the cache coherency mechanism is configured to provide a non-speculative response to the first request in response to receiving the response to the probe from the second cache controller.

23. The computer system of claim 7, wherein the second cache comprises both a level one (L1) cache and a level two (L2) cache.

24. A method of performing a cache fill in a shared memory computer system, the method comprising:

a first device asserting a first cache fill request requesting that data from system memory be stored in the first device'"'"'s cache;

in response to said asserting, sending a probe to a second device;

in response to receiving the probe, the second device determining whether the second device'"'"'s cache contains the data; and

in response to a first amount of time elapsing after said sending and not receiving a response to the probe from the second device before said elapsing, providing a speculative response to the first cache fill request to the first device.

25. The method of claim 24, further comprising providing a non-speculative response to the first cache fill request to the first device in response to receiving a response to the probe from the second device if said receiving occurs after said elapsing.

26. The method of claim 24, wherein said requesting comprises the first device requesting the data from system memory in response to a cache miss occurring in the first device'"'"'s cache.

27. The method of claim 24, further comprising invalidating the speculative response in response to not receiving a response to the probe from the second device before a decision point, wherein the decision point occurs during said providing a speculative response.

28. The method of claim 24, further comprising:

invalidating the speculative response in response to receiving a response to the probe from the second device before a decision point, wherein the response indicates that the system memory does not contain a most recent copy of the data;

in response to said invalidating, providing a non-speculative response to the first cache fill request to the first device, wherein the non-speculative response comprises the most recent copy of the data.

29. The method of claim 24, further comprising validating the speculative response in response to receiving a response to the probe from the second device, wherein the response to the probe indicates that the system memory contains a most recent copy of the data.

30. The method of claim 24, further comprising opening a launch window in response to said elapsing, wherein said providing a speculative response occurs during the launch window.

31. The method of claim 30, further comprising closing the launch window in response to a second amount of time elapsing after said sending.

32. The method of claim 24, wherein the first amount of time is measured in clock cycles.

33. The method of claim 32, further comprising decrementing a counter each clock cycle in response to said sending, wherein said elapsing occurs when the counter is decremented to a minimum counter value.

34. The method of claim 24, further comprising providing a non-speculative response to the first device before providing the speculative response to the first device.

35. The method of claim 24, wherein the second device is configured to control a second cache, wherein the second cache comprises a level one (L1) cache and a level two (L2) cache.