Build a Datapath, part II

Overview

In this continuation of the lab we will finish implementing most of the PIPS instruction set, with support for jump instructions, conditional branches, and memory operations. In addition, we will use memory-mapped I/O to connect a terminal to your datapath so your programs can actually produce output. Your work will augment and update your existing datapath.circ, microprogram.hex, and rules.py files from the previous labs.

Although it might be possible to proceed without having finished the previous lab, you will be better positioned for this work if you do. Please complete part I before working on this lab.

Grading Guidelines

Beginning with Part D of this lab, your datapath will ultimately be assessed by a test suite, and the final grade mostly determined by how many tests your datapath passes.

In addition to verifying circuit and program correctness, other elements of style will also be considered.

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:

  1. 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.

  2. Use a multiplexor to choose the jump destination (which may be either \(R_{d1}\) or the immediate field).

  3. 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.

  4. 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.

  5. 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 all the opcodes (including those you may have previously implemented).

  6. Finally, write the translation rules for each of the three instructions above (in rules.py). A few notes:

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:

  1. If the jump control line is on, set the PC to the jump destination.
  2. 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.
  3. 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.
  4. 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.

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 C: Memory Accesses

The last major piece we’ll add to our datapath in this lab is support for standard memory operations. PIPS is a 16-bit architecture, so a word in this architecture is a 16-bit value. In addition to loading and storing words, we will also want to support loading and storing individual bytes of data.

The datapath provided with the first lab includes a memory controller and a RAM element at the far right edge of the datapath. You should not make any direct connections to the RAM element; the memory controller takes care of some ugly details that make it possible to support writes to individual bytes.

As with the MIPS datapath, we’ll use the output from the ALU as the address we are loading from or storing to. For a write operation, you will need to pass the data you would like to write to the \(W_d\) field, and turn on the \(W_e\) input. If you are writing or reading a byte, send a zero to the bottom control line; otherwise send a one to this control line. For load operations, the read data comes out on the \(R_d\) port. This value is always 16 bits, even if you are just loading a byte.

Just as you did with the register file, you will need to invert the clock input to the memory controller. This avoids the unpredictable behavior we could see when writing a value just as the write enable input to the memory controller changes.

You will need to add control lines from your microprogram ROM output that tell memory whether to enable writes and whether your operation should access a byte or a full word. Another control line should indicate whether the register file write data comes from the ALU result or the memory \(R_d\) port. With these added lines you should be able to implement lw, lb, sw, and sb. Remember that lw and lb use the value of the register specified in the \(r1\) field as the base address, add an immediate value to this address, and then store the loaded value into the register specified in field \(r0\).

The sw and sb instructions do not update any registers, so these instructions will use the value of the register specified in the \(r0\) field as the value to store; you should already have support for reading this register from the beq and bne instructions. You will need to pass the register file output \(R_{d1}\) on to the memory controller to store this value. For the lw and lb instructions, you will need to add one final control line that takes the output of memory and passes it back to the register file instead of the ALU result.

Once your datapath supports load and store instructions you should implement assembler rules for these instructions and test them. At this point you should be able to write procedures that use the stack, although you will need to explicitly load a stack starting address into the $sp register at the start of your program. To do this, just insert li $sp, 0xf800 before the main body of your program. This sets up your stack at the address 0xf800, and the stack can grow downward. The choice of address is largely arbitrary, although we’re leaving space in the upper addresses for some extra features we’ll add later. Because we control the entire processor, it is safe to statically assign memory locations like this.

Test your datapath by writing an interesting procedure that uses conditional branches and stack operations (e.g., your remainder and gcd procedures from Assignment 5 should be able to run with minimal modifications for PIPS). Call the procedure from at least two different points and verify that it does what you expect. You may assume that PIPS calling conventions work much like MIPS calling conventions, except that we have fewer registers.

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 D: Terminal Output

