Loop interchange

Loop interchange

In compiler theory, loop interchange is the process of exchanging the order of two iteration variables.

For example, in the code fragment:

for i from 0 to 10 for j from 0 to 20 a [i,j] = i + j

loop interchange would result in:

for j from 0 to 20 for i from 0 to 10 a [i,j] = i + j

On occasion, such a transformation may lead to opportunities to further optimize, such as vectorization of the array assignments.

The utility of loop interchange

One major purpose of loop interchange is to improve the cache performance for accessing array elements. Cache misses occur if the contiguously accessed array elements within the loop come from a different cache line. Loop interchange can help prevent this. The effectiveness of loop interchange depends on and must be considered in light of the cache model used by the underlying hardware and the array model used by the compiler.

In the C programming language, the array elements from the same row are stored consecutively (Ex: a [1,1] ,a [1,2] , a [1,3] ... ), namely row-major. On the other hand, FORTRAN programs store array elements from the same column together(Ex: a [1,1] ,a [2,1] ,1 [3,1] ...) , called column-major. Thus the order of two iteration variables in the first example is suitable for C program while the second example is better for FORTRAN. Optimizing compilers can detect the improper ordering by programmers and interchange the order to achieve better cache performance.

Caveat

Like any other compiler optimization, loop interchange may lead to worse performance because cache performance is only part of the story. Take the following example:

do i = 1, 10000 do j = 1, 1000 a(i) = a(i) + b(i,j) * c(i) end do end do

Loop interchange on this example can improve the cache performance of accessing b(i,j), but it will ruin the reuse of a(i) and c(i) in the inner loop, as it introduces two extra loads (for a(i) and for c(i)) and one extra store (for a(i)) during each iteration. As a result, the overall performance may be degraded after loop interchange.

Safety

It is not always safe to exchange the iteration variables due to dependencies between statements for the order in which they must execute. In order to determine whether a compiler can safely interchange loops, dependence analysis is required.

Further reading

See also

* Loop splitting
* Loop skewing
* Loop fusion
* Loop unwinding


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Loop tiling — Loop tiling, also known as loop blocking, strip mine and interchange, unroll and jam, or supernode partitioning, is a loop optimization used by compilers to make the execution of certain types of loops more efficient.Loop tiling partitions a loop …   Wikipedia

  • Loop optimization — In compiler theory, loop optimization plays an important role in improving cache performance, making effective use of parallel processing capabilities, and reducing overheads associated with executing loops. Most execution time of a scientific… …   Wikipedia

  • Loop dependence analysis — In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, almost always with respect to array access and modification. For a normalized loop: for i1 from l1 to u1 do for i2… …   Wikipedia

  • Interchange (road) — A high capacity interchange: the Judge Harry Pregerson Interchange in Los Angeles, California, United States …   Wikipedia

  • Loop — A loop is generally something that closes back on itself such as a circle. The closing can appear in time or in space.cience and technology*Loop (algebra), a quasigroup with an identity element *Loop (graph theory), an edge that begins and ends… …   Wikipedia

  • Loop (Texarkana) — Infobox TX State Highway type=Loop route=151 name=Texarkana Loop shields= length mi=16 length km=26 formed= dir1=CCW dir2=CW from= east of Texarkana junction= to= west of Texarkana previous type=Loop previous route=150 next type=Loop next… …   Wikipedia

  • Georgia State Route 120 Loop — Infobox road state=GA type= route=120 Loop length mi=7.6 length ref= [http://www.dot.state.ga.us/DOT/plan prog/transportation data/400reports/2002/dpp444 2002.pdf] length round=1 established= beltway city=Marietta junction= previous route=119… …   Wikipedia

  • Pennsylvania Turnpike/Interstate 95 Interchange Project — Infobox road marker state=PA highway name=Pennsylvania Turnpike/Interstate 95 Interchange Project maint=PennDOT system= commons=The Pennsylvania Turnpike/Interstate 95 Interchange Project is a project to build an interchange where Interstate 95… …   Wikipedia

  • Normalized loop — In computer science, a normalized loop (sometimes called well behaved loop), is a loop which the loop variable starts at 0 (or any constant) and get incremented by one at every iteration until the exit condition is met. Normalized loops are very… …   Wikipedia

  • Texas State Highway Loop 288 — Loop 288 is a state highway within the city limits of Denton, Texas. On the north side of town, the loop runs next to the C. H. Collins Athletic Complex. Despite its name, Loop 288 does not make a complete circuit, running instead around the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”