Lab: Build a Pipelined Datapath

Assigned:

Wednesday, Nov 8, 2017

Due:

Monday, Nov 13, 2017 (by 5pm)

Collaboration:

Work with your assigned partner for this lab. You may use your classmates as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted. If you do not know whether it is acceptable use a specific resource you should ask.

Overview

In this lab, you will add pipelining to your datapath from the previous lab. You are welcome to use your own datapath if you are more comfortable, but I have a completed datapath that includes some useful subcircuits that you may want to start with. I will give you instructions on how to access the completed datapath implementation at the start of class.

Groups

• Kathryn and Greyson
• Reilly and Bazil
• An and Clara
• Ryan and Nick
• John and Jimin
• Mari and Lex
• Andrew and Matt
• Hoang and Faizaan
• Gemma and Prabir
• Zachary and Aditi
• Paps and Rojina
• Nripesh and Dennis

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.

Part B: Connect Pipeline Registers

We will need four pipeline registers: IF/ID, ID/EX, EX/MEM, and MEM/WB. It would be a bit of a hassle to make a separate subcircuit for each, so instead, use the provided pipeline register subcircuits to pass values between stages. The provided subcircuits include all four sizes of registers you should need: 1 bit, 2 bits, 8 bits, and 32 bits.

Use these pipeline registers to separate each stage of the pipeline. Pay close attention to wires that move from the right side of the datapath to the left side; these operations should be associated with instructions as they pass through the pipeline, even though their wires may not cross the entire circuit in the single-cycle implementation.

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. If you do not add nops between the addi instructions, what value do you get at the end of the execution? What is the smallest number of nops you must add for your pipeline to produce the correct answer?

Submit the assembly and machine code programs, both with and without nops.

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: $fib(n) = fib(n-1) + fib(n-2)$, where $fib(0) = 1$ and $fib(1) = 1$. Write and encode an assembly program that computes $fib(n)$ and puts the result in the register $r0. You may assume the value of $n$ is initially in register $r3. When the procedure is finished, send the processor into an infinite loop. Watch out for data and control hazards!

Hint: you may want to write some start-up code that loads a small test value into $r3 before starting your main code.

Hint: our architecture does not have an indirect jump, so there is no way to return from a recursive call. You will have to use an iterative implementation of fib for this architecture.