Logisim has two useful features we will add to the PIPS datapath: command-line invocation, and terminal output. The terminal component makes it possible for your circuit to produce text output, and command-line invocation allows you to run PIPS programs on your datapath from the Linux command line, rather than inside of Logisim. We’ll need to make two small changes to the datapath to support these features.

Adding a halt output

You can run Logisim circuits from the command line, but Logisim needs to know when they’ve finished so the program will terminate. To indicate that a circuit has terminated, you must add an output with the name “halt” and set this output to 1. We’ll just choose an arbitrary program counter value, say 0xff00, that indicates when a program has terminated, and then jump to this location when we want the program to stop.

Add a Comparator from Logisim’s Arithmetic components, and compare the current program counter value to the constant 0xff00. If the two are equal, turn on the halt pin. This will work when your circuit is run from the terminal, but it won’t stop the circuit when you run it inside of Logisim. To make both work, invert the value passed to “halt” and connect this to the enable pin of the program counter registers. This will allow the program counter to update until the program counter reaches 0xff00.

Write a simple program named halt_test.s that performs a few simple operations and then jumps to 0xff00. Assemble this program and load it into your datapath inside of Logisim. Select “Ticks Enabled” from the “Simulation” menu to start running the program. You may want to increase the tick frequency in this menu as well. Verify that your program runs, jumps to 0xff00, and then the program counter stops changing even though the clock continues to tick.

Once that works, save your circuit and open a new terminal window. To run the same program, type the following shell command from your datapath directory:

$ java -jar /home/curtsinger/shared/logisim.jar -tty halt -load programs/halt_test.hex datapath.circ

This should run your circuit briefly, print “halted due to halt pin”, and then terminate. If the command does not terminate you may have named the “halt” output incorrectly. If you see the error “No RAM was found for the ‘-load’ option”, you will need to make sure “main” is indeed set as the main circuit. The instructor or mentor can help you troubleshoot at this point.

Connecting to a terminal

Real MIPS microprocessors incorporate the standard registers detailed in our textbook, but they also add some additional features; some of them use predefined pointer names like TRISA, LATA, and PORTA. These values are locations in memory, but writes or reads to those locations control special peripheral devices (electronic connector pins on the CPU’s host board) instead of just accessing memory. This is a common technique for adding peripherals to architectures without modifying the instruction set to support extra operations or registers. We will use this trick to add a terminal to our datapath so PIPS programs can produce text output.

First, select a “TTY” component from the “Input/Output” category in Logisim and add it to your datapath below the memory controller. Connect this terminal to an inverted clock signal, just as you did with the register file and memory controller. The terminal has two other inputs: a character to write, and an enable pin. We will connect the terminal’s data input to the data being written to memory, but only enable writes when the PIPS processor is writing to a special address 0xff10.

Add a comparator to compare the write address to the constant 0xff10. If the two values are equal and the write enable pin for memory is on, pass a 1 to the enable input on the bottom of the TTY device. Now select a Bit Extender from Logisim’s Wiring category. We’ll use this to truncate the 16-bit data value down to 7 bits, which is what the terminal expects. Connect the \(W_d\) value to the input of the bit extender and connect the extender’s output to the terminal’s data input.

Now you should have a working terminal. The program below should print “Hello” to the terminal, using the raw ASCII encoding of the characters in the message. This program uses assembler constants, which allows you to use named values so you can avoid sprinkling magic numbers throughout your code.

# Print "Hello" to the PIPS terminal
# Charlie Curtsinger
.constant TERMINAL 0xff10
.constant HALT     0xff00

nop # First instruction does not execute
main:
  li $s0, TERMINAL
  li $t0, 0x48   # Load ASCII value for 'H'
  sb $t0, 0($s0) # Print 'H'
  li $t0, 0x65   # Load ASCII value for 'e'
  sb $t0, 0($s0) # Print 'e'
  li $t0, 0x6c   # Load ASCII value for 'l'
  sb $t0, 0($s0) # Print 'l'
  sb $t0, 0($s0) # Print 'l'
  li $t0, 0x6f   # Load ASCII value for 'o'
  sb $t0, 0($s0) # Print 'o'
  li $t0, 0x0a   # Load ASCII value for newline
  sb $t0, 0($s0) # Print newline
  j  HALT        # Stop execution

