Problem 1

Consider two different machines. The first has a single cycle datapath (i.e., a single stage, non-pipelined machine) with a cycle time of 4ns. The second is a pipelined machine with four pipeline stages and a cycle time of 1ns.

Part (a) What is the speedup of the pipelined machine versus the single cycle machine assuming there are no stalls?

Part (b) What is the speedup of the pipelined machine versus the single cycle machine if the pipeline stalls 1 cycle for 30% of the instructions?

Part (c) [2 points] Now consider a 3 stage pipeline machine with a cycle time of 1.1ns. Again assuming no stalls, is this implementation faster or slower than the original 4 stage pipeline? Explain your answer.

Problem 2

Consider two different 5-stage pipeline machines (IF ID EX MEM WB). The first machine resolves branches in the ID stage, uses one branch delay slot, and can fill 60% of the delay slots with useful instructions. The second machine resolves branches in the EX stage and uses a predict-not-taken scheme. Assume that the cycle times of the machines are identical. Assume that 15% of the instructions are branches, 25% of branches are taken, and that stalls are due to branches alone. Which machine is faster? To get any credit, you must justify your answer. 

Problem 3

Consider a pipeline with the following structure: IF ID EX MEM WB. Assume that the EX stage is 1 cycle long for all ALU operations, loads and stores. Also, the EX stage is 3 cycles long for the FP add, and 6 cycles long for the FP multiply. The pipeline supports full forwarding. All other stages in the pipeline take one cycle each. The branch is resolved in the ID stage. WAW hazards are resolved by stalling the later instruction. Assume that there are different registers for FP and int data types, there are different multipliers for FP multiplication and int multiplication operations and there are different adders for FP Addition and int addition. Also assume that all functional units are pipelined. For the following code, list all the data hazards that cause stalls. State the type of data hazard and give a brief explanation why each hazard occurs.

loop:                L.D F0, 0(R1)                  #1

                        L.D F2, 8(R1)                 #2

                        L.D F4, 16(R1)               #3

                        L.D F6, 24(R1)               #4

                         ADD.D F10, F4, F0        #6

                         ADD.D F8, F2, F0          #7

                      S.D 0(R2), F8                  #8

                       DADDI R2, R2, 8            #9

                       S.D 8(R2), F10               #10

                       DSUBI R1, R1, 32            #11

                      BNEZ R1, loop                 #12

                        MULT.D F8, F6, F0           #5

Problem 4 For this problem, we will explore a pipeline for a register-memory architecture. The architecture has two instruction formats: a register-register format and a register-memory format. In the register-memory format, one of the operands for an ALU instruction could come from memory.

There is a single memory-addressing mode (offset + base register). The only non-branch register-memory instructions available have the format:

Op Rdest, Rsrc1, Rsrc2

or

Op Rdest, Rsrc1, MEM

where Op is one of the following: Add, Subtract, And, Or, Load (in which case Rsrc1 is ignored), or Store. Rsrc1, Rsrc2, and Rdest are registers. MEM is a (base register, offset) pair.

Branches compare two registers and, depending on the outcome of the comparison, move to a target address. The target address can be specified as a PC-relative offset or in a register (with no offset). Assume that the pipeline structure of the machine is as follows:

IF RF ALU1 MEM ALU2 WB

The first ALU stage is used for effective address calculation for memory references and branches. The second ALU stage is used for operations and branch comparison. RF is both decode and register-fetch stage. Assume that when a register read and a register write of the same register occur in the same cycle, the write data is forwarded.

(a) Find the number of adders, counting any adder or incrementor, needed to minimize the number of structural hazards. Justify why you need this number of adders.

(b) Find the number of register read and write ports and memory read and write ports needed to minimize the number of structural hazards. Justify why you need this number of ports for the register file and memory.

 (c) Will data forwarding from the ALU2 stage to any of ALU1, MEM, or ALU2 stages reduce or avoid stalls? Explain your answer for each stage.

 (d) [3 points] Will data forwarding from the MEM stage to any of ALU1, MEM, or ALU2 stages reduce or avoid stalls? Explain your answer for each stage.