Normalized loop: Difference between revisions

Revision as of 18:07, 31 January 2018

Revision as of 21:15, 21 May 2020

Line 10:

A well behaved loop is normally of the form:

<sourcesyntaxhighlight lang=c>

for ( i = 0; i < MAX; i++ )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

Because the increment is unitary and constant, it's very easy to see that, if both ''a'' and ''b'' are bigger than MAX, this loop will never access memory outside the allocated range.

Line 23:

A simple example, where it doesn't start at the beginning and increments by more than one:

<sourcesyntaxhighlight lang=c>

// Example 1

for ( i = 7; i < MAX; i+=3 )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

A more complicated example, with an additional exit condition:

<sourcesyntaxhighlight lang=c>

// Example 2

for ( i = 7; i < MAX || i > MIN; i+=3 )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

Loops can also have non-predictable behavior during compilation time, where the exit condition depends on the contents of the data being modified:

<sourcesyntaxhighlight lang=c>

// Example 3

for ( i = 7; i < MAX && a[i]; i+=3 )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

Or even dynamic calculations by means of function calls:

<sourcesyntaxhighlight lang=c>

// Example 4

for ( i = start(); i < max(); i+=increment() )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

Reverse loops are also very simple, and can be easily normalized:

<sourcesyntaxhighlight lang=c>

// Example 5

for ( i = MAX; i > 0; i-- )

a[i] = b[i] + 5;

</syntaxhighlight>

</source>

===Converting to a normalized loop===

Line 65:

If the non-normalized doesn't have dynamic behaviour, it's normally very easy to transform it to a normalized one. For instance, the first example (Example 1) above can easily be converted to:

<sourcesyntaxhighlight lang=c>

// Example 1 -> normalized

for ( i = 0; i < (MAX-7)/3; i++ )

a[i*3+7] = b[i*3+7] + 5;

</syntaxhighlight>

</source>

While the third example can be partially normalized to allow some parallelization, but still lack the ability to know the loop span (how many iterations there will be), making it harder to vectorize by using multi-media hardware.

Line 77:

The reverse loop (Example 5) is also easy to normalize:

<sourcesyntaxhighlight lang=c>

// Example 5 -> normalized

for ( i = 0; i < MAX; i++ )

a[MAX-i] = b[MAX-i] + 5;

</syntaxhighlight>

</source>

Note that the access is still backwards. In this case, it makes no sense to leave it backwards (as there is no [[data dependence]]), but where dependences exist, caution must be taken to revert the access as well, as it could disrupt the order of assignments.