2013. An Improving Method for Loop Unrolling

(IJCSIS) International Journal of Computer Science and Information Security,Vol. 11, No. 5, May 2013An Improving Method for Loop UnrollingMeisam Booshehri, Abbas Malekpour, Peter LukschChair of Distributed High Performance Computing,Institute of Computer Science, University of Rostock,Rostock, Germanym_booshehri@sco.iaun.ac.ir, abbas.malekpour@uni-rostock.de, peter.luksch@uni-rostock.deAbstract—In this paper we review main ideas mentioned inseveral other papers which talk about optimization techniquesused by compilers. Here we focus on loop unrolling technique andits effect on power consumption, energy usage and also its impacton program speed up by achieving ILP (Instruction-levelparallelism).

Concentrating on superscalar processors, we discussthe idea of generalized loop unrolling presented by J.C. Hang andT. Leng and then we present a new method to traverse a linkedlist to get a better result of loop unrolling in that case. After thatwe mention the results of some experiments carried out on aPentium 4 processor (as an instance of super scalar architecture).Furthermore, the results of some other experiments onsupercomputer (the Alliat FX/2800 System) containingsuperscalar node processors would be mentioned. Theseexperiments show that loop unrolling has a slight measurableeffect on energy usage as well as power consumption.

But it couldbe an effective way for program speed up.Keywords- superscalar processors;Parallelism; Loop Unrolling; Linked ListInstructionII. SUPERSCALAR PROCESSORSThe aim of designing superscalar processors is to reduce theaverage of execution time per instruction through executing theinstructions in parallel. To do this instruction latency should bereduced. One of cases that in designing superscalar processorswe should consider it is data dependency which its side effectsmust be removed or at least should be minimized.

This meanssuperscalar processors must organize the results to have thecomputation continued correctly [2, 4].Writing a program can be divided into several stepsincluding writing the program code with a high-level language,translating the program to assembly code and binary code andetc.

it is important to attempt to divide the program translatedto assembly code, into Basic Blocks [4]. A basic block has themaximum number of instructions with a specified input andoutput point. Therefore, each basic block has the maximumnumber of successive instructions with no branch (with theexception of last instruction) and no jump (with the exceptionof first instruction). The basic block would always be traversed.In this manner the processor can execute a basic block inparallel.

So the compilers and superscalar architectureconcentrate on size of basic blocks. Through integrating somebasic blocks for instance by executing Branch statementsentirely, the amount of parallelism would increase. If noexception occurs within the execution time, the processor mustcorrect all results and pipeline contents. Therefore there is astrong relation between superscalar architecture and compilerconstruction (especially code generator and optimizer).Certainly there are some data dependencies inside a basicblock. These dependencies exist among data of variousinstructions.

Despite RISC processors in which there are onlyread after write hazards, the superscalar processors mayencounter read after write hazards as well as write after writehazards Because of executing instructions in parallel.LevelI.INTRODUCTIONNowadays processors have the power to execute more thanone instruction per clock. And this can be seen in superscalarprocessors. As the amount of parallel hardware withinsuperscalar processors grows, we have to make use of somemethods which effectively utilize the parallel hardware.Performance improvements can be achieved by exploitingparallelism at instruction level.

Instruction level parallelism(ILP) refers to executing low level machine instructions, suchas memory loads and stores, integer adds and floating pointmultiplies, in parallel. The amount of ILP available tosuperscalar processors can be limited with conventionalcompiler optimization techniques, which are designed forscalar processors. One of optimization techniques that in thispaper we focus on it is loop unrolling which is a method forprogram exploiting ILP for machines with multiple functionalunits. It also has other benefits that we present them in section3.III.GENERALIZED LOOP UNROLLING: LIMITATION ANDPROPOSED SOLUTIONLoop unrolling is one kind of code transformationstechniques used by compilers to reach ILP. With loop unrollingtechnique we transform an M-iteration loop into a loop withM/N iterations.

So it is said that the loop has been unrolled Ntimes.This paper is organized as follows. Section 2 describessome goals of designing a superscalar processor and theproblems which would occur. Section 3 describes methods ofloop unrolling and put forwards some new ideas. Section 4reports the results of some experiments. Section 5 describesfuture work. Section 6 concludes. Section 7 thanks people whoencouraged me to prepare this paper.73http://sites.google.com/site/ijcsis/ISSN 1947-5500(IJCSIS) International Journal of Computer Science and Information Security,Vol. 11, No.

5, May 2013-Unrolling FOR Loops. Consider the following countableloop:for(i=0;i<100;i++)a[i]*=2;This FOR loop can be transformed into the followingequivalent loop consisting of multiple copies of the originalloop body:for(i=0;i<100;i+=4){1.q=0;2.while(a>=b)3.{4.a=a-b;5.q++;6.}1.q=0;2.While(a>=b && a>=2*b) //unrolled loop3.{4.a=a-b;5.q++;6.a=a-b;7.q++;8.} //end of unrolled loop9.while(a>=b)a[i]*=2;a[i+1]*=2;a[i+2]*=2;a[i+3]*=2;}Unlike FOR loops operating on arrays which can beunrolled simply by modifying the counter and terminationcondition of loop as illustrated above, WHILE loops aregenerally more difficult to unroll. It is so important because ofdifficulty in determining the termination condition of anunrolled WHILE loop.

Hang and Leng et al. [1] present amethod that we review it briefly.10. {-Unrolling WHILE Loops. We assume that loops arewritten in the form: “while B do S” the semantic of which isdefined as usual. B is loop predicate and S is loop body. It isproved that the following equivalence relation holds.11. a=a-b;12. q++;13. }As mentioned in [3] “The experimental results show thatthis unrolled loop is able to achieve a speed up factor veryclose to 2, and if we unroll the loop k times, we can achieve aspeed up factor of k.”Wherestands for the equivalence relation, and wp(S, B)the weakest precondition of S with respect to post condition B[3].Example 2: A loop for traversing a linked list and countingthe nodes traversed:Therefore we can speed up the execution of the loopconstruct mentioned above by following steps:1.Count =0;1.Form wp(S,B), the weakest precondition of S with respectto B2.While (lp!=NULL)3.{2.Unroll the loop once by replacing it with a sequence oftwo loops:4.lp=lp->next;while (B and wp(S,B)) do begin S;S end;5.Count++;while B do S;6.}The best solution presented by Hang and Leng [3] is toattach a special node named NULL_NODE at the end of thelist.

The link field of this node points to the node itself.3. Simplify the predicate (B AND wp(S,B)) and the loopbody S;S to speed up.To illustrate, consider the following example.With this idea, after unrolling the loop twice, it becomes:Example 1: This example contains a loop for computingthe quotient, q, of dividing b into a:741.Count=0;2.lp1=lp->next;3.lp2=lp1->next;http://sites.google.com/site/ijcsis/ISSN 1947-5500(IJCSIS) International Journal of Computer Science and Information Security,Vol.

11, No. 5, May 20134.While(lp2!=NULL)5.{6.Count+=3;7.lp=lp2->next;8.lp1=lp->next;9.lp2=lp1->next;10.list, they finally visit the middle node of list at thesame time. Therefore the termination condition ofloop is F=L and the middle node won’t becounted. So we count the node by using the lasttwo instructions.2.The number of list nodes is even. In this statethe pointers F and L finally reach the state inwhich following relations holds:(F->right==L) and (L->left==F)}So one of these conditions could be used to form thetermination condition.11. While(lp!=NULL)12.