Lab 10: Pipelining a Simple Datapath

In this lab, you will add pipelining to your datapath from the previous lab. You will use the same architectural design and datapath file from the previous lab as well. I recommend using your datapath from the previous lab, but if you don’t think your datapath works correctly I can share a completed version with you.

Assigned: Tuesday, November 8

Due: Monday, November 14 by 10:30pm

Submitting your work: Submit your completed datapath file by email. Include your assembly and machine code programs from part C in the body of the email.

Groups

  • Eli, Sophie, and Jacob
  • Giang and Charlie
  • Linda and Tanner
  • Ana and Adam H.
  • Bea and Ryan
  • Kamal and Fengyuan
  • Hattie and Matt
  • Maddie and Hamza
  • Jerry and Sara
  • Theo and Adam W.
  • Blake and Devin

Part A: Getting Started

First, we need to identify the five pipeline stages of our datapath. These are:

Instruction Fetch
This stage includes the program counter and instruction memory
Instruction Decode/Register Read
This stage includes both the large splitter that breaks apart instructions and the register file (for reading, not writing).
Execute
This stage includes just the ALU and the multiplexer you used to choose between immediates and register read port 2.
Memory
This stage includes only the data memory element.
Writeback
This stage includes the register file write port and the multiplexor that chooses between ALU output and memory output.

We will need four pipeline registers: IF/ID, ID/EX, EX/MEM, and MEM/WB. Identify all the control and data lines that cross between your pipeline stages and list them. Make note of both the names and bit widths of each connection between stages.

Part B: Build Pipeline Registers

Now that we know what values we need to pass between pipeline stages, we can build subcircuits for each pipeline register. Use the Project, Add Circuit menu item to create a subcircit for each pipeline register. Make sure each pipeline register has an input for every output of the previous stage, and a corresponding output for the next stage. You will need to add a falling-edge register for each input/output pair. Be careful! Logisim defaults to rising edge flip-flops.

You will also need a clock input on each pipeline register. This should be an input pin, which you will connect to the shared datapath clock in your main circuit.

Once you’ve created a pipeline register, you may want to use the Project, Edit Circuit Appearance menu item to make your pipeline register tall enough to handle all the connections you’ve added. You can resize the subcircuit’s rectangle and position inputs and outputs in positions that minimize the number of wire bends required in your main circuit.

As you complete each pipeline register, add it to your main circuit and connect the pipeline together. This is a good time to test your datapath to make sure you haven’t crossed any wires! It’s really difficult to test a completed datapath, so test as you build.

Part C: Writing Pipeline-Friendly Programs

Now that we’ve built a pipelined datapath, we can test it with some useful programs. Of course we don’t have any special circuitry to avoid data and control hazards, so you have to be careful.

Program 1

Encode the simple test program from class on Monday, where we add 1 to a register five times in a row. What is the value in the register after the pipeline has completely cleared? Submit your encoded program along with your answer.

Program 2

Write a program that counts up by powers of two in a loop, storing the result in $r0 each time. Add nop instructions as needed to avoid data and control hazards. Submit your assembly program and an encoded version.

Program 3

Recall that the Fibonacci sequence has a nice recursive definition: , where and . Write and encode an assembly program that iteratively computes the Fibonacci sequence. This program should store the value of in $r0, computing the next value in the sequence on every iteration of the loop. Watch out for data and control hazards!