CSE 378 Homework #5: Pipelining

Due: Monday, 3/1/2003

Assignment Goals

You'll convert your machine from HW4 to a pipelined implementation. The result should be a much faster machine, measured in terms of the number of (simulated) cycles required to execute most programs.

Note that there is no change to the ISA in this assignment. Exactly the same set of programs that ran on your final machine for HW4 should run on this pipelined machine.

Overview

Implementing pipelining requires a number of changes:
• Add pipeline registers to the data path between each pair of successive stages. Much of the output of your control is captured in a pipeline register, and passed from one stage to another, rather than immediately used. As well, the outputs of each stage are (typically) placed in the pipeline registers (and passed down the line, until needed).
• You must add forwarding units to deal with data hazards.
• You must introduce a bubble to deal with the lw hazard.
• You must be able to flush part of the pipeline on a mispredicted branch. Additionally, you may have to change the datapath slightly to allow branches to be resolved as early as possible (within reason -- remember, your goal is to run as fast as possible).
• You must deal with exceptions correctly.

Pipeline Registers

The easiest way to deal with pipeline registers in SMOK is to use ControlRegisters. Each ControlRegister contains an essentially arbitrary number of individual registers. It is convenient in SMOK to make all pipeline registers structurally identical, even though what is absolutely required varies from one stage to the next. If you configure the first (most upstream) ControlRegister, you can create the others successively. If you connect one ControlRegister to another, an uninitialized downstream register will automatically create inside itself as many registers as the upstream one has, and will connect the individual registers in a directly corresponding way. You will have to modify those default connections somewhat, but by and large the defaults are useful.

You may find it convenient to use a BitCombine component to aggregate all control (PLA) outputs into a single word, which can then be stored in a single ConttrolRegister register. (Note that because the datapath may need to be changed, the PLA's may need to be changed as well.) You can extract the control bits you need from that register at each stage.

Data Hazards: Forwarding

You will need two forwarding units. The book shows only one, but that's because it assumes the register file is capable of performing forwarding itself. The SMOK register does not (and cannot be made to) forward.

You can build these forwarding units either out of SMOK's standard components, or you can create new component types using SMOK's plug-in facility. The advantages of the latter approach are (a) fewer components total, so less screen cluttter, and (b) most of the work is implementing software, not connecting logic components. The potential disadvantages are (a) the infrastructure for creating plug-ins requires that you code in C++ (although you need hardly understand the language to use it for this purpose -- just think of it as Java), and (b) the infrastructure requires use of Visual Studio. More on this later.

Data Hazards: LW

You will need to provide a hazard detection unit that looks for the load hazard. Again, you can build this either in logic or else create a new component type in software using the plug-in facility.

Either way, you will sometimes have to stall the pipeline. The SMOK ControlRegisters have inputs designed for that purpose.

Branch Hazards

Because the result of a branch is not known until the second stage, at least, you must fetch instructions that succeed it "speculatively." For this assignment, you should just guess "branch not taken" when fetching the succeeding instruction. HW6 will give you an opportunity to try better branch prediction techniques.

When you detect a mis-predicted branch, you have to flush the pipeline. SMOK ControlRegisters have an input that helps with that. You can build the branch hazard detection unit either out of logic or as a new (plug-in) component type.

Exceptions

Your pipelined machine should raise the same set of exceptions as your HW4 machine, and should take the same actions as that machine (since those actions are part of the ISA). However, pipelining introduces a complication -- you cannot act on the exception until all instructions ahead of the one that generated it have completed, that is, passed out of the pipeline. (If you were to act immediately, it would appear to software like the OS that an instruction before the one generating the exception had not executed, which is impossible according to the ISA.)

To achieve this, when you detect an exception you should indicate that in the pipeline register. That indication passes down the pipeline until it reaches the writeback stage, at which time you actually throw the exception. Be careful to make sure that neither the offending instruction nor any that come after it in the pipeline update any machine state -- they shouldn't write registers or memory.

Building Plug-in Components

In the SMOK install directory (e.g., C:/Program Files/University of Washington CSE/SMOK, or O:\cse\courses\cse378\04wi\SMOK in the labs) you'll find a directory named UserDefinedComponentExamples. Copy it somewhere.

Enter subdirectory VS7Project (in your copy) and double-click on the .vcproj file. That will bring up the sample project in Visual Studio. (After you have run Visual Studio once, you should find a .sln file in that directory. You should lauch thereafter by double-clicking on the .sln file.)

That project contains code to build three different plug-in component types, MAX, Latched Max, and Watchpoint. You can have a look at those components in a SMOK model: start SMOK, right-click / Add Component. Near the bottom you will see a menu item ExampleUserPackage. Its submenu allows you to insert one or more of each of the three example plug-in component types. (If you don't see that menu item, look a little further down this section for information about setting SMOK's path variables.)

The implementations for the example component types are in file ComponentExample.cpp. The best thing to do to build new component types is to modify that file. This page provides more information about the how to do that.

When you build your project it will create a .smokdll file in the Executables directory. That is the executable code required for your new plug-ins. Two problems may arise. First, the package name for your components is taken from the name of the .smokdll file, and so will conflict with the sample package in the SMOK distribution. You can rename your .smokdll to resolve that. (You can also modify the project settings in Visual Studio so that it writes the .smokdll with a different name.) Second, SMOK can find your .smokdll only if the directory it is in is on the appropriate SMOK path "environment variable." (Environment variables in SMOK are actually kept in the registry.) To add your directory to the path, start SMOK and under the Edit menu you will find an Edit SMOK Env Vars. That brings up a dialog box that lets you change the path variables. (You may have to quit and restart SMOK for a change to take effect.)

Testing

It would be wise to test using short sequences of instructions (written by you, in assembler) before moving on to larger applications. A correctly working machine should run the OS, though.

What to Hand In

• Your SMOK machine and associated PLA files.
• An indication of the number of cycles required to run quicksort.exe as a standalone program (i.e., linked with iolib.o, so not part of an image file containing the OS) on both your HW4 machine and your completed pipelined machine.
• If you modified any "system code" (e.g., iolib.c), and those modifications are required for programs to run on your machine, we'll need those modified files as well.