CSE logo University of Washington Department of Computer Science & Engineering
 CSE 378, Winter 2007
 Machine Organization and Assembly Language Programming
  CSE Home  About Us    Search    Contact Info 

Mechanics
 Home
 Overview
 Academic (Mis)Conduct
 Course wiki
 Mailing list
Schedule
 Lectures and readings
 Lab hours
Assignments
 Homeworks
 Your Grades
Documentation
 Cebollita
 Miscellaneous
Anonymous Feedback
 Submit Feedback
 Read Feedback
   
Printable view

Lab 2: Taking Control - SW

Assigned: 2/7/2007
Due: 6:00PM, 2/14/2007

Description

The first lab focused on the the logic needed for the datapath whilst providing all necessary control signals.  This lab will add support for three new instructions that are essential for subroutines.  Once that logic is present the remainder of the lab will be constructing a control unit that supports all the normal operations. At the end the controller and datapath will be joined together and tested.

Phase 0: Administration

This lab will take place in the same workspace as lab1, but the design will now be lab2. The files for this lab are provided as an archived design. You will need to restore the design, add it to the workspace, and copy the design files from lab1 into the new design. Download the archived design lab2.zip and follow these steps:

  1. Download lab2.zip.
  2. Start Active-HDL and Open the cse378 workspace used in lab1.
  3. Select Design > Restore Design from the menu
  4. Browse to the downloaded lab2.zip file
  5. Set the Restore To: directory to the cse378 directory that contains the folders lab1 and lib378 and click Finish.

At this point the files are all available. Now we need to tell Active-HDL about the new design.

  1. Right-Click the yellow workspace icon name cse378 from the design browser and choose "Add Existing Design to Workspace".
  2. Find and open the file "lab2.adf" in the newly restored lab2 directory.
  3. Set lab2 as the active design
  4. Click and Drag datapath.bde and pcaddresscomputer.v from lab1 to lab2.

Phase 1: Subroutine Operations (JAL, JR, JALR)

Function calls rely on the ability to jump to a location, run a number of instructions and then return to the point after the call. However, with the instructions implemented thus far, it is impossible to store PC or any value explicitly derived from it in a register. Similarly, it's (in general) impossible to jump or branch to a location specified in a register. These requirements are satisfied by three new instructions.

    The jump-register (JR), jump-and-link (JAL), and jump-and-link-register (JALR) instructions remedy this situation. The jump-register instruction (JR) is an unconditional jump like the J instruction from Lab 1. The difference is that the target address for JR comes from a register specified in the instruction. The jump-and-link instruction (JAL) behaves like the simple jump instruction (J), but also stores a return address in register 31 ($ra). This stored value is useful because the JR or Jump-Register instruction sets the PC to the value stored in a register.  The jump-and-link-register instruction (JALR) is the union of JAL and JR, meaning that it transfers control to the address in a specified register, and stores the return address in the register file. However, unlike JAL, JALR allows the programmer to specify the destination register of the return address.

Part A. Using a register as a jump Target (JR,JALR)

These two instructions set the PC to be the value in the register specified by the rs field of the instruction.  This is mainly to allow returns from subroutines, but has additional advantages (see book for more). The PCAddressComputer from Lab 1 has an RS input that was previously unimportant. 

Note: RS refers to the value coming from the output named "read data 1" on the register file.

  • Check that the RS input port of the PCAddressComputer is connected properly.
  • Modify PCAddressComputer Unit so PC = RS when both JR and Jump control signals are set.

Part B. Computing Return Addresses (JAL,JALR)

The return address for these instructions is the address of the next instruction in the program. This address needs to be stored in the register file, so we need some way to present it as the Write input to the register file. The best way to do this is to simply pass the return address through the ALU by adding the address to 0. 

  • Add a multiplexer between the Register file and the rs/immed multiplexer that chooses between the value from the register file and the return address.
  • Add a multiplexer between the Register file and the rt/immed multiplexer that chooses between the value from the register file and a constant (currently 0). 
  • Note: Control signals are added in part D

Part C. Destination register for JAL

The destination register is specified by a field in all previously implemented instructions. The Jump-and-Link (JAL) instruction changes this trend by forcing the destination to be register 31, commonly called the return address register. This behavior is unique to JAL and should not happen the JALR instruction.

  • Create a 5-bit constant containing the value 31
    • add a constant component
    • Right-Click the new constant and select "Properties"
    • Switch to the Parameters tab and set VALUE = 31 and WIDTH = 5
  • Use an m5w_2_1 5-bit mux to set register write destination for the JAL instruction.

Part D. Control for JAL, JR, JALR

The JAL operation requires the choice of register 31 as target and the next instruction address as value to write to the register file.  It also sets the PC to the jump target stored in the instruction.  The JR instruction sets the PC to value in the register specified by the RS field of the instruction. Finally the JALR instruction sets the PC the way JR does, and stores the next instruction the way JAL does, but stores the result to a register specified by the RD field of the instruction.

  • Use control signal JAL to perform JAL and JALR tasks
  • Modify PCAddressComputer Unit to compute proper PC based on JR and Jump signals.

Part E. Testing

Test the updated Datapath.bde with test fixture phase1_tf.v, and macro phase1_runtest.do from the Tests folder. If there are any errors, you may want to see the source code for the test (phase1.s).

Phase 2: Building the Controller

The earlier tasks focused on building the datapath and connecting the proper control signals. Now that work is complete, and the task of generating the control signals must be addressed. 

