Prefetching irregular data references for software controlled caches

• US 8,762,968 B2
• Filed: 06/27/2012
• Issued: 06/24/2014
• 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 B
• Assistant Examiner(s): NGUYEN, DUY KHUONG THANH
• Application Number:
  US13/534,794
• Publication Number:
  US 20120265941A1
• Time in Patent Office: 727 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 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, determining whether the irregular memory reference is valid for prefetching, 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 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;

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

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

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

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

5. The method of claim 4, 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 whether 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.

6. A computer program product comprising a non-transitory computer readable storage 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 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, 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;

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

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

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

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

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

11. 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 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, 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;

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

12. The apparatus of claim 11, 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.

13. The apparatus of claim 11, 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 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.

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

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

for each of a plurality of second functions associated with the first function, determine whether 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.