Prefetching irregular data references for software controlled caches

• US 8,239,841 B2
• Filed: 04/04/2008
• Issued: 08/07/2012
• Est. Priority Date: 04/04/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Tong, Gonzalez tallada, Marc, Sura, Zehra N., Zhang, Tao
• Primary Examiner(s): Zhen, Li
• Assistant Examiner(s): NGUYEN, DUY KHUONG THANH
• Application Number:
  US12/062,579
• Publication Number:
  US 20090254895A1
• Time in Patent Office: 1,586 Days
• Field of Search: 717/140, 717150-151
• US Class Current: 717/140
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

Prefetching irregular memory references into a software controlled cache is provided. A compiler analyzes source code to identify at least one of a plurality of loops that contain an irregular memory reference. The compiler determines if the irregular memory reference within the at least one loop is a candidate for optimization. Responsive to an indication that the irregular memory reference may be optimized, the compiler determines if the irregular memory reference is valid for prefetching. Responsive to an indication that the irregular memory reference is valid for prefetching, a store statement for an address of the irregular memory reference is inserted into the at least one loop. A runtime library call is inserted into a prefetch runtime library for the irregular memory reference. Data associated with the irregular memory reference is prefetched into the software controlled cache when the runtime library call is invoked.

Claims

1. A method, in a data processing system, for prefetching irregular memory references into a software controlled cache, the method comprising:

receiving source code that is to be compiled;

analyzing the source code to identify at least one of a plurality of loops that contain an irregular memory reference;

determining if the irregular memory reference within the at least one of the plurality of loops is a candidate for optimization;

responsive to an indication that the irregular memory reference may be optimized, determining if the irregular memory reference is valid for prefetching;

responsive to an indication that the irregular memory reference is valid for prefetching, inserting a store statement for an address of the irregular memory reference into the at least one of the plurality of loops;

inserting a runtime library call into a prefetch runtime library for the irregular memory reference, wherein data associated with the irregular memory reference is prefetched into the software controlled cache when the runtime library call is invoked; and

wherein determining if the irregular memory reference within the at least one of the plurality of loops is the candidate for optimization comprises;

determining if a computed address accessed by the irregular memory reference is an affine function of a loop index variable;

responsive to the address failing to be the affine function of the loop index variable, determining if there is a loop-carried dependency between statements used in the computed address; and

responsive to failure to identify any loop-carried dependencies, indicating the irregular memory reference as the candidate for optimization.

2. The method of claim 1, wherein determining if the irregular memory reference is valid for prefetching comprises:

back-slicing the address of the irregular memory reference to determine if a computed address for the irregular memory reference contains a cache reference thereby forming a back-sliced address; and

responsive to the back-sliced address failing to contain the cache reference, indicating the irregular memory reference as valid for prefetching.

3. The method of claim 1, wherein the store statement records one or more addresses for the data accessed by the irregular memory reference across all loop iterations and wherein the one or more address are written into a temporary array.

4. The method of claim 1, further comprising:

distributing the at least one of the plurality of loops into an address collection loop and a computation loop; and

inserting the runtime library call into the prefetch runtime library for the irregular memory reference between the address collection loop and the computation loop.

5. The method of claim 1, further comprising:

receiving a request to prefetch the data within the at least one of the plurality of loops;

determining if a temporary array associated with the at least one of the plurality of loops contains more than one data access for a plurality of irregular memory references;

responsive to the temporary array containing only one data access, determining if the data associated with the irregular memory reference exists in the software controlled cache; and

responsive to the data failing to exist within the software controlled cache, prefetching the data into the software controlled cache.

6. The method of claim 5, further comprising:

responsive to the temporary array containing more than one data access, invoking a first function within the temporary array;

for each of a plurality of second functions associated with the first function, determining if the data associated with each second function exists in the software controlled cache; and

responsive to the data associated with each second function failing to exist within the software controlled cache, invoking the second function to prefetch the data associated with the second function into the software controlled cache.

7. A computer program product comprising a non-transitory computer readable medium storing a computer readable program recorded thereon, wherein the computer readable program, when executed on a computing device, causes the computing device to:

receive source code that is to be compiled;

analyze the source code to identify at least one of a plurality of loops that contain an irregular memory reference;

determine if the irregular memory reference within the at least one of the plurality of loops is a candidate for optimization;

responsive to an indication that the irregular memory reference may be optimized, determine if the irregular memory reference is valid for prefetching;

responsive to an indication that the irregular memory reference is valid for prefetching, insert a store statement for an address of the irregular memory reference into the at least one of the plurality of loops;

insert a runtime library call into a prefetch runtime library for the irregular memory reference, wherein data associated with the irregular memory reference is prefetched into the software controlled cache when the runtime library call is invoked; and