Fortunately, the MIPS instruction set makes instruction decoding easy by grouping the instructions into 3 separate formats: R-format, I-format, and J-format instructions. These formats describe the meanings of the bits in the instruction and also help to group similar instructions.

R-format instructions are instructions that generally take two operand registers and store the result of the operation in a third register. Exceptions to this rule are instructions like JR. For all R-format instructions, the opcode field (top 6 bits) will always be 0. This is followed by the rs, rt, and rd fields, which are each 5 bits in size. In most R-format instructions, the rs and rt fields indicate which registers are used as operands and the result is stored in the register indicated by the rd field. These fields are followed by the shamt field, which is also 5 bits in size and contains the amount to shift by in certain operations. Finally, there is a 6-bit funct field, which is used to differentiate between the different R-format instructions.

I-format instructions are instructions that generally take one register and an immediate value as operands, then store the result of the operation in the other specified register. Exceptions to this rule include branches and stores, which use the immediate field as an offset to determine the location to branch or store to. In all I-format instructions, the top 6 bits are used for a unique opcode which distinguishes the functions from each other and other types of instructions. This is followed by the rs and rt fields, each of which are 5 bits in size. In general, if a register is involved as a destination, the rt field is used to determine which register is the destination, while the rs field is used as the first operand. The last 16 bits of the instruction are used as an immediate value, which may or may not be sign extended depending on the instruction being executed.

J-format instructions are the used when jumps larger than can be handled by branches are needed. In a J-format instruction, the top 6 bits are used as an opcode to distinguish the instruction from other instructions, and this is followed by a 26-bit address to jump to. When a J-format instruction is executed, the 26-bit address is shifted left by 2, and the top four bits of PC+4 are prepended onto the resulting 28-bit address. Be aware that some jump instructions, like JR, are NOT J-format instructions, but are R-format instructions instead.

Part A. Putting it all in

A skeleton for the controller you need to implement is included in the design. It is highly suggested that you treat each output wire as the result of a boolean expression. The individual variables in the expression should be either tests for a specific instruction, or the result of a different boolean expression.  For an example, assume that there was a control signal STOP that was only asserted during instructions XACT and WAIT. Then, the following Verilog would ensure that STOP was set properly.

wire op_x = (op == XACT);
wire op_w = (op == WAIT);
assign STOP = op_x | op_w;

The advantage of this scheme is that it minimizes repetitious code, which is one key failing of using a large case statement to explicitly set the value of every control signal for every instruction. The ALUControl component is implemented in this style, so feel free to look at its source for a larger example.

Controller Description

The expected behavior of the controller is detailed in a separate page. lab2_controller.html

Instruction List

Be sure to implement all of the following instructions. Take advantage of similarity between groups of instructions

  • Branch Instructions:  BEQ, BNE, BLEZ, BGTZ
  • Jump Instructions: J, JR, JAL, JALR  (note that JR, JALR are R-Format instructions )
  • Shift Instructions: SRL, SLL, SRA, SRLV, SLLV, SRAV
  • Logical Immediates:  XORI, ORI, ANDI
  • Arithmetic Immediates: ADDI, ADDIU, SLTI, SLTIU
  • Arithmetic: ADD, SUB, ADDU, SUBU, SLT, SLTU
  • Logical: AND, OR, XOR, NOR
  • Loads: LW, LH, LB, LHU, LBU
  • Stores: SW, SH, SB
  • Multiplies: MULT, MULTU
  • HI-LO: MTHI, MFHI, MTLO, MFLO  (MULT and MULTU put results in [HI,LO])
  • Misc: LUI - load upper immediate. (see COD:3e 95-96)

Part B. Testing in Isolation

UPDATE: Before you start this part, open up the file phase2_tf.v and find a line with ".func(func));". Change this line to ".Func(func));".

The controller will be tested in isolation to verify that all instructions are implemented properly. Test the controller with the test fixture phase2_tf.v, and macro phase2_runtest.do.  Be aware that the generated waveform may have regions where the signal is green. These correspond to signals that are not required to have a specific value for the current instruction. This does not mean that you may leave these signals unassigned! They must have a value of 1 or 0. If there are any errors, you may want to see the source code for the test (phase2.s). DO NOT continue until all operations pass successfully.

Phase 3: Putting it together

The controller needs to be integrated with the datapath now that both have been successfully tested in isolation.  To make things easier in later labs we will want to add the controller and logic from the datapath into a single block diagram.  This diagram will represent the full single-cycle processor and will only have input ports for things like CLK, Reset, Instruction, and CPUDataIn and output ports for PCOut and CPUDataOut. 

Part A: Combining Control and Datapath

  • Open the block diagram cpu.bde.
  • Copy the datapath logic from datapath.bde into cpu.bde
  • Add the controller component to cpu.bde
  • Connect things up properly

Part B: Testing the integration

Verify that the integration was successful with test fixture phase3_tf.v, and macro phase3_runtest.do. If there are errors, you may want to see the source code for the test (phase3.s).

Turnin

To turn in your lab, complete all phases and use the Design -> Archive Design command in ActiveHDL on the final product to produce a .zip file containing all the essential files. Put this somewhere accessible via attu and use "turnin -c cse378 'your file'" to submit it for grading.


Creative Commons License
This work is licensed under a Creative Commons Attribution-Share Alike 2.5 License.
Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to zahorjan]