The MIPS R4000 had an eight-stage pipeline as shown here:
This organization can be completely pipelined without structural hazards, as shown in this pipeline timing diagram:
Cycle ->
Instruction 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0: add $1, $2, $3 IF IS RF EX DF DS TC WB
1: add $4, $5, $6 IF IS RF EX DF DS TC WB
2: add $7, $8, $9 IF IS RF EX DF DS TC WB
3: add $10,$11,$12 IF IS RF EX DF DS TC WB
4: add $13,$14,$15 IF IS RF EX DF DS TC WB
5: add $16,$17,$18 IF IS RF EX DF DS TC WB
6: add $19,$20,$21 IF IS RF EX DF DS TC WB
7: add $22,$23,$24 IF IS RF EX DF DS TC WB
8: add $25,$26,$27 IF IS RF EX DF DS TC WB
Pipeline speedup
What is the ideal pipeline speedup for the R4000
Data hazards and forwarding
For each data hazard that can happen between R-type instructions with this organization between: 1) show a sequence of MIPS instructions that has that that hazard and no others. 2) Explain what forwarding would be necessary to avoid it (e.g. forward the ALU result from EX/DF of instruction 0 in cycle 4 to ALU input in EX of instruction 1 in cycle 5). 3) Give a multi-cycle pipeline diagram showing any stalls necessary with a line drawn between the end of one stage to the beginning of a stage in the next cycle, showing the forwarding you propose.
Data load/compute hazards
Repeat the previous problem, but showing hazards between data from a load instruction to be used by an R-type instruction.
Data compute/store hazards
Repeat the previous problem, but showing hazards between data from an R-type instruction to be used by a store instruction.
Data load/store hazards
Repeat one more time, showing hazards between data load and data store.
Forwarding organization
Draw a version of the R4000 pipeline organization with all of these forwarding paths
In class, we used this single-cycle organization for the SSEM, assuming a modern multi-port register unit could be used for the 32-words of memory.
This a microcode representation of how this datapath is used for each of the seven instructions:
JMP: Data0=Mem[C]; Data1=Mem[Data0[12:0]]; ALU=0+Data1; C=ALU+1 JRP: Data0=Mem[C]; Data1=Mem[Data0[12:0]]; ALU=C+Data1; C=ALU+1 LDN: Data0=Mem[C]; Data1=Mem[Data0[12:0]]; ALU=0-Data1; A=ALU; C=C+1 STO: Data0=Mem[C]; Mem[Data0[12:0]]=A; C=C+1 SUB: Data0=Mem[C]; Data1=Mem[Data0[12:0]]; ALU=A-Data1; A=ALU; C=C+1 CMP: Data0=Mem[C]; ALU=C+1; if(A<0) C=ALU+1 else C=C+1 STP: Data0=Mem[C]; ALU=C-1; C=ALU+1
Pipelining an organization
Draw a modified architecture with a 3-stage pipeline: instruction fetch, data memory, execute. You do not need to include forwarding.
Microcode
Write microcode for the seven instructions on your architecture. Assume every microcode instruction includes the microcode address of the next-instruction
Hazards
Which pairs of instructions could possibly have hazards, what kind of hazard, and how many cycles of stall would be necessary to resolve the hazard?
Forwarding
Which of these cannot be resolved by forwarding? Assuming you do as much as you can with forwarding, how many cycles of stall cannot be avoided for each case.
As this homework does not include programming, you should submit a hard copy of your assignment at the beginning of class on the due date. Electronic or email submissions will not be accepted for this assignment.