Methods and apparatus for training prefetch information

Patent metadata

Field	Value
Publication number	US-11599473-B1
Application number	US-202117505957-A
Country	US
Kind code	B1
Filing date	Oct 20, 2021
Priority date	Oct 20, 2021
Publication date	Mar 7, 2023
Grant date	Mar 7, 2023

Abstract

Aspects of the present disclosure relate to an apparatus comprising prefetch information storage circuitry and prefetch training circuitry. The prefetch training circuitry comprises a plurality of entries, and is configured to: allocate a given entry to a given data address region; receive access information indicative of data accesses within the given data address region; based on said access information, train prefetch information associated with the given data address region, the prefetch information being indicative of a pattern of said data accesses within the given data address region; and responsive to an eviction condition being met after an elapsed period, since said allocation of the given entry, has exceeded a threshold, perform an eviction comprising transferring the prefetch information associated with the given data address region to the prefetch information storage circuitry.

First claim

We claim:

1. An apparatus comprising:
prefetch information storage circuitry to store prefetch information associated with respective data address regions, the prefetch information in respect of a given data address region identifying expected access patterns associated with the given data address region;
prefetch training circuitry, comprising a plurality of entries, to:
allocate a given entry to a given data address region;
receive access information indicative of data accesses within the given data address region;
based on said access information, train prefetch information associated with the given data address region, the prefetch information being indicative of a pattern of said data accesses within the given data address region; and
responsive to an eviction condition being met after an elapsed period, since said allocation of the given entry, has exceeded a threshold, perform an eviction comprising transferring the prefetch information associated with the given data address region to the prefetch information storage circuitry.

2. An apparatus according to claim 1 , wherein:
said expected access patterns are spatial access patterns; and
the pattern of said data accesses is a spatial pattern of said data accesses.

3. An apparatus according to claim 2 , wherein the prefetch information storage circuitry stores the prefetch information in a spatial pattern history table.

4. An apparatus according to claim 1 , wherein the prefetch training circuitry is configured to:
maintain a cooldown counter which, when started, expires after a cooldown period has elapsed;
maintain a next eviction identifier to identify a next entry to be evicted; and
responsive to the eviction condition being met after the cooldown counter has expired, evicting said next entry to be evicted, starting the cooldown counter, and configuring the next eviction identifier to identify a new next entry to be evicted.

5. An apparatus according to claim 4 , wherein the prefetch training circuitry is configured to identify the new next entry to be evicted based on an eviction policy.

6. An apparatus according to claim 4 , wherein the prefetch training circuitry is configured to identify the new next entry to be evicted as an oldest entry of said plurality of entries.

7. An apparatus according to claim 6 , wherein:
the next eviction identifier is a round robin pointer; and
the prefetch training circuitry is configured to identify the new next entry to be evicted by incrementing the round robin pointer.

8. An apparatus according to claim 4 , wherein the prefetch training circuitry is configured to block received entry allocation requests whilst the cooldown counter is running.

9. An apparatus according to claim 4 , wherein the cooldown period is an integer number of prefetch information training operations.

10. An apparatus according to claim 9 , wherein said integer number is a prime number.

11. An apparatus according to claim 4 , wherein said threshold time is equal to the product of the cooldown time period and the number of said plurality of entries.

12. An apparatus according to claim 1 , wherein the prefetch training circuitry is configured to:
maintain an entry-specific cooldown counter in respect of each said entry, each cooldown counter being configured to, when started, expire after said threshold has elapsed;
start the cooldown counter, in respect of a given entry, responsive to allocating that given entry; and
responsive to the cooldown counter in respect of a given entry having expired, determine that the threshold has been exceeded in respect of that given entry.

13. An apparatus according to claim 12 , wherein the prefetch circuitry is configured to dynamically increase said threshold, in respect of a given entry, in response to a threshold increase determination.

14. An apparatus according to claim 13 , wherein the threshold increase determination is responsive to determining that training of said given entry is expected to improve given said increased threshold time; and wherein the threshold increase determination is a random selection of allocated entries.

15. An apparatus according to claim 14 , wherein the prefetching circuitry is configured to determine that training of said given entry is expected to improve based on continuing receiving of access information in respect of said given entry.

16. An apparatus according to claim 13 , wherein the prefetch training circuitry is configured to: responsive to said increased threshold leading to an increased quantity of access information in respect of the given entry, identify a data address region, to which the given entry is allocated, for future application of the increased threshold; and responsive to subsequently allocating a given new entry to said given data region, apply the increased threshold to said given new entry.

17. An apparatus according to claim 1 , wherein: said eviction condition is met in response to receiving access information in respect of a given data region having no associated entry; and the prefetch training circuitry is responsive to evicting said given entry to allocate said given entry to said given data region.

18. An apparatus according to claim 1 , comprising prefetch circuitry to: receive said access information; and based on said access information, and on corresponding prefetch information in the prefetch information storage circuitry, prefetch data into a temporary storage in advance of an anticipated use of said data by processing circuitry.

19. A system comprising: the apparatus of claim 1 ; and processing circuitry configured to access data and, based on said data access, provide said access information to the prefetch training circuitry.

20. A method comprising: storing, in prefetch information storage, prefetch information associated with respective data address regions, the prefetch information in respect of a given data address region identifying expected access patterns associated with the given data address region; allocating a given entry to a given data address region; receiving access information indicative of data accesses within the given data address region; based on said access information, training prefetch information associated with the given data address region, the prefetch information being indicative of a pattern of said data accesses within the given data address region; and responsive to an eviction condition being met after an elapsed period, since said allocation of the given entry, has exceeded a threshold, performing an eviction comprising transferring the prefetch information associated with the given data address region to the prefetch information storage.

Assignees

• Advanced Risc Mach Ltd

Inventors

• Lafford Devin S
• Shulyak Alexander Cole

Classifications

• G06F2212/6024

  History based prefetching · CPC title

• G06F12/0862 Primary

  with prefetch · CPC title

• G06F12/0284

  Multiple user address space allocation, e.g. using different base addresses (interprocessor communication G06F15/163) · CPC title

• G06F2212/502

  using adaptive policy · CPC title

• G06F2212/1016

  Performance improvement · CPC title