What is software loop unrolling and why does it help to speedup execution?

What will be an ideal response?

Loops are normally used in iterative techniques involving vectors, tables and arrays; for example, adding 1 to all
the elements of an array. Consider the following.



Loop LDR r0,[r1,#4]! ;Repeat get element

ADD r0,r0,#1 ;Increment element

STR r0,[r1] ;Save element

SUBS r2,r2,#1 ;Decrement loop counter (preset in r2)

BNE Loop ;Repeat until all done

In this case, a trip round the loop involves a read, increment, store, and loop check. Consider the following
where the loop is unrolled by performing two iterations.



Loop LDR r0,[r1,#4]! ;Repeat get element 1

LDR r10,[r11,#4]! ;Repeat get element 2

ADD r0,r0,#1 ;Increment element 1

ADD r10,r10,#1 ;Increment element 2

STR r0,[r1] ;Save element 1

STR r10,[r11] ;Save element 2

SUBS r2,r2,#1 ;Decrement loop counter (preset in r2)

BNE Loop ;Repeat until all done

Note that the first form performs one iteration in 5 cycles and the second performs two iterations in 8 cycles;
that is a single iteration takes 4 cycles, demonstrating a speed up. Now, if the processors were three?way
superscalar, we couldn’t perform the first three operations in parallel because of the data dependency. The
best we could do is to put the loop count decrement and branch in parallel with earlier instructions; that is,



Loop LDR r0,[r1,#4]!

ADD r0,r0,#1 SUBS r2,r2,#1

STR r0,[r1] BNE Loop

This gives us two cycles per iteration. If we do the same to the unrolled loop, we get



Loop LDR r0,[r1,#4]! LDR r10,[r11,#4]!

ADD r0,r0,#1 ADD r10,r10,#1 SUBS r2,r2,#1

STR r0,[r1] STR r10,[r11] BNE Loop

Now we have two iterations in three cycles or 1.5 cycles per iteration.
So, loop unrolling permits greater use of superscalar processing resources by avoiding data dependence by
running multiple iteration trips together.