Coordinated prefetching based on training in hierarchically cached processors

• US 9,098,418 B2
• Filed: 03/20/2012
• Issued: 08/04/2015
• Est. Priority Date: 03/20/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Kannan, Hari S., Lilly, Brian P., Williams, Gerard R. III, Sadoughi-Yarandi, Mahnaz, Subramoniam, Perumal R., Kanapathipillai, Pradeep
• Primary Examiner(s): KIM, HONG CHONG
• Application Number:
  US13/425,123
• Publication Number:
  US 20130254485A1
• Time in Patent Office: 1,232 Days
• Field of Search: 711/137, 711/122, 711/213, 712/233, 712/237, 712/240
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 2212/6028 Prefetching based on hints or prefetch instructions
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions

Abstract

Processors and methods for coordinating prefetch units at multiple cache levels. A single, unified training mechanism is utilized for training on streams generated by a processor core. Prefetch requests are sent from the core to lower level caches, and a packet is sent with each prefetch request. The packet identifies the stream ID of the prefetch request and includes relevant training information for the particular stream ID. The lower level caches generate prefetch requests based on the received training information.

Claims

1. A processor comprising:

a cache hierarchy comprising at least two caches arranged in two levels;

a first prefetch unit associated with a first cache of the at least two caches, wherein the first prefetch unit is configured to maintain a first prefetch table comprising a plurality of entries, wherein each entry comprises a stream identifier (ID) and attributes associated with a corresponding stream;

a second prefetch unit associated with a second cache of the at least two caches, the second prefetch unit being different from the first prefetch unit, wherein the second prefetch unit is configured to maintain a second prefetch table with an entry for each entry in the first prefetch table including a stream ID and attributes associated with a corresponding stream; and

a prefetch training mechanism associated with the first cache;

wherein the prefetch training mechanism is configured to generate training information for each of a plurality of streams, wherein the training information is utilized for determining whether the first prefetch unit is to issue prefetch requests for data corresponding to the plurality of streams into the first cache;

wherein the prefetch unit is configured to convey said training information to the second prefetch unit; and

wherein said second prefetch unit is configured to issue prefetch requests for data corresponding to a plurality of streams into the second cache based on attributes stored in the second prefetch table.

2. The processor as recited in claim 1, wherein said second prefetch unit does not perform any training for prefetches.

3. The processor as recited in claim 1, wherein said training information includes temporal data that is used by the second cache as part of a cache replacement policy.

4. The processor as recited in claim 3, wherein the first prefetch unit is configured to:

generate a prefetch request for a given stream based on attributes stored in a corresponding entry in the first prefetch table; and

convey the prefetch request and a packet to the second cache, wherein the packet comprises one or more attributes from the corresponding entry in the first prefetch table.

5. The processor as recited in claim 4, wherein the second prefetch unit is further configured to:

detect a page boundary for a given stream; and

stop prefetching responsive to detecting said page boundary.

6. The processor as recited in claim 1, wherein training information in the second prefetch table is synchronized with training information in the first prefetch table.

7. The processor as recited in claim 1, wherein the second prefetch unit is configured to:

count a number of prefetch requests issued by the first prefetch unit; and

increase a number of prefetch requests generated by the second prefetch unit in response to determining said number exceeds a threshold.

8. The processor as recited in claim 1, wherein the prefetch training mechanism is coupled to a highest level of cache of the plurality of levels of caches and generates training information for a plurality of streams, wherein the training information is utilized for generating prefetch requests at each of the plurality of levels of caches.

9. The processor as recited in claim 1, wherein said attributes in the first prefetch table comprise an indication of whether a corresponding stream is a load stream or a store stream.

10. The processor as recited in claim 8, wherein the prefetch unit is configured to:

generate a plurality of prefetch requests based on the training information;

generate a packet for each prefetch request, wherein the packet comprises attributes associated with the prefetch request and a corresponding stream; and

convey the prefetch request and the packet to a lower level cache.

11. The processor as recited in claim 1, wherein said training information further comprises data used by the second cache to bias way selection in a cache replacement policy.

12. The processor as recited in claim 11, wherein the attributes further comprises a stride of the corresponding stream.

13. The processor as recited in claim 11, wherein the prefetch unit is further configured to assign a load stream and a store stream with a single stream identifier, responsive to detecting accesses by the load stream and the store stream to a same address.

14. A method comprising:

generating training information on a plurality of streams, wherein the training is performed by a prefetch training mechanism coupled to a first cache at a first cache level, wherein said training information is utilized to determine whether prefetch requests are to be issued by a first prefetch unit corresponding to the plurality of streams into the first cache; and

storing the training information in a first table at the first cache level, wherein the first table comprises a plurality of entries, each entry comprising a stream identifier (ID) and attributes associated with a corresponding stream;

conveying said training information to a second cache level;

storing the training information in a second table at the second cache level, wherein the second table comprises a plurality of entries, each entry comprising a stream identifier (ID) and attributes associated with a corresponding stream; and

a second prefetch unit, different from the first prefetch unit, coupled to said second cache at said second cache level issuing prefetch requests for a plurality of streams into the second cache based on attributes stored in the second prefetch table.

15. The method as recited in claim 14, wherein said second prefetch unit does not perform any training for prefetches.

16. The method as recited in claim 15,

wherein the second table is synchronized with the first table.

17. The method as recited in claim 14, further comprising:

counting by the second prefetch unit a number of prefetch requests issued by the first prefetch unit; and

increasing a number of prefetch requests generated by the second prefetch unit in response to determining said number exceeds a threshold.

18. The method as recited in claim 17, wherein said training information includes temporal data that is used by the second cache as part of a cache replacement policy.

19. The method as recited in claim 16, further comprising storing the training information in a third table at the third cache level, wherein the third table is synchronized with the second table.

20. The method as recited in claim 15, wherein the first cache level is a level one (L1) cache, wherein the second cache level is a level two (L2) cache.