Dynamically controlling a prefetching range of a software controlled cache

• US 8,146,064 B2
• Filed: 04/04/2008
• Issued: 03/27/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): Das, Chameli
• Application Number:
  US12/062,559
• Publication Number:
  US 20090254733A1
• Time in Patent Office: 1,453 Days
• Field of Search: None
• US Class Current: 717/141
• 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 whether 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 whether 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 of the at least one of the plurality of loops.

2. The method of claim 1, wherein determining whether the irregular memory reference within the at least one of the plurality of loops is the candidate for optimization comprises:

determining whether 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 whether 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 whether the irregular memory reference is valid for prefetching comprises:

back-slicing the address of the irregular memory reference to determine whether a computed address for the irregular memory reference contains a cache reference thereby firming 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 whether 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 whether 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 whether 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 whether 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 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 irregular memory references;

for each irregular memory reference, determine whether 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 whether 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 of the at least one of the plurality of loops.

10. The computer program product of claim 9, wherein the computer readable program to determine whether 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 whether 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 whether 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 whether 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 whether 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 whether 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 whether 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 whether 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 of the at least one of the plurality of loops.

16. The apparatus of claim 15, wherein the instructions to determine whether the irregular memory reference is valid for prefetching further cause the processor to:

back-slice the address of the irregular memory reference to determine whether 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 farther 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 whether a temporary array associated with the at least one of the plurality of loops contains more than one data access fur a plurality of irregular memory references;

responsive to the temporary array containing only one data access, determine whether 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 whether 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 whether 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.