List-based prefetching

• US 9,348,755 B2
• Filed: 10/09/2013
• Issued: 05/24/2016
• Est. Priority Date: 10/12/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boettiger, Hans, Maurer, Thilo
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Phan, Dean
• Application Number:
  US14/049,287
• Publication Number:
  US 20140108741A1
• Time in Patent Office: 958 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers

Abstract

A computer implemented method for prefetching data for a processor into a first memory, wherein in a recording mode, a prefetching unit for a processor performs the steps of a method. The method includes: receiving one or more first addresses from the processor; filtering the one or more first addresses; providing a recording-list including the filtered one or more first addresses; receiving at least one second address from the processor; receiving a playback-list including all or a subset of the first addresses of the recording-list; comparing the at least one second address with each of the first addresses in the playback-list for identifying a matching address; if a matching address is identified, fetching data from a second memory; and transferring the fetched data to a first memory.

Claims

1. A computer implemented method for prefetching data for a processor into a first memory, wherein in a recording mode, a prefetching unit of the processor performs the steps of a method comprising:

receiving one or more first addresses from the processor, wherein the one or more first addresses is a load address;

filtering the one or more first addresses for removing at least some of the first addresses from a list;

providing a recording-list including the filtered one or more first addresses, wherein in a playback mode, the prefetching unit executes;

receiving at least one second address from the processor, wherein the at least one second address is a load address;

receiving a playback-list, wherein the playback-list includes all or a subset of the first addresses in the recording-list;

comparing the at least one second address with each of the first addresses in the playback-list for identifying a matching address within the playback-list;

fetching data, in case a matching address is identified, from a second memory, wherein the fetched data is identified by addresses sequential to the position of the matching address in the playback-list; and

transferring the fetched data to the first memory, wherein the first and the second memory are caches within a multi-level cache of the processor,

wherein the prefetchinq unit enters the recording mode upon starting the prefetchinq unit or upon executing a program loop a first time, thereby generating the recording-list and wherein the prefetching unit enters playback-mode in respect to the recording-list executing the program loop.

2. The computer implemented method of claim 1, wherein filtering comprises:

removing the first addresses which lie within an address interval and/or lie outside an address interval; and

removing the first addresses which follow an address pattern and/or are duplicates of another one of the first addresses in the list, wherein a duplicate first address lies within a predefined number of most recently added first addresses within the list.

3. The computer implemented method of claim 2, wherein the step of filtering is executed by a filtering unit of the prefetching unit, the filtering unit comprising:

configuring a filter comprising a configuration storage, thereby setting the address interval, the address pattern, and/or the predefined number in the configuration storage, wherein the configuring is implemented as a configuration technique selected from a group consisting of;

a first technique or a second technique, wherein;

the first technique includes compilation of an executable source code, evaluating, by a compiler, user-specified filtering-annotations within the source code, injecting, by the compiler, filter configuration commands into the compiled code in accordance with the filtering annotations, and storing, by the processor executing the compiled code, the configuration of the filtering unit in accordance with the configuration commands in the configuration storage; and

the second technique includes compilation of an executable source code, evaluating, by a compiler, the source code, wherein the source code is free of user-specified filtering-annotations, injecting, by the compiler, filter configuration commands into the compiled code in accordance with the evaluation results, and storing, by the processor executing the compiled code, the configuration of the filtering unit in accordance with the configuration commands in the configuration storage.

4. The computer implemented method of claim 3, wherein the configuration storage of the filtering includes MMIO registers being readable and writable by the processor.

5. The computer implemented method of claim 1, wherein the recording mode comprises:

storing the recording-list to a write buffer;

writing the recording-list to a pre-allocated memory area;

emptying the write buffer and the recording-list, wherein playback mode further comprises, upon each identification of a current matching address in the playback-list;

determining a first address position within the playback-list, the first address position being the position of the current matching address;

selecting all first addresses in the playback-list directly succeeding the first address position, the selected first addresses having been received and added to the recording-list later than the matching address;

moving the selected first addresses to a corresponding number of address positions in the playback-list at the begin of the playback-list, thereby overwriting all addresses stored in the corresponding number of address positions and creating one or more empty address positions at the end of the play-back list; and

filling all empty address positions by reading a corresponding number of first addresses from the recording list, the read first addresses directly succeeding the last one of the moved selected first addresses;

wherein the first addresses in the recording-list and in the playback-list are ordered chronologically in accordance with the time of being received from the processor.

6. The computer implemented method of claim 1, wherein receiving the first addresses from the processor comprises:

receiving, by the prefetching unit, the first addresses from ports of the processor, or receiving, by the prefetching unit, the first addresses from the processor after the first addresses have been used by the processor for reading data from the first memory.

