Methods and systems for nested stream prefetching for general purpose central processing units

1. A method of prefetching data called by a stream in an inner loop, the inner loop nested in an outer loop of executable code, the method comprising:

identifying, with a compiler analysis, stream linking information defining how the stream in the inner loop is linked to a stream in the outer loop;

transferring the stream linking information from the executable code to hardware units of a prefetcher; and

prefetching the data using the stream linking information and the hardware units of a prefetcher;

wherein the compiler analysis comprises:

identifying an inner stream candidate, being the stream in the inner loop, the inner loop nested in the outer loop;

determining whether the inner stream candidate corresponds to a qualified nested loop scenario;

identifying the outer stream candidate, being a stream in the outer loop nesting the inner loop;

using information from the candidate streams to create a stream dependency tree;

identifying the stream linking information defining how the inner stream is linked to the outer stream;

generating stream handling instructions for an intermediate representation code;

inserting the stream handling instructions in the intermediate representation code; and

where the qualified nested loop scenario is a scenario for which the number of times a stream handling instruction is executed can be reduced.

2. The method of claim 1 , wherein:

the inner loop stream is a subordinate stream to the outer loop stream;

the outer loop stream is a master stream to the inner loop stream,

the stream linking information includes:

a subordinate stream identification;

a master stream identification, providing an initial value for the subordinate stream's induction variable;

an initial value for the subordinate stream identification's, coming from the master stream's identification;

a master stream identification, providing an end value for the subordinate stream's induction variable;

an end value for the subordinate stream identification, coming from the master stream's identification; and

a subordinate stream being a stream in an inner loop that is changed at each iteration of the outer loop, and a master stream being a stream in an outer loop that can change one of:

the initial value of the subordinate stream's induction variable,

the end value of the subordinate stream's induction variable, and

a base address of the subordinate stream.

3. The method of claim 1 , wherein

the inner loop stream is a subordinate stream to the outer loop stream;

the outer loop stream is a master stream to the inner loop stream; and

the stream linking information includes

an identification for the subordinate stream, and

an identification for the master stream, the identification for the master stream providing a base address for the identification of the subordinate stream.

4. The method of claim 1 , where the properties of a qualified nested loop scenario include:

the outer loop containing only innermost loops;

the outer loop having not previously been selected for a corresponding stream handling instruction to be inserted according to a prefetcher's instruction set architecture;

the inner loop stream being potentially linked to the outer loop stream with information including at least one of:

an initial value for an induction variable;

a final value for an induction variable;

a base address.

5. The method of claim 1 , further comprising eliminating a stream in the outer loop that is not linked to a stream in an inner loop.

6. The method of claim 1 , further comprising eliminating a stream that is missing required stream linking information.

7. The method of claim 1 , further comprising compiling the intermediate representation code into code executable by the instruction set architecture of a selected prefetcher.

8. The method of claim 1 , further comprising eliminating a stream candidate not meeting certain criteria, criteria being:

for a stream candidate having an induction variable, containing a loop-invariant start value, a loop-invariant end value, and a loop-invariant increment value;

for a stream candidate that is a direct stream, containing a loop-invariant base address;

for a stream candidate that is an indirect stream, containing a loop-invariant base address; and

having an index, the calculation of which performs types of arithmetic operations that are supported by a prefetcher's implemented arithmetic units.

9. The method of claim 1 , where transferring stream linking information from the executable code to hardware units of a prefetcher comprises:

receiving with the prefetcher, executable code containing stream linking information, the executable code having been compiled for the instruction set architecture of the prefetcher;

executing the code with the prefetcher;

recording the stream linking information from the executable code in a stream configuration table (SCT); and

reading the stream linking information from the SCT, with a stream prefetch manager.

10. The method of claim 9 , further comprising, for each stream having stream linking information in the SCT, while an outer loop is being iterated:

producing prefetches to bring data to a cache;

fetching data from a cache and storing it in buffers; and

producing a prefetch for each iteration of the loop.

11. The method of claim 9 , further comprising, for each stream having stream linking information in the SCT, while an inner loop is being iterated:

reconfiguring an inner loop stream prefetcher using the stream linking information; and

prefetching for arrays in the inner loop until all iterations are completed.

12. The method of claim 9 , wherein transferring the stream linking information from the executable code to hardware units of a prefetcher is performed through a mechanism available with the instruction set architecture (ISA) of the processor incorporating the prefetcher.