Loop Unrolling and Fibonacci: Consider the Following Pseudo-C Code to Compute

question 12

Essay

Loop Unrolling and Fibonacci: Consider the following pseudo-C code to compute the fifth Fibonacci number (F(5)).
1 int a,b,i,t;
2 a=b=1; /* Set a and b to F(2) and F(1) respectively */ 3 for(i=0;i<2;i++)
4 {
5 t=a; /* save F(n-1) to a temporary location */ 6 a+=b; /* F(n) = F(n-1) + F(n-2) */
7 b=t; /* set b to F(n-1) */ 8 }
One observation that a compiler might make is that the loop construction is somewhat unnecessary. Since the the range of the loop indices is fixed, one can unroll the loop by simply writing three iterations of the loop one after the other without the intervening increment/comparison on i. For example, the above could be written as:
1 int a,b,t;
2 a=b=1;
3 t=a;
4 a+=b;
5 b=t;
6 t=a;
7 a+=b;
8 b=t;
(a) Convert the pseudo-C code for both of the snippets above into reasonably efficient MIPS code. Represent each variable of the pseudo-C program with a register. Try to follow the pseudo-C code as closely as possible (i.e. the first snippet should have a loop in it, while the second should not).
(b) Now suppose that instead of the fifth Fibonacci number we decided to compute the 20th. How many static instructions would there be in the first version and how many would there be in the unrolled version? What about dynamic instructions? You do not need to write out the assembly for this part.

---

Definitions:

Low-Cost Leadership

A strategy where a business aims to become the least costly producer in its industry while maintaining sufficient levels of quality.

Product Differentiation

The process of distinguishing a product or service from others in the market to make it more attractive to a particular target market.

Total Assets Turnover Ratio

A financial metric that measures the efficiency of a company's use of its assets in generating sales revenue; calculated by dividing sales revenue by total assets.

Sales

The transactions involved in selling goods or services in return for money or other compensation.