7. The computer implemented method of claim 6, wherein the first addresses are received from the processor after the first addresses have been used by the processor for reading data from the first memory and wherein the received first addresses are flagged as a hit address or a miss address and the flagging is evaluated by the filtering unit for filtering out one or more of the first addresses.

8. The computer implemented method of claim 1, wherein the first memory is an L1 data cache of the processor and wherein the second memory is an L2 data cache of the processor.

9. The computer implemented method of claim 1, wherein:

the prefetching unit is one of a plurality of prefetching units;

the processor is one of a plurality of processors, the plurality of processors share the second memory, and each processor is assigned a respective one of the prefetching units; and

the first memory is one of a plurality of first memories, each of the first memories is assigned to a respective one of the processors, each processor being operable to execute one or more threads, and the threads of each processor share the first memory assigned to the processor.

10. The computer implemented method of claim 1, wherein:

the processor is operable to execute a number (n) of threads in parallel;

the prefetching unit of the processor comprises the number (n) of filtering units;

the prefetching unit of the processor is operable to manage one recording-list and one playback-list for each of the number (n) of threads; and

the prefetching unit comprises one prefetch-engine for fetching the data from the second memory and for transferring the data to the first memory for each of the number (n) of threads.

11. The computer implemented method of claim 1, wherein:

the received one or more first addresses and the at least one second addresses are virtual addresses pointing to cache lines in the second memory;

a matching unit of the prefetching unit uses the virtual addresses for executing the address comparison; and

the first addresses in the recording-list in the pre-allocated memory area are virtual addresses.

12. The method of claim 11, further comprising:

translating, by a translation unit of the prefetching unit or by a translation unit external to the prefetching unit, each of the first addresses in the playback-list into a physical address; and

executing the fetching of the data from the second memory by using the physical address.

13. The computer implemented method of claim 1, wherein:

the allocated memory area is one of at least a first and a second allocated memory area respectively being used for storing a recording-list;

the prefetching unit is in recording-mode in respect to a first recording list using the first allocated memory area for storing the first recording-list; and

the prefetching unit, simultaneously, is in playback-mode in respect to a second recording list using the second allocated memory for storing the second recording list and for playing-back the second recording list.

14. A computer implemented method for prefetching data for a processor into a first memory, wherein in a recording mode, a prefetching unit of the processor performs the steps of a method comprising:

receiving one or more first addresses from the processor, wherein the one or more first addresses is a load address;

filtering the one or more first addresses for removing at least some of the first addresses from a list;

providing a recording-list including the filtered one or more first addresses, wherein in a playback mode, the prefetching unit executes;

receiving at least one second address from the processor, wherein the at least one second address is a load address;

receiving a playback-list, wherein the playback-list includes all or a subset of the first addresses in the recording-list;

comparing the at least one second address with each of the first addresses in the playback-list for identifying a matching address within the playback-list;

fetching data, in case a matching address is identified, from a second memory, wherein the fetched data is identified by addresses sequential to the position of the matching address in the playback-list; and

transferring the fetched data to the first memory, wherein the first and the second memory are caches within a multi-level cache of the processor,

wherein;

the processor executes a number (n) of threads in parallel,

the prefetching unit of the processor comprises the number (n) of filtering units,

the prefetching unit of the processor manages one recording-list and one playback-list for each of the number (n) of threads, and

the prefetching unit comprises one prefetch-engine for fetching the data from the second memory and for transferring the data to the first memory for each of the number (n) of threads.

15. A computer implemented method for prefetching data for a processor into a first memory, wherein in a recording mode, a prefetching unit of the processor performs the steps of a method comprising:

receiving one or more first addresses from the processor, wherein the one or more first addresses is a load address;

filtering the one or more first addresses for removing at least some of the first addresses from a list;

providing a recording-list including the filtered one or more first addresses, wherein in a playback mode, the prefetching unit executes;

receiving at least one second address from the processor, wherein the at least one second address is a load address;

receiving a playback-list, wherein the playback-list includes all or a subset of the first addresses in the recording-list;

comparing the at least one second address with each of the first addresses in the playback-list for identifying a matching address within the playback-list;

fetching data, in case a matching address is identified, from a second memory, wherein the fetched data is identified by addresses sequential to the position of the matching address in the playback-list; and

transferring the fetched data to the first memory, wherein the first and the second memory are caches within a multi-level cache of the processor,

wherein;

the allocated memory area is one of at least a first and a second allocated memory area respectively being used for storing a recording-list,

the prefetching unit is in recording-mode in respect to a first recording list using the first allocated memory area for storing the first recording-list, and

the prefetching unit, simultaneously, is in playback-mode in respect to a second recording list using the second allocated memory for storing the second

recording list and for playing-back the second recording list.