CS316 Programming Assignment 3: FAQ

Instructor: Kavita Bala

Due: Tuesday, October 12th, 2007, 11:59pm


12 October 4:45PM: The cs316 Logisim library has been updated to fix a bug in the encoding of branch instructions.

12 October 4:00PM: If you have problems with the first instruction of your test program being skipped, it is a bug in Logisim or your circuit. To help ensure it is not a Logisim bug, every time you reset the simulation, use the arrow tool to click on any empty space to cause Logisim to make sure all of the values are up-to-date before doing anything else. You should also use the tick-once command (control-t) rather than poking the clock to run your circuit.

8 October 3:40AM: Yet another update to the cs316 Logisim library. This release rolls back yesterday's changes to the MIPS Program ROM.

When writing numerical jump targets and branch offsets in assembly, there are at least two conventions one can choose. The targets and offsets can be represented in terms of actual word-aligned PC addresses, or in terms of the number of instructions. For example, to jump to the second instruction in the program, you would write j 4 if the first convention is being followed; or you can write j 1 if the second convention is used.

It doesn't matter which convention is used as long as the compiler and the assembler agree. The MIPS Program ROM implemented in the CS316 Library includes an assembler that follows the first convention (PC offsets).

So, all branch offsets and jump targets that you will write in assembly are actual PC offsets and PC targets, so they have to be word-aligned because the PC is always word-aligned. When they get encoded as MIPS instructions, though, the lowest two bits of the targets and offsets will be dropped (since they're always zero).

What will probably confuse you is that looking at the BEQ documentation in MIPS Vol.2 (for example), it seems to imply that the "offset" in the instruction encoding and the "offset" in the assembly instruction are numerically the same, when in fact they are not (at least in the assembly language implemented by the Program ROM): "Offset" in encoding = "offset" in assembly >> 2.

Note that when coding in assembly, you can sidestep this whole issue by jumping and branching to labels and letting the assembler figure it out for you. It's better coding style anyway.

7 October 7:25PM: The cs316 Logisim library has been updated yet again. This release fixes a bug in the register file. Writes to the register file now happen on the falling edge of the clock, out of phase with the pipeline registers. This avoids the need to forward data from the WB stage.

7 October 3:30PM: The cs316 Logisim library has been updated again. This release fixes bugs in the handling of branch instructions that were overlooked in the previous release.

7 October 1:45PM: The cs316 Logisim library has been updated. This release fixes bugs in the handling of branch instructions. Also included is a drop-in replacement for the RAM component built into Logisim, which exhibits bugs when you try to do logging with it.

2 October 4:30PM: Make sure you set the WE for the register file correctly.  A common mistake in PA2 was, to instead of set WE, to set the write to occur to register $0 when WE would normally be off.  This will not work in PA3.  You should correctly compute the value of WE.

2 October 4:25PM: Some sequences of assignments are hazards between two registers, such as:

  addu $1, $2, $3 # $1 is computed here...
  addu $4, $3, $1 # ...and used here, but it isn't through the pipeline yet!

The processor designer (you) can avoid requiring no-ops to separate these hazards by detecting when they occur; in this case, the current ALU phase can detect that rW, the register being written, is the same as rB, one of the inputs, in the current Fetch/Decode phase (the next instruction), and send the output of the ALU backwards in the pipeline to be available immediately.

  addu $1, $2, $3 # same as before...
  addu $4, $3, $1 # same as before...
  addu $4, $3, $1 # and again, but $1 still isn't done yet!
  addu $4, $3, $1 # this is not a hazard because $1 is written back in time.

In this example, the same kind of forwarding needs to occur from the Memory phase all the way back to the Fetch/Decode phase; note that if both the ALU and Memory phases are writing to a register needed for an input in Fetch/Decode, the ALU phase contains the more recent instruction and its value takes precedence.


There is, however, a kind of hazard you are NOT required to handle, and will instead need to be aware of in order to insert no-ops in test programs.  Consider the following:

  lw $1, 0($0)    # load the contents of memory location 0x0 into register $1
  addu $4, $3, $1 # $1 hasn't been retrieved yet!

You do not need to detect this; instead, be sure that enough time has passed after a load before its value is used:

  lw $1, 0($0)    # load the contents of memory location 0x0 into register $1
  nop             # the load instruction is currently in ALU
  addu $4, $3, $1 # the value is now available in the Memory phase

Note that only one no-op is needed because as soon as the value has been found in the Memory phase, it can be forwarded as in the arithmetic cases above; you must do this forwarding.  You need not, however, stall the pipeline to wait for the value; instead assume no-ops will be manually inserted and be sure that they are in all your own test cases.

  1. Implement forwarding to avoid data hazards at the ALU phase.
  2. Implement forwarding to require only one no-op for data hazards at the Memory phase (lw being the only instruction to which this is
  3. Ensure that one instruction (e.g. a nop) separates a load from any instruction that uses the value loaded.
  4. Ask questions if any of the causes of hazards or details of data forwarding elude you.

Page maintained by Kavita Bala