If you save this program to programs/print_hello.s, you should be able to assemble and run it from the command line:

$ ./asm programs/print_hello.s
$ java -jar /home/curtsinger/shared/logisim.jar -tty tty -load programs/print_hello.hex datapath.circ
Hello
$

If your program fails to produce any output on the command line terminal, you should verify that you have not incorrectly inverted the sense of the halt pin.

Writing an Interesting Program

You now have a datapath that can perform basic arithmetic operations, run loops and conditionals, access memory, and produce output. We can now write interesting programs for this datapath. Your task for this part of the lab is to write a program that computes the first 15 numbers in the Fibonacci sequence and prints them to the terminal. You will need to implement a print_decimal_number procedure that takes an integer and displays it in decimal (base ten) form. You will also need to implement a procedure that computes the Fibonacci sequence using a recursive implementation, which requires that you use the stack. While I expect you can come up with a recursive implementation of the Fibonacci sequence on your own, this C implementation of a number printing procedure may be helpful:

void
print_decimal_number (int n) {
  if (n == 0) {
    putchar ('0');
  } else {
    int digit = n % 10;
    if (n > digit) {
      print_decimal_number (n / 10);
    }
    putchar ('0' + digit);
  }
} // print_decimal_number

You may find it useful to refer to an ASCII table, such as the one at https://ascii.cl.

Notice that this procedure uses both remainder and division; these are not operations that PIPS supports natively, so you will need to implement remainder and quotient as procedures in your solution. Make sure you use the equivalent of MIPS calling conventions in your implementation.

When you are finished, we should be able to run your code with the following commands inside your datapath directory:

$ ./asm programs/fibonacci.s
$ java -jar /home/curtsinger/shared/logisim.jar -tty tty -load programs/fibonacci.hex datapath.circ
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610

Package to Submit

When you are finished, please create an archive of your required datapath directory elements using the following command, starting from inside the datapath directory:

$ cd ..
$ zip datapath-part2.zip datapath/rules.py datapath/microprogram.hex datapath/datapath.circ datapath/programs/fibonacci.s

Note that although the command line beginning with zip may wrap in your browser, you should enter (copy and paste) the entire command (through fibonacci.s) all at once.

This should create a datapath-part2.zip file one directory up from your datapath. Submit this archive to complete the lab.

On Autograding

Rather than using subcircuits, the autograder looks for byte-by-byte matches with your datapath’s terminal output. If your terminal is not implemented correctly, these tests can fail, even for instructions you’ve had manually checked.

You can check the byte-level output yourself by “piping” (using the | character) the output to the xxd command, which displays the output in hexadecimal.

For example,

$ java -jar /home/curtsinger/shared/logisim.jar -tty tty -load programs/print_hello.hex datapath.circ | xxd
00000000: 4865 6c6c 6f0a                           Hello.

From this output (which displays 16 bytes at a time), we can see the first byte is 0x48=72='H', the second byte is 0x65=101='e', and the last byte is 0x0a=10='\n'.

For your fibonacci.s program, here are the bytes we would expect:

$ java -jar /home/curtsinger/shared/logisim.jar -tty tty -load programs/fibonacci.hex datapath.circ | xxd
00000000: 310a 310a 320a 330a 350a 380a 3133 0a32  1.1.2.3.5.8.13.2
00000010: 310a 3334 0a35 350a 3839 0a31 3434 0a32  1.34.55.89.144.2
00000020: 3333 0a33 3737 0a36 3130 0a              33.377.610.

In this case, the first digit is 0x31=49='1', which is followed by 0x0a=10='\n', and so forth.

If your tests are failing in the autograder, you should verify there are not mysterious bytes appearing in your output (which would indicate a likely problem with your datapath or possibly assembler rules).

Copyright © 2018–2025 Charlie Curtsinger and Jerod Weinman

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.