5. Pipeline and Hazards

• for lecturer: tutorial 5

1. Fibonacci sequence
2. Transcription C code to assembler
3. Simulation and debugging for processor without pipeline (Mips simulator).
4. Simulation and debugging for processor with pipeline (MipsPipeS simulator).

1. To understand the previous lecture.

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

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

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

To the calculated Fibonacci number (for instructional purposes) add 15. In your program you may use following instructions:

• add, addi, bne, beq.

More detailed instructions description:

Possible solution in C:

t0 = 5;  //  Set N value
s0 = 0;  //  F(0)
s1 = 1;  //  F(1)
 
for(t1 = 2; t1 < t0; t1++)
{
	t2 = s0 + s1;
	s0 = s1;
	s1 = t2;
}
s1 += 15;
 
while(1)
	;   // Final infinite loop

For your assembler version of the program you may use following template:

#define t0 $8
#define t1 $9
#define t2 $10

#define s0 $16
#define s1 $17
#define s2 $18

.globl start
.set noat
.set noreorder
.ent start

start:
// Fill in your code here...

nop
.end start

Debug your code for Mips simulator and then make your code work in MipsPipeS simulator.

Note how the delay slots are handled. They filled automatically by compiler, who will fill in following instruction:

1. If there is not a label set for instruction before branch, the compiler will move such instruction after the branch instruction.
2. Otherwise the compiler will fill in the NOP instruction.

This behavior of the compiler can be turned off by following pseudoinstruction:

.set noreorder

Compile your code with this pseudoinstruction, try to execute your code in the MipsPipeS simulator and observe the differences. Modify your code for the pipelined processor (MipsPipeS) in such way, that it will produce the same value as on processor without pipeline (Mips).

Try to find out rules for the compiler, with which the compiler will produce the program without data and control hazards - program will have the same results as in Mips simulator (without pipeline).

Modify your code to write the result (F(N) + 15) to memory on address 0x02 (using sw instruction) and then read the value back into a register (using lw instruction). Execute your program in MipsPipeS and MipsPipeXL simulators. Observe the execution closely, namely the sw and lw instructions.

• Find out how the add instruction is executed.
• Find out how the addi instruction is executed.
• Find out how the lw instruction is executed.
• Find out how the sw instruction is executed.
• How many clocks does it take to find out the branch target address? And how I will find it out? (instructions beq a bne)