wherein the computer readable program to determine if the irregular memory reference within the at least one of the plurality of loops is the candidate for optimization, wherein the computer readable program further causes the computing device to;

determine if a computed address accessed by the irregular memory reference is an affine function of a loop index variable;

responsive to the address failing to be the affine function of the loop index variable, determine if there is a loop-carried dependency between statements used in the computed address; and

responsive to failure to identify any loop-carried dependencies, indicate the irregular memory reference as the candidate for optimization.

8. The computer program product of claim 7, wherein the computer readable program to determine if the irregular memory reference is valid for prefetching further comprises computer readable program that causes the'"'"'computing device to:

back-slice the address of the irregular memory reference to determine if a computed address for the irregular memory reference contains a cache reference thereby forming a back-sliced address; and

responsive to the back-sliced address failing to contain the cache reference, indicate the irregular memory reference as valid for prefetching.

9. The computer program product of claim 7, wherein the store statement records one or more addresses for the data accessed by the irregular memory reference across all loop iterations and wherein the one or more address are written into a temporary array.

10. The computer program product of claim 7, wherein the computer readable program further causes the computing device to:

distribute the at least one of the plurality of loops into an address collection loop and a computation loop; and

insert the runtime library call into the prefetch runtime library for the irregular memory reference between the address collection loop and the computation loop.

11. The computer program product of claim 7, wherein the computer readable program further causes the computing device to:

receive a request to prefetch the data within the at least one of the plurality of loops;

determine if a temporary array associated with the at least one of the plurality of loops contains more than one data access for a plurality of irregular memory references;

responsive to the temporary array containing only one data access, determine if the data associated with the irregular memory reference exists in the software controlled cache; and

responsive to the data failing to exist within the software controlled cache, prefetch the data into the software controlled cache.

12. The computer program product of claim 11, wherein the computer readable program further causes the computing device to:

responsive to the temporary array containing more than one data access, invoke a first function within the temporary array;

for each of a plurality of second functions associated with the first function, determine if the data associated with each second function exists in the software controlled cache; and

responsive to the data associated with each second function failing to exist within the software controlled cache, invoke the second function to prefetch the data associated with the second function into the software controlled cache.

13. An apparatus, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

receive source code that is to be compiled;

analyze the source code to identify at least one of a plurality of loops that contain an irregular memory reference;

determine if the irregular memory reference within the at least one of the plurality of loops is a candidate for optimization;

responsive to an indication that the irregular memory reference may be optimized, determine if the irregular memory reference is valid for prefetching;

responsive to an indication that the irregular memory reference is valid for prefetching, insert a store statement for an address of the irregular memory reference into the at least one of the plurality of loops;

insert a runtime library call into a prefetch runtime library for the irregular memory reference, wherein data associated with the irregular memory reference is prefetched into the software controlled cache when the runtime library call is invoked; and

wherein the instructions to determine if the irregular memory reference within the at least one of the plurality of loops is the candidate for optimization further cause the processor to;

determine if a computed address accessed by the irregular memory reference is an affine function of a loop index variable;

responsive to the address failing to be the affine function of the loop index variable, determine if there is a loop-carried dependency between statements used in the computed address; and

responsive to failure to identify any loop-carried dependencies, indicate the irregular memory reference as the candidate for optimization.

14. The apparatus of claim 13, wherein the instructions to determining if the irregular memory reference is valid for prefetching further cause the processor to:

back-slice the address of the irregular memory reference to determine if a computed address for the irregular memory reference contains a cache reference thereby forming a back-sliced address; and

responsive to the back-sliced address failing to contain the cache reference, indicate the irregular memory reference as valid for prefetching.

15. The apparatus of claim 13, wherein the instructions further cause the processor to:

distribute the at least one of the plurality of loops into an address collection loop and a computation loop; and

insert the runtime library call into the prefetch runtime library for the irregular memory reference between the address collection loop and the computation loop.

16. The apparatus of claim 13, wherein the instructions further cause the processor to:

receive a request to prefetch the data within the at least one of the plurality of loops;

determine if a temporary array associated with the at least one of the plurality of loops contains more than one data access for a plurality of irregular memory references;

responsive to the temporary array containing only one data access, determine if the data associated with the irregular memory reference exists in the software controlled cache; and

responsive to the data failing to exist within the software controlled cache, prefetch the data into the software controlled cache.

17. The apparatus of claim 16, wherein the instructions further cause the processor to:

responsive to the temporary array containing more than one data access, invoke a first function within the temporary array;

for each of a plurality of second functions associated with the first function, determine if the data associated with each second function exists in the software controlled cache; and

responsive to the data associated with each second function failing to exist within the software controlled cache, invoke the second function to prefetch the data associated with the second function into the software controlled cache.