ADAPTIVE CACHE PREFETCHING BASED ON COMPETING DEDICATED PREFETCH POLICIES IN DEDICATED CACHE SETS TO REDUCE CACHE POLLUTION

• US 20150286571A1
• Filed: 04/04/2014
• Published: 10/08/2015
• Est. Priority Date: 04/04/2014
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Palframan, David John, Cain, Harold Wade III
• Application Number:
  US14/245,356
• Publication Number:
  US 20150286571A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 2212/283 Plural cache memories
• CPC Class Codes: G06F 2212/602 Details relating to cache prefetching
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 2212/6046 Using a specific cache allocation policy other than replacement policy
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Adaptive cache prefetching based on competing dedicated prefetch policies in dedicated cache sets to reduce cache pollution is disclosed. In one aspect, an adaptive cache prefetch circuit is provided for prefetching data into a cache. The adaptive cache prefetch circuit is configured to determine which prefetch policy to use as a replacement policy based on competing dedicated prefetch policies applied to dedicated cache sets in the cache. Each dedicated cache set has an associated dedicated prefetch policy used as a replacement policy for the given dedicated cache set. Cache misses for accesses to each of the dedicated cache sets are tracked by the adaptive cache prefetch circuit. The adaptive cache prefetch circuit can be configured to apply a prefetch policy to the other follower (i.e., non-dedicated) cache sets in the cache using the dedicated prefetch policy that incurred fewer cache misses to its respective dedicated cache sets to reduce cache pollution.

Claims

1. An adaptive cache prefetch circuit for prefetching cache data into a cache, comprising:

a miss tracking circuit configured to update at least one miss state based on a cache miss resulting from an accessed cache entry in;

at least one first dedicated cache set in a cache for which at least one first dedicated prefetch policy is applied, and at least one second dedicated cache set in the cache for which at least one second dedicated prefetch policy, different from the at least one first dedicated prefetch policy, is applied; and

a prefetch filter configured to select a prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy based on the at least one miss state of the miss tracking circuit.

2. The adaptive cache prefetch circuit of claim 1, wherein the prefetch filter is further configured to select the prefetch policy to be applied to a prefetch request issued by a prefetch control circuit to cause the cache to be filled.

3. The adaptive cache prefetch circuit of claim 1, wherein:

the at least one first dedicated prefetch policy is comprised of a first dedicated prefetch policy;

the at least one second dedicated prefetch policy is comprised of a second dedicated prefetch policy; and

the prefetch filter is configured to select the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, based on the at least one miss state of the miss tracking circuit.

4. The adaptive cache prefetch circuit of claim 3, wherein:

the first dedicated prefetch policy is comprised of a never prefetch policy; and

the second dedicated prefetch policy is comprised of an always prefetch policy.

5. The adaptive cache prefetch circuit of claim 1, wherein the miss tracking circuit is comprised of at least one miss counter, and the at least one miss state is comprised of at least one miss count;

the at least one miss counter configured to update the at least one miss count based on the cache miss resulting from the accessed cache entry in the at least one first dedicated cache set and the at least one second dedicated cache set; and

the prefetch filter configured to select the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, based on the at least one miss count of the at least one miss counter.

6. The adaptive cache prefetch circuit of claim 1, wherein the miss tracking circuit is comprised of a miss saturation indicator and the at least one miss state is comprised of a miss state,

the miss saturation indicator configured to update the miss state based on the cache miss resulting from the accessed cache entry in the at least one first dedicated cache set and the at least one second dedicated cache set;

and

the prefetch filter configured to select the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, based on the miss state of the miss saturation indicator.

7. The adaptive cache prefetch circuit of claim 6, wherein the miss saturation indicator is comprised of a miss saturation counter and the miss state is comprised of a miss saturation count;

the miss saturation counter configured to update the miss saturation count based on the cache miss resulting from the accessed cache entry in the at least one first dedicated cache set and the at least one second dedicated cache set; and

the prefetch filter configured to select the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, based on the miss saturation count of the miss saturation counter.

8. The adaptive cache prefetch circuit of claim 7, wherein the miss saturation counter is configured to update the miss saturation count by being configured to:

update the miss saturation count by incrementing or decrementing the miss saturation count, based on the cache miss resulting from the accessed cache entry in the at least one first dedicated cache set in the cache for which the at least one first dedicated prefetch policy is applied; and

update the miss saturation count by decrementing or incrementing the miss saturation count, respectively, based on the cache miss resulting from the accessed cache entry in the at least one second dedicated cache set in the cache for which the at least one second dedicated prefetch policy, different from the at least one first dedicated prefetch policy, is applied.

