Blocking of nested loops having feedback or feedforward indexes

Details Blocking of nested loops having feedback or feedforward indexes Blocking of nested loops having feedback or feedforward indexes

2011-01-04

2011-01-04

Bullock, Jr., Lewis A (Department: 2193)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S151000, C717S159000

Reexamination Certificate

active

07865886

ABSTRACT:
A method and apparatus for to blocking nested loops having feedback or feedforward indexing. An embodiment of a method includes receiving a computer code segment, the segment including a first inner loop and a second outer loop, the inner loop being within the outer loop and the inn loops having a one-dimensional iteration space that is independent of the outer loop. The first loop is indexed by a variable I over a contiguous one-dimensional iteration space and addresses one or more data arrays with a shift in the index. The method further includes dividing a two-dimensional iteration space of the first loop and the second loop into multiple contiguous windows, where the second loop uses only one window of the plurality of windows during each iteration and the plurality of windows cover the iteration space. The method includes modifying the computer code segment by adding a third outer loop outside the second loop of the segment, the third loop encompassing the first loop and the second loop.

REFERENCES:
Li et al, “New tiling techniques to improve cache temporal locality”, May 1999, vol. 34, pp. 215-228.
Li et al, “Optimal skewed tiling for cache locality enhancement”. 2003, 17th international Parallel and Distributed Processing Symposium.
Dulong et al—Technology Journal Q4 1999—An Overview of the Intel IA-64 Compiler—pp. 1-15.
www.publib.boulder.ibm.com/infocenter/pseries/topic/com.ibm.vacpp7a.doc/compiler/ref/r...—Compiler Reference—#pragma block—loop—2 pages.
http://en.wikipedia.org/wiki/Loop—nest—optimization—Loop Nest Optimization—Wikipedia, the free encyclopedia—5 pages.
http://docs.hp.com/cgi-bin/pf-new.cgi?IN=/en/B3909-90003/ch05s05.html&printable=1—Loop Blocking—6 pages.
Intel Reference Manual—IA-32 Intel Architecture Optimization—Chapter 3 pp. 3-1 through 3-38 and Chapter 7 pp. 7-1 through 7-34.

Affiliated with

Also associated with

Rating

Blocking of nested loops having feedback or feedforward indexes does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2710002