Unrolling transformation of nested loops

• US 7,140,009 B2
• Filed: 11/14/2002
• Issued: 11/21/2006
• Est. Priority Date: 06/28/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tal, Arie, Blainey, Robert J.
• Primary Examiner(s): Zhen, Wei
• Assistant Examiner(s): DENG, ANNA CHEN
• Application Number:
  US10/294,938
• Publication Number:
  US 20040003386A1
• Time in Patent Office: 1,468 Days
• Field of Search: 717/160, 717/161, 717/154, 717/156, 717/158, 717/141, 717/146, 717/148, 717/159, 703/14, 709/224, 712/241, 716/18
• US Class Current: 717/160
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A transformation technique for nested loops. A virtual iteration space may be determined based on an unroll factor (UF). The virtual iteration space, which includes the actual iteration space, is fanned such that, the virtual iteration space may be evenly divided by a selected UF. Once the virtual iteration space has been calculated or determined, the virtual iteration space is “cut” into regular portions by one or more unroll factors. Portions of the actual iteration space which do not fill the cut portions of the virtual iteration space or which fall outside these cuts which have been evenly divided by the unroll factor form a residue which is calculated. The portions of the actual iteration space which remain arc also evenly divided by the unroll factor(s). An outer loop for this remaining portion of the actual iteration space is then unrolled. This unrolled portion forms a perfect nested loop.

Claims

1. A computer-implemented method for unrolling loops in a loop nest, said loop nest iterating aver an actual iteration space of n-dimension, said method comprising:

accounting for residues, said residues comprising portions of said actual iteration space falling outside of, or incompletely overlapping with, cuts of a virtual iteration space, said virtual iteration space comprising said actual iteration space and said virtual iteration space evenly divided by an unrolling factor, said cuts and said virtual iteration space having n-dimensions;

unrolling at least one outer loop of said loop nest, said unrolled outer loop bounded by cuts of said virtual iteration space falling completely within said actual iteration space;

calculating a boundary of said virtual iteration space using said unrolling factor, wherein said unrolling factor is used to determine a next integer value greater than an upper bound of the outer loop which is evenly divisible by said unrolling factor.

2. The method of claim 1 wherein said accounting for residues comprises:

generating a residue loop nest, said residue loop nest iterating over said portion of said actual iteration space falling outside of, or incompletely overlapping with, cuts of said virtual iteration space.

3. The method of claim 2 wherein said residue loop nest comprises a perfect loop nest.

4. The method of claim 1 wherein said unrolling at least one outer loop of said loop nest comprises:

iterating over said at least one outer loop of said loop neat, the induction variable of said at least one outer loop being incremented by said unrolling factor;

replicating an inner portion of said loop nest, whereby the total number of said inner portions of said loop nest equal said unrolling factor.

5. The method of claim 1 wherein said loop nest comprises a two dimensional loop nest.

6. The method of claim 5 wherein said loop nest comprises a perfect triangular loop where at least one of an upper and lower bound of an inner loop is a linear function of an outer loop induction variable.

7. The method of claim 6 wherein said virtual iteration space is bounded by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

8. The method of claim 6 wherein said accounting for residues comprises:

generating a residue loop nest iterating over said portion of said actual iteration space falling outside of, or incompletely overlapping with, outs of said virtual iteration space, said residue loop nest comprising;

an outer residue loop; and

an inner residue loop;

an induction variable “

i”

for said outer residue loop bounded by the bounds of the induction variable of said outer loop; and

an induction variable “

j”

for said inner residue loop having a lower bound governed by the equation;

j_{lower bound}=max (0,i−

mod(+UF−

mod(n, UF),UF));

where “

n”

is the upper bound of said outer loop;

and said induction variable “

j”

for said inner residue loop having an upper bound governed by said induction variable for said outer residue loop.

9. The method of claim 5 wherein said loop nest comprises a rectangular loop.

10. The method of claim 9 wherein said virtual iteration space is bounded by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

11. The method of claim 10 wherein said accounting for residues comprises:

generating a residue loop nest iterating over said portion of sold actual Iteration space felling outside of, or incompletely overlapping with, cuts of said virtual iteration space, said residue loop nest comprising;

an outer residue loop; and

an inner residue loop;

an induction variable “

i”

for said outer residue loop comprising a lower bound of the induction variable of said outer loop and an upper bound governed by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

12. The method of claim 1 wherein said loop nest comprises at least one of:

