Unrolling transformation of nested loops

Details Unrolling transformation of nested loops Unrolling transformation of nested loops

2006-11-21

2006-11-21

Zhen, Wei (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S150000, C717S151000

Reexamination Certificate

active

07140009

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.

REFERENCES:
patent: 5797013 (1998-08-01), Mahadevan et al.
patent: 5905863 (1999-05-01), Knowles et al.
patent: 5950007 (1999-09-01), Nishiyama et al.
patent: 6035125 (2000-03-01), Nguyen et al.
patent: 6064820 (2000-05-01), Subrahmanyam
patent: 6192515 (2001-02-01), Doshi et al.
patent: 6341370 (2002-01-01), Tirumalai et al.
patent: 6341371 (2002-01-01), Tandri
patent: 6438747 (2002-08-01), Schreiber et al.
patent: 6507947 (2003-01-01), Schreiber et al.
patent: 6948160 (2005-09-01), Click et al.
IEEE 1992, “Compiler Blockability of Numerical Algorithms” by S. Carr et al, pp. 114-124.
ACM 2000, “Optimized Unrolling of Nested Loops”, by V. Sarkar, pp. 153-166.
ACM 1997, “Compiler Blockability of Dense Matrix Facorizations”, by S. Carr pp. 336-361.

Affiliated with

Also associated with

Rating

Unrolling transformation of nested loops does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Unrolling transformation of nested loops, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unrolling transformation of nested loops will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3680408