Build a Datapath, part III

Due: 5:00 pm (US CDT/UTC-5) Monday 5 October
Summary: You will complete the datapath for a simple Logisim-based ISA with control-flow instructions.
Collaboration: You will continue work with your previous collaborator. You must complete the work together in these groups, whether during or after the scheduled lab time.
Submitting: The work for Parts A and B will be checked off by the instructor or mentor.

Overview

In this continuation of the lab we add support for control flow in the PIPS instruction set: jump instructions and conditional branches. Your work will augment and update your existing datapath.circ, microprogram.hex, and rules.py files from the previous labs.

Although it may be possible to proceed without having finished the previous portion of the lab, you will be better positioned for this work if you do. Please undertake completion of parts I and II before working on this lab.

Part A: Jumps

We’ll start today’s lab with the jump instructions. This opcode includes all three types of unconditional jumps: j, jal, and jr. These instructions work the same way in PIPS as they do in MIPS, but it’s worth looking at how they are encoded:

j: This instruction is encoded as a regular iformat instruction with the opcode 15 (the last opcode in our microprogram ROM). The destination of the jump is encoded using the sixteen bits of the immediate field. There’s no need for pseudo-direct addressing in PIPS; addresses are 16 bits, so the immediate field has plenty of space to hold any jump destination.
jal: This instruction works exactly like a j instruction, except for two important differences: the instruction should be encoded to turn on the link field (bit 17 of the instruction), and the return address (PC+4) should be written to register $ra. The link field indicates to the datapath that instead of writing the ALU result, the register file should store the value of PC+4 when executing this instruction.
jr: This instruction is also similar to the j instruction, but it is an rformat instruction and should use the value of a register as the jump destination rather than using the immediate field. In PIPS, the jump destination is the value of the register encoded in the r2 field, which comes out of the register file in output $R_{d1}$ .

Implementation

To implement these instructions you will need to make a few changes to your datapath:

Select a bit in your control unit’s microprogram to indicate that a particular instruction is a jump. Add a splitter to pull this jump control line bit out of the microprogram ROM’s output.
Use a multiplexor to choose the jump destination (which may be either $R_{d1}$ or the immediate field).
Use another multiplexor connected to the jump control line to select either PC+4 or the jump destination (above) when updating the program counter register. The provided datapath always uses PC+4, so you will need to break the existing connection.
Use the link field of the instruction to determine whether the register file’s $W_d$ input receives the ALU result or PC+4 as the data to be written.
Once you’ve made these connections, edit your control signals for the jump opcode (in microprogram.hex); be sure to include all the necessary documentation both for the new bit field (at the top) and the value it takes in the opcodes.
Finaly, write the translation rules for each of the three instructions above (in rules.py). A few notes:
- To set the link field in the machine instruction for jal, your pips.iformat call should include the parameter link=True.
- Remember that some (but not all) jump instructions need to write to a register. You will need to make sure j and jr do not modify any registers in the register file by setting the destination register to $zero; writes to this register are ignored.

Testing

Write a program using labels and each of the various jump instructions to test your implementation. A simple infinite loop that increments registers would be a reasonable test for this part. Make sure the jr and jal instructions work also correctly; you can do this by using jal to go to a label, perform some simple operation, and then use jr $ra to return to the next instruction after the call.

You should see the program counter moving around as expected, but you will almost certainly discover something has gone wrong with your arithmetic instructions.

What went wrong?

If your implementation went the way mine did, you likely discovered that instructions executed immediately before a branch do not seem to have an effect. This happens because of a race condition. A race condition is any set of events in a concurrent system (such as our datapath) where two events can occur in either order, but we want them to happen in a specific order.

Here is the rundown: Our datapath begins executing an add instruction on a rising clock edge. The datapath reads the input registers, passes their values to the ALU, and then sends the result back to the register file to be written. On the next rising clock edge, the register file writes the result. However, this rising clock edge also triggers a move to the next instruction. If that instruction does not turn on the write enable control line the outcome is uncertain; the register file may write the value if it sees the clock edge before write enable is turned off, but it may not if the clock signal arrives second.

To fix this we need to delay writing to the register file to make sure we write values in the middle of an instruction’s execution rather than right at the end of the instruction’s execution. This is a fairly easy fix:

add a NOT gate before the clock connection to the register file so it will write registers on falling clock edges, which happen at the midpoint of an instruction’s execution.

One small complication from making this fix is that your datapath will not fully execute the first instruction in your program. From now on you will need to add a nop as the first instruction of any program you write for your PIPS datapath.

Please have the instructor or a mentor sign off on this part before moving on. You should be prepared to show your well-documented microprogram, your test program (whose comments also indicate the expected behavior), and assembler rules. You will demonstrate the assembly of your program, load it, and run it.

Part B: Conditional Branches

Now that you have unconditional control flow working it’s time to add support for conditional branches. We’ll implement the same two branch instructions supported by MIPS: beq and bne.

beq: This instruction is encoded in immediate format. As with unconditional jumps, the branch destination is held in the immediate field; PIPS does not use relative addressing for branch instructions. The beq instruction should only go to this branch destination if the values of two registers are equal. These registers are passed in the fields $r0$ and $r1$ . Note that we’ve only used $r0$ as the written register up to this point.
bne: This instruction is exactly like beq except it should not jump if the two register values are equal.

To implement the beq instruction you will need to choose an available bit in the microprogram and add a control line that indicates that the current instruction is a conditional branch. If this bit is set and the output of the ALU is zero, then your datapath should jump to the branch destination. This will require some changes to your various control circuits.

You will also need to choose an additional bit in your microprogram and use it for another control line that tells your datapath to use $r0$ as the second register file read address instead of $r2$ . This allows you to read two registers while also using the immediate field as the branch destination.

Once you have the beq instruction working, add a third additional control line to your microprogram that inverts the $zero$ output of the ALU so you can implement bne. When you are finished you should have logic that ultimately implements the following policy:

If the jump control line is on, set the PC to the jump destination.
If the branch control line is on, the branch invert control line is off, and the ALU’s zero output is 1, set the PC to the jump destination.
If the branch control line is on, the branch invert control line is on, and the ALU’s zero output is 0, set the PC to the jump destination.
Otherwise, set the PC to PC+4.

You should write at least one program to test both your bne and beq instructions. The tests should also make sure your datapath can still execute the arithmetic instructions you implemented before when combined with jump and branch instructions.

CC-BY-NC-SA This work is licensed under a Creative Commons Attribution NonCommercial ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.