Post
by **walker7** » Wed May 30, 2018 10:52 pm

For those who are interested, let me explain the derivation of the formula.

Assume that the instruction(s) take *c* cycles to execute. The DBRA takes 10 cycles when taken, and 14 cycles when not taken.

When the loop is completely rolled, each iteration takes *c*+10 cycles. The final iteration takes *c*+14 cycles.

The variable *r* represents the number of iterations.

Therefore, the total number of cycles is: *C1* = *r*(*c*+10)+4.

For unrolling, consider the variable *u*, which is the unroll factor. That is, the looped instructions are listed *u* times before DBRA.

When the loop is unrolled the formula becomes *uc*+10 for all but the final iteration, and *uc*+14 for the final iteration.

But, the number of loop iterations becomes *r*/*u*, not just *r*.

The formula then becomes: *C2* = (*r*/*u*)(*uc*+10)+4.

Since *C2* < *C1*, we then calculate the time savings as *C1* - *C2*.

The formula becomes: *D* = *C1* - *C2* = [*r*(*c*+10)+4] - [(*r*/*u*)(*uc*+10)+4].

It then simplifies to: *D* = 10*r* * ((*u*-1)/*u*).

The variable *c* has vanished, so no matter what your loop does, just go by the number of iterations needed.

If you were to graph this with *D* as the dependent variable and *u* as the independent variable (*r* is constant), it looks kind of like a square root or logarithm function. That is, it rises steeply at first, then rises more slowly.

The function is monotone increasing, which means that the more iterations you unroll, the more time saved. But, the more iterations unrolled, the more space used up. There could be a nice compromise where the tangent slope of the function is equal to 1.

To find the tangent slope, take the first derivative of the function with respect to *u*. Then, set it equal to 1 and solve for *u*.

Function: *D* = 10*r* * ((*u*-1)/*u*)

1st Derivative: *D*' = 10*r* / *u*^2

10*r* / *u*^2 = 1

*u* = sqrt(10*r*)

(*u* is the unrolling factor, *r* is the number of iterations)

And there you have it! The reason for multiplying by 10 is because of how a DBRA instruction takes 10 cycles when the branch is taken.

Last edited by

walker7 on Fri Jun 08, 2018 7:36 pm, edited 1 time in total.

When programming, you can do it if you put your mind to it.