Dynamically Controlling a Prefetching Range of a Software Controlled Cache

• US 20090254733A1
• Filed: 04/04/2008
• Published: 10/08/2009
• Est. Priority Date: 04/04/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zhang, Tao, Sura, Zehra N., Gonzalez tallada, Marc, Chen, Tong
• Granted Patent: US 8,146,064 B2
• Time in Patent Office: Days
• US Class Current: 711/213
• CPC Class Codes: G06F 12/0837 with software control, e.g. non-cacheable data
• CPC Class Codes: G06F 12/0862 with prefetch

Abstract

Dynamically controlling a prefetching range of a software controlled cache is provided. A compiler analyzes source code to identify at least one of a plurality of loops that contain irregular memory references. For each irregular memory reference in the source code, the compiler determines whether the irregular memory reference is a candidate for optimization. Responsive to identifying an irregular memory reference that may be optimized, the complier determines whether the irregular memory reference is valid for prefetching. If 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 to dynamically prefetch the irregular memory references. Data associated with the irregular memory references are dynamically prefetched into the software controlled cache when the runtime library call is invoked.

Claims

1. A method, in a data processing system, for dynamically controlling a prefetching range of 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 irregular memory references;

for each 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; and

inserting a runtime library call into a prefetch runtime library to dynamically prefetch the irregular memory references associated with the at least one of the plurality of loops, wherein data associated with the irregular memory references are dynamically prefetched into the software controlled cache when the runtime library call is invoked and wherein the irregular memory references are dynamically prefetched for a lower boundary to an upper boundary.

2. The method of claim 1, 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.

3. 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.

4. 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 addresses are written into a temporary array.

5. 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 to dynamically prefetch the irregular memory references associated with the at least one of the plurality of loops between the address collection loop and the computation loop.

6. 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.

7. The method of claim 6, further comprising:

responsive to the temporary array containing more than one data access, invoking a first function within the temporary array to prefetch the irregular data references from the lower boundary to the upper boundary;

for each of a plurality of second functions from the lower boundary to the upper boundary, determining if the data associated with each second function exists in the software controlled cache;

responsive to the data associated with each second function failing to exist within the software controlled cache, determining if prefetching the data will cause an associativity conflict; and

responsive to determining that the prefetching fails to cause the associativity conflict, invoking the second function to prefetch the data from the lower boundary to the upper boundary into the software controlled cache.

8. The method of claim 7, further comprising:

responsive to determining that the prefetching causes the associativity conflict, stopping execution of the first function;

resetting the lower boundary to an iteration where the prefetching was stopped thereby forming a new lower boundary; and

invoking the second function to prefetch the data from the new lower boundary to the upper boundary into the software controlled cache, thereby eliminating any cache lookup overhead.

9. A computer program product comprising a computer recordable medium having 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 irregular memory references;

for each 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; and

insert a runtime library call into a prefetch runtime library to dynamically prefetch the irregular memory references associated with the at least one of the plurality of loops, wherein data associated with the irregular memory references are dynamically prefetched into a software controlled cache when the runtime library call is invoked and wherein the irregular memory references are dynamically prefetched for a lower boundary to an upper boundary.

10. The computer program product of claim 9, 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.

11. The computer program product of claim 9, 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 to dynamically prefetch the irregular memory references associated with the at least one of the plurality of loops between the address collection loop and the computation loop.

12. The computer program product of claim 9, 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.

13. The computer program product of claim 12, 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 to prefetch the irregular data references from the lower boundary to the upper boundary;

for each of a plurality of second functions from the lower boundary to the upper boundary, determine if the data associated with each second function exists in the software controlled cache;

responsive to the data associated with each second function failing to exist within the software controlled cache, determine if prefetching the data will cause an associativity conflict; and

responsive to determining that the prefetching fails to cause the associativity conflict, invoke the second function to prefetch the data from the lower boundary to the upper boundary into the software controlled cache.

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

responsive to determining that the prefetching causes the associativity conflict, stop execution of the first function;

reset the lower boundary to an iteration where the prefetching was stopped thereby forming a new lower boundary; and

invoke the second function to prefetch the data from the new lower boundary to the upper boundary into the software controlled cache, thereby eliminating any cache lookup overhead.

15. 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 irregular memory references;

for each 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; and

insert a runtime library call into a prefetch runtime library to dynamically prefetch the irregular memory references associated with the at least one of the plurality of loops, wherein data associated with the irregular memory references are dynamically prefetched into a software controlled cache when the runtime library call is invoked and wherein the irregular memory references are dynamically prefetched for a lower boundary to an upper boundary.

16. The apparatus of claim 15, wherein the instructions to determine 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.

17. The apparatus of claim 15, 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 to dynamically prefetch the irregular memory references associated with the at least one of the plurality of loops between the address collection loop and the computation loop.

18. The apparatus of claim 15, 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.

19. The apparatus of claim 18, 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 to prefetch the irregular data references from the lower boundary to the upper boundary;

for each of a plurality of second functions from the lower boundary to the upper boundary, determine if the data associated with each second function exists in the software controlled cache;

responsive to the data associated with each second function failing to exist within the software controlled cache, determine if prefetching the data will cause an associativity conflict; and

responsive to determining that the prefetching fails to cause the associativity conflict, invoke the second function to prefetch the data from the lower boundary to the upper boundary into the software controlled cache.

20. The apparatus of claim 19, wherein the instructions further cause the processor to:

responsive to determining that the prefetching causes the associativity conflict, stop execution of the first function;

reset the lower boundary to an iteration where the prefetching was stopped thereby forming a new lower boundary; and

invoke the second function to prefetch the data from the new lower boundary to the upper boundary into the software controlled cache, thereby eliminating any cache lookup overhead.