a rectangular and a triangular loop nest.

13. A computer readable media storing data and instructions, said data and instructions, when executed, adapting a computer system to unroll loops in a loop nest, said nested loop nest iterating over an actual iteration space of n-dimension, said computer system adapted to:

account for residues, said residues comprising portions of said actual iteration space falling outside of, or incompletely overlapping with, cuts of a virtual iteration space, said virtual iteration apace comprising said actual iteration space and said virtual iteration space evenly divided by an unrolling factor, said cuts and said virtual iteration space having n-dimensions;

unroll at least one outer loop of said nested loop nest, said unrolled outer loop bounded by cutsslices of said virtual iteration space falling completely within said actual iteration space;

calculate a boundary of said virtual iteration space using said unrolling factor, wherein said unrolling factor is used to determine a next integer value greater than an upper bound of the outer loop which is evenly divisible by said unrolling factor.

14. The computer readable media of claim 13 wherein said adaptation to account for residues comprises adapting said computer system to:

generate a residue loop nest, said residue loop nest iterating over said portion of said actual iteration space falling outside of, or incompletely overlapping with, cuts of said virtual iteration space.

15. The computer readable media of claim 14 wherein said residue loop nest comprises a perfect loop nest.

16. The computer readable media of claim 13 wherein said adaptation to unroll at least one outer loop of said loop nest comprises adapting said computer system to:

iterate over said at least one outer loop of said loop nest, the induction variable of said at least one outer loop being incremented by said unrolling factor,

replicate an inner potion of said loop nest, whereby the total number of said inner portions of said loop nest equal said unrolling factor.

17. The computer readable media of claim 13 wherein said loop nest comprises a two dimensional loop nest.

18. The computer readable media of claim 17 wherein said loop nest comprises a perfect triangular loop where at least one of an upper and lower bound of an inner loop is a linear function of an outer loop induction variable.

19. The computer readable media of claim 18 wherein said virtual iteration space is bounded by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

20. The computer readable media of claim 18 wherein said adaptation to account for residues comprises adapting said computer system to:

create a residue, loop neat iterating over said portion of said actual iteration space falling outside of, or incompletely overlapping with, cuts of said virtual iteration apace, said residue loop nest comprising;

an outer residue loop; and

an inner residue loop;

an induction variable “

i”

for said outer residue loop bounded by the bounds of the induction variable of said outer loop; and

an induction variable “

j”

for said inner residue loop having a lower bound governed by the equation;

j_{lower bound}=max (0,i −

mod(i+UF−

mod(n, UF),UF));

where “

n”

is the upper bound of said outer loop;

and said induction variable “

j”

for said inner residue loop having an upper bound governed by said induction variable for said outer residue loop.

21. The computer readable media of claim 17 wherein said loop nest comprises a rectangular loop.

22. The computer readable media of claim 21 wherein said virtual iteration space is bounded by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

23. The computer readable media of claim 22 wherein said adaptation to account for residues comprises adapting said computer system to:

generate a residue loop nest iterating over said portion of said actual iteration space falling outside of, or incompletely overlapping with, cuts of said virtual iteration space, said residue loop nest comprising;

an outer residue loop; and

an inner residue loop;

an induction variable “

i”

for said outer residue loop comprising a lower bound of the induction variable of said outer loop and an upper bound governed by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

24. The computer readable media of claim 13 wherein said loop nest comprises at least one of:

a rectangular and a triangular loop nest.

25. A computer-implemented method for unrolling loops in a loop nest, said nested loop nest iterating over an actual iteration space of n-dimension, said method comprising:

means accounting for residues, said residues comprising portions of said actual iteration space failing outside of, or incompletely overlapping with, cuts of a virtual iteration space, said virtual iteration space comprising said actual iteration space and said virtual iteration space evenly divided by an unrolling factor, said cuts and said virtual iteration space having n-dimensions;

means unrolling at least one outer loop of said nested loop nest, said unrolled outer loop bounded by cutsslices of said virtual iteration space falling completely within said actual iteration space;

means for calculating a boundary of said virtual iteration space using said unrolling factor, wherein said unrolling factor is used to determine a next integer value greater than an upper bound of the outer loop which is evenly divisible by said unrolling factor.

26. The method of claim 25 wherein said means for accounting for residues comprises:

moans for generating a residue loop nest, said residue loop nest iterating over said portion of said actual iteration space falling outside of or incompletely overlapping with, cuts of said virtual iteration space.

