CS-343 Assignment 7
Solutions

The right one. The left one has 4 as one input because it computes PC+4. The right one computes PC+4 + part of the instruction (namely the immediate field shifted left two positions and sign extended), which is the Branch Target Address.

The ALU is used to compute memory addresses for lw and sw instructions, so its output has to go to the address input of data memory. It also computes arithmetic results for R-type instructions, so its output has to go to the WD input of the register file also. At most one of these two destinations would be used for any particular instruction.

To the RR1 and RR2 inputs of the register file.

They come from the RD1 and RD2 outputs of the register file.

Because it is always safe to read two registers from the register file even if their values are not used. As long as their values are not used to alter the state of the registers and/or the data memory, no harm is done by reading them out.

It subtracts R[rt] from R[rs] to see if they are equal.

If it is true, the data read from memory will be connected to the WD input of the register file. Otherwise, the output of the ALU will be connected to the WD input of the register file.

Only the lw instruction.

To tell if the op code is beq AND the ALU result is zero.

For R-type instructions, the rd field of the instruction should be connected to the WR (write register number) input of the register file. Since the rd field occupies bits 15-11 of R-type instructions, RegDst should be 1 for R-type instructions.

For lw instructions, the immediate field “covers” the rd field, and the rt field, bits 20-16, must be used instead. Thus, RegDst has to be set to 0 for lw instructions.

It doesn’t matter: sw instructions don’t cause anything to be written into the register file, so it doesn’t matter what bits are connected to the WR input to the register file.

It doesn't matter: beq instructions don’t cause anything to be written into the register file, so it doesn’t matter what bits are connected to the WR input to the register file.

The amount of time it takes to process (fetch and execute) an instruction.

The rate at which instructions are processed (completed). Instructions per second.

For the single-cycle datapath, they are simple reciprocals of each other. It takes exactly one clock period to fetch and execute an instruction using the single-cycle datapath, and one instruction is completed for each clock period. In this case, the instruction rate (throughput) is the reciprocal of the clock period.

Seconds/Program = Instructions/Program × Clock cycles/Instruction × Seconds/Clock cycle

The largest number of propagations delays necessary to process the slowest instruction.

lw, because it requires the longest sequence of dependencies: instruction fetch, register read, compute address, read from memory, write to register file.

One in which the number of propagation delays in each stage are exactly equal.

Latency is the sum of the propagation delays in all the stages for a perfectly balanced pipeline. But if the pipeline is not perfectly balanced, the latency is n times the number of propagation delays in the slowest stage, where n is the number of pipeline stages.

It will be n times faster.

The latency does not change.

It will be n times greater.

Structural: when two different instructions need the same piece of computational hardware at the same time and one has to wait for the other. Data: When an instruction requires an operand value that is not available at the time it is needed. Control: when a branch instruction causes instructions already partially executed to be abandoned.

Trying to use the ALU to compute the BTA and the difference between R[rs] and R[rt] at the same time. The solution is to add a separate adder to the datapath for computing the BTA.

When an operand from an instruction is a result produced by a previous instruction that is still working its way through the pipeline. Register Forwarding is the name of the technique that gets the needed result from a “downstream” pipeline register without waiting for it to work its way down to the last stage and written back to the register file.

Delayed loads is the technique that defines the MIPS instruction set so that the next instruction following a lw instruction is guaranteed not to receive the value fetched by the lw instruction; it gets the previous value.

All conditional branch instructions introduce control hazards. One solution is speculative execution in which part of the datapath hardware id duplicated so that both the instructions immediately following the branch instruction and those starting at the BTA start being processed while waiting for the the decision whether to branch or not has been resolved.

Data hazards: see above.

When an instruction enters the ID stage, its rs and rt register numbers are compared to the destination register numbers of all instructions currently ahead of it in the pipeline. If there is a match, the data from the corresponding pipeline register is substituted for the R[rs] or R[rt] output of the register file as necessary.

The throughput increases proportionately to the number of stages, because the clock speed increases in proportion to the number of stages.

The penalty for control hazards is greater than for shallower pipelines because more partially completed instructions have to be discarded.

Each pipeline register holds all the control and data information that will be needed in successive stages of the pipeline to complete execution of the instruction at the current stage of the pipeline.

n + 1: One for the PC, one for the register file, plus n - 1 for the pipeline registers.