Computer
Architectures Education

Write a code for the calculation of the N-th Fibonacci number (for \(N > 2\)). The Fibonacci sequence is defined as follows:

$$ F(n) = F(n-1) + F(n-2) $$ for \( n > 2 \), and $$ F(0) = 0, F(1) = 1 $$

Here are the first few numbers in the Fibonacci sequence: $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,... $$

Modify the code in such a way that it does have no hazards (the code produces correct results in the pipelined execution without the hazard unit). Minimize the number of nops in your code. Prefer instruction reordering whenever possible.

The input number 'n' is at location 'input'. Save your result to location output. Execute with pipeline with no hazard unit.

A possible solution in C

t0 = 5;  //  Set value of N
s0 = 0;  //  F(0)
s1 = 1;  //  F(1)

for(t1 = 2; t1 <= t0; t1++)
{
        t2 = s0 + s1;
        s0 = s1;
        s1 = t2;
}

Input: Data hazard prevention.