27. The method of claim 26 wherein said residue loop nest comprises a perfect loop nest.

28. The method of claim 25 wherein said means for unrolling at least one outer loop of said loop nest comprises:

means for iterating over said at least one outer loop of said loop nest, the induction variable of said at least one outer loop being incremented by said unrolling factor;

means for replicating an inner portion of said loop nest whereby the total number of said inner portions of said loop nest equal said unrolling factor.

29. The method of claim 25 wherein said loop nest comprises a two dimensional loop nest.

30. The method of claim 29 wherein said loop nest comprises a perfect triangular loop where at least one of an upper and lower bound of an inner loop is a linear function of an outer loop induction variable.

31. The method of claim 30 wherein said virtual iteration space is bounded by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

32. A compiled file corresponding to a source code file, said source code file comprising a nested loop nest iterating over an actual iteration space of n-dimension, said compiled file comprising machine readable instructions corresponding to said nested loop, said machine readable instructions tangibly embodied in a tangle computer readable medium and comprising:

machine readable instructions accounting for residues, said residues comprising portions of said actual iteration space falling outside of, or incompletely overlapping with, curs of a virtual iteration space, said virtual iteration space comprising said actual iteration space and said virtual iteration space evenly divided by an unrolling factor, said cuts and said virtual iteration space having n-dimensions;

machine readable instructions unrolling at least one outer loop of said loop nest said unrolled outer loop bounded by cuts of said virtual iteration space falling completely within said actual iteration space;

machine readable instructions for calculating a boundary of said virtual iteration space using said unrolling factor, wherein said unrolling factor is used to determine a next integer value greater than an upper bound of the outer loop which is evenly divisible by said unrolling factor.

33. The compiled file of claim 32 wherein sold machine readable instructions accounting for residues comprises:

machine readable instructions for a residue loop nest, said residue loop nest iterating over said portion of said actual iteration space falling outside of or incompletely overlapping with, cuts of said virtual iteration space.

34. The compiled file of claim 33 wherein said residue loop nest comprises a perfect loop nest.

35. The compiled file of claim 32 wherein said machine readable instructions unrolling at least one outer loop of said loop nest comprises:

machine readable instructions iterating over said at least one outer loop of said loop nest, the induction variable of said at least one outer loop being incremented by said unrolling factor;

machine readable instructions iterating over replicated inner portions of said loop nest, whereby the total number of said inner portions of said loop nest equal said unrolling factor.

36. The compiled file of claim 35 wherein said loop nest comprises a two dimensional loop nest.

37. The compiled file of claim 36 wherein said loop nest comprises a perfect triangular loop where at least one of an upper and lower bound of an inner loop is a linear function of an outer loop induction variable.

38. The compiled file of claim 37 wherein said virtual iteration space is bounded by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

39. The compiled file of claim 37 wherein said machine readable instructions accounting for residues comprises:

machine readable instructions for a residue loop nest iterating over said portion of said actual iteration space falling outside of, or incompletely overlapping with, cuts of said virtual iteration space, said residue loop nest comprising;

an outer residue loop; and

an inner residue loop;

an induction variable “

i”

for said outer residue loop bounded by the bounds of the induction variable of said outer loop; and

an induction variable “

j”

for said inner residue loop having a lower bound governed by the equation;

j_{lower bound}=max (0,i−

mod(i+UF−

mod(n, UF),UF));

where “

n”

is the upper bound of said outer loop;

and said induction variable “

j”

for said inner residue loop having an upper bound governed by said induction variable for said outer residue loop.

40. The compiled file of claim 37 wherein said loop nest comprises a rectangular loop.

41. The compiled file of claim 40 wherein said virtual iteration space is bounded by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

42. The compiled file of claim 41 wherein said machine readable instructions accounting for residues comprises:

machine readable instructions for a residue loop nest iterating over said portion of said actual iteration space falling outside of, or incompletely overlapping with, cuts of said virtual iteration space, said residue loop nest comprising;

an outer residue loop; and

an inner residue loop;

an induction variable “

i”

for said outer residue loop comprising a lower bound of the induction variable of said outer loop and an upper bound governed by the modulus of an upper bound of the induction variable of said outer loop and said unrolling factor.

43. The compiled file claim 32 wherein said loop nest comprises at least one of:

a rectangular and a triangular loop nest.