Build a Datapath, part 2

In this continuation of last week’s lab we will finish implementing most of the PIPS instruction set. You will add support for jump instructions, conditional branches, and memory operations. In addition to supporting the above instruction types, we will use memory-mapped I/O to connect a terminal to your datapath so your programs can actually produce output.

This lab has two due dates. You will need to complete parts A and B by next Tuesday. Please complete the remainder of the lab by the final due date.

Part A: Jumps

We’ll start today’s lab with 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:

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

Once you’ve made these connections you should be able to edit your control signals for the jump opcode (in microprogram.hex) and write translation rules for each of the three instructions above (in rules.py). A few notes:

You can now write a simple program using labels and 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 as well; 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.

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:

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.

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.

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:

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.

Part C: Memory Accesses

The last major piece we’ll add to our datapath in this lab is support for 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 in into the $sp register at the start of your program. To do this, just add li $sp 0xf800 before the body of your program. This sets up your stack at the address 0xf800, and the stack will 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’s safe to statically assign memory locations like this.

Test your datapath by writing an interesting procedure that uses conditional branches and stack operations. 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 we have fewer registers.

Please have the instructor or a mentor sign off on this part before moving on.

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:

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. The instructor or mentor can help you troubleshoot at this point.

Connecting to a terminal

The PIC32s we use in this class have standard MIPS registers, but they also add some additional features; we saw a few of them when we dealt with values like TRISA, LATA, and PORTA. The values are locations in memory, but writes or reads to those locations control special peripheral devices (the pins on the microstick) 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.

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

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_number procedure that takes a number and displays it in decimal form. You will also need to implement a procedure that compute the Fibonacci sequence using a recursive implementation, which requires that you use the stack. While I expect you can come up with an 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, I should be able to run your code with the following commands inside your datapath directory:

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

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

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.

Build a Datapath, part 2

Overview

Part A: Jumps

What went wrong?

Part B: Conditional Branches

Part C: Memory Accesses

Part D: Terminal Output

Adding a `halt` output

Connecting to a terminal

Writing an Interesting Program

Overview

Part A: Jumps

What went wrong?

Part B: Conditional Branches

Part C: Memory Accesses

Part D: Terminal Output

Adding a halt output

Connecting to a terminal

Writing an Interesting Program

Adding a `halt` output