Unrolling transformation of nested loops

• US 20040003386A1
• Filed: 11/14/2002
• Published: 01/01/2004
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tal, Arie, Blainey, Robert J.
• Granted Patent: US 7,140,009 B2
• Time in Patent Office: Days
• US Class Current: 717/160
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

The present invention is directed to 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 formed 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 are 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. Accordingly, the operations for the unrolled remaining portion of the actual iteration space when combined with the operations for the residue of the actual iteration space which was not evenly divided by the unroll factor is, in appropriate situations, semantically equivalent to the original nested loops. Aspects of the invention are applicable to rectangular and triangular loop nests, and combinations thereof. Moreover, the invention is applicable to loops having n-dimensions.

Claims

1. A method for unrolling loops in a loop nest, said loop nest iterating over 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.

2. The method of claim 1, further comprising:

calculating a virtual iteration space, said virtual iteration space comprising said actual iteration space and being evenly divided by said unrolling factor.

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

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

5. 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 nest, 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.

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

7. The method of claim 6 wherein said loop nest comprises a perfect triangular loop.

8. The method of claim 7 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.

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

10. The method of claim 6 wherein said loop nest comprises a rectangular loop.

11. The method of claim 10 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.

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

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

a rectangular and a triangular loop nest.

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

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.

15. The computer readable media of claim 14, further adapting said computer system to:

calculate a virtual iteration space, said virtual iteration space comprising said actual iteration space and being evenly divided by said unrolling factor.

16. The computer readable media of claim 15 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.

17. The computer readable media of claim 16 wherein said residue loop nest comprises a perfect loop nest.

18. The computer readable media of claim 14 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 portion of said loop nest, whereby the total number of said inner portions of said loop nest equal said unrolling factor.

19. The computer readable media of claim 14 wherein said loop nest comprises a two dimensional loop nest.

20. The computer readable media of claim 19 wherein said loop nest comprises a perfect triangular loop.

21. The computer readable media of claim 20 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.

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

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

23. The computer readable media of claim 19 wherein said loop nest comprises a rectangular loop.

24. The computer readable media of claim 23 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.

25. The computer readable media of claim 24 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.

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

a rectangular and a triangular loop nest.

27. A 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 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;

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.

28. The method of claim 27, further comprising:

means for calculating a virtual iteration space, said virtual iteration space comprising said actual iteration space and being evenly divided by said unrolling factor.

29. The method of claim 28 wherein said means for accounting for residues comprises:

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

30. The method of claim 29 wherein said residue loop nest comprises a perfect loop nest.

31. The method of claim 27 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.

32. The method of claim 27 wherein said loop nest comprises a two dimensional loop nest.

33. The method of claim 32 wherein said loop nest comprises a perfect triangular loop.

34. The method of claim 33 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.

35. 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 comprising:

machine readable instructions 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;

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.

36. The compiled file of claim 35 wherein said 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.

37. The compiled file of claim 36 wherein said residue loop nest comprises a perfect loop nest.

38. The compiled file of claim 35 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.

39. The compiled file of claim 38 wherein said loop nest comprises a two dimensional loop nest.

40. The compiled file of claim 39 wherein said loop nest comprises a perfect triangular loop.

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

44. The compiled file of claim 43 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.

45. The compiled file of claim 44 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.

46. The compiled file claim 35 wherein said loop nest comprises at least one of:

a rectangular and a triangular loop nest.

41. The compiled file of claim 41 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 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.