J.C. Huang, T. Leng - Generalized Loop-Unrolling - a Method for Program Speed-Up

Generalized Loop-Unrolling: a Method for Program Speed-UpJ. C. Huang and T. LengDepartment of Computer ScienceThe University of HoustonHouston, TX 77204-3475jhuang|leng@cs.uh.eduAbstract - It is well-known that, to optimize a program for speed-up, efforts should be focusedon the regions where the payoff will be greatest. Loop constructs in a program represent suchregions. In the literature, it has been shown that a certain degree of speed-up can be achieved byloop unrolling. The technique published so far, however, appears to be applicable to FOR-loopsonly. This paper presents a generalized loop-unrolling method that can be applied to any typeof loop construct.

Possible complications in its applications, together with some experimentalresults, are discussed in detail.IntroductionThere has been considerable effort to develop source-to-source transformation methods thatrestructure loop constructs to expose possibilities for parallelism. Most published looprestructuring methods are designed for countable loops, where the iteration count can bedetermined without executing the loop.

One such method, called loop unrolling [2], is designedto unroll FOR loops for parallelizing and optimizing compilers. To illustrate, consider thefollowing loop:for (i = 1; i <= 60; i++) a[i] = a[i] * b + c;This FOR loop can be transformed into the following equivalent loop consisting of multiplecopies of the original loop body:for (i ={a[i] =a[i+1]a[i+2]}1; i <= 60; i+=3)a[i] * b + c;= a[i+1] * b + c;= a[i+2] * b + c;The loop is said to have been unrolled twice, and the unrolled loop should run faster because ofreduction in loop overhead.Loop unrolling was initially developed for reducing loop overhead and for exposing instructionlevel parallelism for machines with multiple functional units.

More recently it has also beenapplied in conjunction with instruction scheduling for pipelined and RISC architectures[2]. By1increasing the size of the loop body, the instruction scheduler can often produce a shorterschedule for the unrolled loop.Unlike FOR loops operating on arrays, which can be unrolled simply by modifying the counterand termination condition of the loop as illustrated above, WHILE loops are generally moredifficult to unroll and seldom mentioned in the subject area. It is so mainly because of difficultyin determining the termination condition of an unrolled WHILE loop.In this paper, we present a new method for unrolling a WHILE loop and discuss problems thatmay be encountered in its application.

The method is "generalized" in the sense that it can beapplied to any type of loop construct, including implicit one, because any loop construct can berewritten as a WHILE loop.Main ResultsWe assume that loops are written in the form: while B do S, the semantic of which is defined asusual. This assumption should not cause any loss in generality because any loop of other formcan be rewritten in this form.

We shall refer to B as the loop predicate and S as the loop body.By using the analysis method we have developed [1], it is easy to show that the followingequivalence relations hold.while B do S; ⇔ while B ∧ wp(S, B) do begin S; S end; while B do S;(A)where ⇔ stands for the equivalence relation, and wp(S, B) the weakest precondition of S withrespect to postcondition B.We shall say that the equivalent program on the right-hand side is obtained by unrolling the looponce. Observe that if any data will cause the loop on the left-hand side to iterate n times then itwill cause the first loop on the right to iterate n/2 times, and the second 0 or 1 time.

Now if wecan simplify B ∧ wp(S, B) or S; S, as explained below, we can unroll the loop to achieve a certaindegree of computational speed-up.A WHILE loop can be unrolled further. It can be shown thatwhile B do S;⇔ while B ∧ wp(S, B) ∧ wp(S, wp(S, B)) do begin S; S; S end; while B do S;(B)Expression on the right-hand side shows how to unroll a loop twice. Needless to say, a loop canbe unrolled thrice, four times, and so on and so forth.Thus, given a loop construct of the form: while B do S; we may be able to speed up itsexecution by following the steps listed below to unroll it once:21. Form wp(S, B), the weakest precondition of S with respect to B.2. Unroll the loop once by replacing it with a sequence of two loops:while B ∧ wp(S, B) do begin S; S end;while B do S;3.

Simplify the predicate B ∧ wp(S, B) and the loop body S;S to speed up.The second loop is the original loop. Since it will be iterated no more than once, in theory it canbe replaced by the construct: if B then S. From the software engineering point of view,however, it is more desirable to leave it unmodified because the original loop is easier tounderstand. Besides, if the loop unrolling becomes no longer desirable for some reason, all weneed to do is to delete the first loop.

