Unrolling transformation of nested loops
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
43 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
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. - View Dependent Claims (26, 27, 28, 29, 30, 31)
-
-
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. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43)
-
Specification