Question

Consider the following loop.

loop:lw r1,0(r1)

and r1,r1,r2

lw r1,0(r1)

lw r1,0(r1)

beq r1,r0,loop

Assume that perfect branch prediction is used (no stalls due to control hazards), that there are no delay slots, and that the pipeline has full forwarding support. Also, assume that many iterations of this loop are executed before the loop exits.

4.11.1 Show a pipeline execution diagram for the third iteration of this loop, from the cycle in which we fetch the first instruction of that iteration up to(but not including) the cycle in which we can fetch the first instruction of the next iteration. Show all instructions that are in the pipeline during these cycles (not just those from the third iteration).

4.11.2 How often (as a percentage of all cycles) do we have a cycle in which all five pipeline stages are doing useful work?

Short answer

4.11.1. Pipeline execution diagram for the third iteration of the loop:

Instructions
lw r1,0(r1)	WB
lw r1,0(r1)	EX	MEM	WB
beq r1,r0,Loop	ID	****	EX	MEM	WB
lw r1,0(r1)	IF	****	ID	EX	MEM	WB
and r1,r1,r2			IF	ID	****	EX	MEM	WB
lw r1,0(r1)				IF	****	ID	EX	MEM
lw r1,0(r1)						IF	ID	****
beq r1,r0,Loop							IF	****

4.11.2 Useful work done by the five pipeline stages.

Cycles in which all stages do useful work -0

Step-by-step solution

Determine the 5-staged pipeline.

The 5-stage pipeline has five steps:

1. The instruction will be fetched from the memory.
2. The fetch instruction will be decoded by reading the registers.
3. The decoded instruction will be executed with the values read from the registers.
4. The operands in the data memory will be accessed.
5. The result will be written back into a register.

Determine the pipeline diagram for the third iteration of the loop.

4.11.1The pipeline stages of the third iteration of the loop are as follows:

Instructions
lw r1,0(r1)	WB
lw r1,0(r1)	EX	MEM	WB
beq r1,r0,Loop	ID	****	EX	MEM	WB
lw r1,0(r1)	IF	****	ID	EX	MEM	WB
and r1,r1,r2			IF	ID	****	EX	MEM	WB
lw r1,0(r1)				IF	****	ID	EX	MEM
lw r1,0(r1)						IF	ID	****
beq r1,r0,Loop							IF	****

Determine the percentage of cycles in which all stages do useful work.

4.11.2

In the pipeline diagram of 4.11.1, the stalled stages will not have names in the particular cycle.

The stages marked in blue mention that the particular stage is not doing useful work.

So, the total cycle per iteration is 8.

Cycles in which all stages do useful work is none.

So, the percentage of cycles in which all stages do useful work is 0%.