To this end, we suggest that the first loop be always clearlydemarcated with appropriate comments. If it needs to be temporarily removed, say, fordebugging purposes, it can be readily accomplished by using the host-language facility to turn thefirst loop into a comment.The analysis method described in [1] is particularly useful in Step 3.To illustrate, consider the following example. (NOTE: Throughout this paper, the source code ofall example programs are written in C and listed in Courier.)Example 1. A loop for computing the quotient, q, of dividing b into a:q=0;while (a>=b){a=a-b;q++;}⇔q=0;while (a>=b && a>=2*b){a=a-b;q++;a=a-b;q++;}while (a>=b){a=a-b;q++;}//unrolled loop//end of the unrolled loop3⇔⇔q=0;while (a>=2*b){a=a-2*b;q=+2;}while (a>=b){a=a-b;q++;}q=0;x=2*b;while (a>=x){a=a-x;q=+2;}while (a>=b){a=a-b;q++;}//unrolled loop//end of the unrolled loop//unrolled loop//end of the unrolled loopOur experimental results show that this unrolled loop is able to achieve a speed-up factor veryclose to 2, and if we unroll the loop k times, we can achieve a speed-up factor of k.

Speed factoris defined to be the ration between the CPU time required to execute the modified program andthat required to execute the original program.DiscussionsAlthough the programs on both sides of ⇔ are logically equivalent in theory, it may not becompletely so in practice.

Note that in the equivalence relation (A) given above, the looppredicate of the first loop on the right-hand side is B ∧ wp(S, B). Since the logical operation of"∧" (and) is commutative, it should make no difference in theory if the loop predicate is writtenas B ∧ wp(S, B) or wp(S, B) ∧ B, or if B or wp(S, B) is evaluated first.

In practice, however, Bshould be evaluated first, and if it is false, wp(S, B) should not be evaluated at all because itdetermines if the second part of the unrolled loop should be executed.This would present no problem if (1) components of the loop predicate is always written in thecorrect order, and (2) the program is compiled and executed in an environment where thecomponents of the loop predicate are evaluated in the order given, and the evaluation isterminated as soon as one is found to be false. Otherwise, the unrolled loop may have run-timeerrors that would not occur in the original loop.

For instance, consider the following program.4Example 2. A loop for finding GCD (Greatest Common Divisor) of two positive integers a and bby using Euclid’s algorithm, the final result of the loop, which is the GCD of a and b, is stored ina.while (b>0){r = a % b;a = b;b = r;}By unrolling the loop once and simplifying the result we obtain⇔while (b>0) && (r = a % b > 0) //unrolled loop{a=b;b=b % r;}//end of the unrolled loopwhile (b>0){r = a % b;a = b;b = r;}Note that the value of a%b can be properly computer only if b>0, and there will be an arithmaticfault in computing a%b if b=0. In order to avoid such fault, we can modify the loop as follows.⇔while (b>0){a = a % b;if (a>0) b = b % a;else{r=a;a=b;b=r;break;}}The speed-up achieved in this case is rather limited because the gain mostly comes fromreduction of instructions in the loop bodies. In an experiment using 10,000 pairs of randomintegers, the average speed-up factor is approximately 1.05.A possible alternative is to make use of exception handling.

Some programming languages, suchas C++, Smalltalk, and Ada, provide mechanism for the programmer to handle exceptions.Although the penalty of exception handling is high, it is deemed a viable solution becauseexceptions of this sort occur infrequently.Problems of similar nature may arise if pointers are involved.5Example 3. A loop for traversing a linked list and counting the nodes traversed:count=0;while (lp != NULL){lp = lp->next;count++;}After unrolling the loop twice, it becomes:⇔count=0;lp1=lp->next;lp2=lp1->next;while (lp2 != NULL){count=+3;lp = lp2->next;lp1 = lp ->next;lp2 = lp1->next;}while (lp != NULL){lp = lp->next;count++;}//unrolled loop//end of the unrolled loopSince we do not know apriori how many more items will be in the linked list, computation of lp1and lp2 may cause rum-time errors, which would not occur in the original loop.