9. The adaptive cache prefetch circuit of claim 1, wherein the miss tracking circuit is comprised of a plurality of miss indicators each comprising a miss state, each of the plurality of miss indicators associated with a dedicated cache set among the at least one first dedicated cache set and the at least one second dedicated cache set;

the plurality of miss indicators each further configured to update the associated miss state based on the cache miss resulting from the accessed cache entry in the dedicated cache set among the at least one first dedicated cache set and the at least one second dedicated cache set in the cache; and

the prefetch filter configured to select the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, based on a comparison of the at least one miss state in the plurality of the miss indicators.

10. The adaptive cache prefetch circuit of claim 1, wherein the prefetch filter is further configured to selectively not select the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, based on the at least one miss state of the miss tracking circuit.

11. The adaptive cache prefetch circuit of claim 7, wherein the prefetch filter is further configured to selectively not select the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, to be applied to the prefetch request issued by the prefetch control circuit based on at least one significant bit in the miss saturation count of the miss saturation counter.

12. The adaptive cache prefetch circuit of claim 1, wherein the prefetch filter is further configured to always not select the at least one first dedicated prefetch policy or the at least one second dedicated prefetch policy.

13. The adaptive cache prefetch circuit of claim 1, wherein the prefetch filter is further configured to:

probabilistically determine if the at least one first dedicated prefetch policy or the at least one second dedicated prefetch policy, should be applied to a prefetch request issued by a prefetch control circuit based on the at least one miss state of the miss tracking circuit; and

select the at least one first dedicated prefetch policy or the at least one second dedicated prefetch policy, to be applied to the prefetch request issued by the prefetch control circuit, based on the probabilistic determination.

14. The adaptive cache prefetch circuit of claim 1, wherein:

the cache comprising a plurality of cache sets each configured to store one or more cache entries, the plurality of cache sets comprising;

the at least one first dedicated cache set configured to receive prefetched cache data based on the at least one first dedicated prefetch policy;

the at least one second dedicated cache set configured to receive the prefetched cache data based on the at least one second dedicated prefetch policy; and

at least one follower cache set configured to receive the prefetched cache data based on either the at least one first dedicated prefetch policy or the least one second dedicated prefetch policy;

a cache controller configured to receive a memory access request comprising a memory address and determine if a cache entry corresponding to the memory address is contained in the cache; and

a prefetch control circuit configured to issue a prefetch request to prefetch the prefetched cache data into the plurality of cache sets in the cache according to the prefetch policy.

15. The adaptive cache prefetch circuit of claim 14, wherein the prefetch filter is disposed outside of the cache controller.

16. The adaptive cache prefetch circuit of claim 14, wherein the cache controller comprises the prefetch filter

17. The adaptive cache prefetch circuit of claim 1 disposed into an integrated circuit (IC).

18. The adaptive cache prefetch circuit of claim 1 integrated into a device selected from the group consisting of a set top box, an entertainment unit, a navigation device, a communications device, a fixed location data unit, a mobile location data unit, a mobile phone, a cellular phone, a computer, a portable computer, a desktop computer, a personal digital assistant (PDA), a monitor, a computer monitor, a television, a tuner, a radio, a satellite radio, a music player, a digital music player, a portable music player, a digital video player, a video player, a digital video disc (DVD) player, and a portable digital video player.

19. An adaptive cache prefetch circuit for prefetching cache data into a cache, comprising:

a miss tracking means for updating at least one miss state means based on a cache miss resulting from an accessed cache entry in;

at least one first dedicated cache set in a cache for which at least one first dedicated prefetch policy is applied, and at least one second dedicated cache set in the cache for which at least one second dedicated prefetch policy, different from the at least one first dedicated prefetch policy, is applied; and

a prefetch filter means for selecting a prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy based on the at least one miss state means of the miss tracking means.

20. A method of adaptive cache prefetching based on competing dedicated prefetch policies in dedicated cache sets, comprising:

receiving a memory access request comprising a memory address to be addressed in a cache;

determining if the memory access request is a cache miss by determining if an accessed cache entry among a plurality of cache entries in the cache corresponding to the memory address, is contained in the cache;

updating at least one miss state of a miss tracking circuit based on the cache miss resulting from the accessed cache entry in;

at least one first dedicated cache set in the cache for which at least one first dedicated prefetch policy is applied, and at least one second dedicated cache set in the cache for which at least one second dedicated prefetch policy, different from the at least one first dedicated prefetch policy, is applied;

issuing a prefetch request to prefetch cache data into a cache entry in a follower cache set among a plurality of cache sets in the cache;

selecting a prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, to be applied to the prefetch request, based on the at least one miss state of the miss tracking circuit; and

filling the prefetched cache data into the cache entry in the follower cache set based on the selected prefetch policy.

21. The method of claim 20, wherein updating the miss tracking circuit comprises:

updating the at least one miss state of the miss tracking circuit based on the cache miss resulting from the accessed cache entry to the at least one first dedicated cache set in the cache, for which a never prefetch policy is applied; and

updating the at least one miss state of the miss tracking circuit based on the cache miss resulting from the accessed cache entry to the at least one second dedicated cache set in the cache, for which an always prefetch policy is applied.

22. The method of claim 20, wherein:

updating the at least one miss state of the miss tracking circuit comprises updating at least one miss count of at least one miss counter based on the cache miss resulting from the accessed cache entry in;

the at least one first dedicated cache set in the cache, for which the at least one first dedicated prefetch policy is applied, and the at least one second dedicated cache set in the cache, for which the at least one second dedicated prefetch policy, different from the at least one first dedicated prefetch policy, is applied; and

selecting the prefetch policy comprises selecting the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, to be applied to the prefetch request, based on the at least one miss count of the at least one miss counter.

23. The method of claim 22, wherein:

updating the at least one miss count of the at least one miss counter comprises updating at least one miss saturation count of at least one miss saturation counter, based on the cache miss resulting from the accessed cache entry in;

the at least one first dedicated cache set in the cache for which the at least one first dedicated prefetch policy is applied, and the at least one second dedicated cache set in the cache, for which the at least one second dedicated prefetch policy, different from the at least one first dedicated prefetch policy, is applied; and

selecting the prefetch policy comprises selecting the prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, to be applied to the prefetch request, based on the at least one miss saturation count of the at least one miss saturation counter.

24. The method of claim 23, wherein updating the at least one miss saturation count of the at least one miss saturation counter, comprises:

incrementing or decrementing the at least one miss saturation count of the at least one miss saturation counter, based on the cache miss resulting from the accessed cache entry in the at least one first dedicated cache set in the cache for which the at least one first dedicated prefetch policy is applied; and

decrementing or incrementing, respectively, the at least one miss saturation count of the at least one miss saturation counter, based on the cache miss resulting from the accessed cache entry in the at least one second dedicated cache set in the cache for which the at least one second dedicated prefetch policy, different from the at least one first dedicated prefetch policy, is applied.

25. The method of claim 20, further comprising ignoring the at least one first dedicated prefetch policy as the selected prefetch policy or the at least one second dedicated prefetch policy as the selected prefetch policy.

26. The method of claim 20, further comprising probabilistically determining if the at least one first dedicated prefetch policy or the at least one second dedicated prefetch policy should be selected as the selected prefetch policy;

wherein filling the prefetched cache data comprises filling the prefetched cache data into the cache entry in the follower cache set based on the probabilistically determined prefetch policy.

27. A non-transitory computer-readable medium having stored thereon computer executable instructions to cause a processor-based adaptive cache prefetch circuit to prefetch cache data into a cache, by:

updating at least one miss state of a miss tracking circuit based on a cache miss resulting from an accessed cache entry in;

at least one first dedicated cache set in a cache for which at least one first dedicated prefetch policy is applied, and at least one second dedicated cache set in the cache for which at least one second dedicated prefetch policy, different from the at least one first dedicated prefetch policy, is applied; and

selecting a prefetch policy from among the at least one first dedicated prefetch policy and the at least one second dedicated prefetch policy, to be applied in a prefetch request issued by a prefetch control circuit to cause the cache to be filled, based on the at least one miss state of the miss tracking circuit.

28. The non-transitory computer-readable medium of claim 27 having stored thereon the computer executable instructions to cause the processor-based adaptive cache prefetch circuit to prefetch cache data into the cache by updating the at least one miss state of the miss tracking circuit by:

updating the at least one miss state of the miss tracking circuit based on the cache miss resulting from the accessed cache entry to the at least one first dedicated cache set in the cache, for which a never prefetch policy is applied; and

updating the at least one miss state of the miss tracking circuit based on the cache miss resulting from the accessed cache entry to the at least one second dedicated cache set in the cache for which an always prefetch policy is applied.

29. The non-transitory computer-readable medium of claim 27 having stored thereon the computer executable instructions to cause the processor-based adaptive cache prefetch circuit to prefetch cache data into the cache by ignoring the at least one first dedicated prefetch policy as the selected prefetch policy or the at least one second dedicated prefetch policy as the selected prefetch policy.