CSE 378 Assignment 4

Spring 2001

Due: Friday 4/27/01

Purpose

UPDATE 4/25/01: This assignment is due Friday before midnight. You should bring your printout of Exercise 1 to class on Friday.

UPDATE 4/24/01: You no longer need to check for jumps to invalid addresses. You can consider doing this as extra credit.

UPDATE 4/22/01: Error codes for out of bounds jumps/branches and invalid instructions have been added. See the Error Checking section.

There will be three assignments on designing the microarchitecture of a processor. For at least two of these, and hopefully the third one as well, you will use the SMOK toolkit to design hardware components for the SLOOP machine. (For our local historians of trivia, the Sloop Tavern is the name of a bar frequented by the authors of the software, John Zahorjan and Ben Dugan. This is probably where they cooked up the idea of this project.)

This is the first of the three assignments. It's purpose is to familiarize you with the SMOK toolkit. The result of this assignment will be a complete single-cycle implementation of the 378 stack machine from assignment 3.

Information on SMOK can be found here . You will quickly discover that this type of programming feels very different from programming in C/C++ or most languages that you're familiar with. So to ease into this different style, we'll give you some exercises that will illustrate the capabilities of the toolkit.

For this assignment (and the next one as well), you should work in teams of two, so that you have a buddy to talk over your design decisions with. Each member of the team should contribute equally to the completion of the assignment.

Getting Started

You should read sections 5.1-5.3 before attempting this assignment
You'll want to start by visiting the SMOK/Sloop homepage . Read the documentation, download the toolkit, and install it on your (or the lab's) PC. Do the tutorial/example on the webpage.

Exercise 0

Suppose we wanted to build a simple machine to multiply two numbers. Our machine might use three registers, called A, B, and Product, respectively. We could use the following algorithm:

while (A != 0) {
  Product = Product + B;
  A = A - 1;
}

You can download an example of a machine that implements this algorithm from here. Download this model, load it into the simulator, and experiment with it. How many cycles are required to multiply two relatively large numbers (say 0x1234 by 0xABCD)?

Exercise 1

Build a better multiplier machine. Your machine should contain three registers, called A, B, and Product, but will use a more savvy algorithm for multiplying numbers. It's called the "Russian Peasant's Algorithm":


while (A != 0) {
  if (A % 2 == 1)              // If A is odd
    Product = Product + B;
  B = B << 1;                  // Multiply B by two
  A = A >> 1;                  // Divide A by two
}

Checking for oddness in hardware is easier than in software; think how you might do this.
Doubling and halving numbers is also easily accomplished by shifting left or right, respectively. How many cycles are required to multiply two numbers?

Exercise 2: Return of the 378 Machine

Remember the HW3 machine? Well, it's back. To simplify this assignment we have removed loads, stores and the divide operation from the model you built before. The remaining instructions are listed in the table below. To remind you what the 378 machine looks like, it is a 32-bit processor with an extremely simple architecture. It has no general purpose registers, and no explicit addressing of memory. Instead, data memory is organized as a stack of 32-bit integers, and all instructions refer to the top of the stack for operands. (There is also a separate memory to hold instructions, addressable only through the 378 PC.) The 378 CPU has an internal register, the SP, to keep track of the top of the stack. The user's program can affect the SP only indirectly, by adding to or removing from the stack.

The table below lists the set of instructions available (as well as some other info to be explained shortly). A user of the 378 machine would write a program using those instructions. (Please note: the opcodes have changed from the original 378 definition.)

Opcode	Operation	Example	Meaning
0000	Stop	0x00000000	Stop the program
0001	Show	0x10000000	Show the stack top
0010	Clear	0x20000000	Clear the stack
0100	Jump	0x40000000	Jump to address in stack top
0101	Bez	0x50000010	Branch if stack top = 0: PC := PC + 16
0110	Bgtz	0x60000004	Branch if stack top > zero: PC := PC + 4
1010	Mult	0xA0000000	Multiply
1000	Add	0x80000000	Add
1001	Sub	0x90000000	Subtract
1111	Push	0xF0000003	Push 3 onto the stack

Stop indicates the end of a program.
Show requests that the integer at the top of the stack be printed.
Clear indicates that the stack should be cleared, that is, set to empty.
Jump jumps to the address at the top of the stack
Bgtz and Bgez compare the value at the top of the stack to zero, branch to the target or fall through and pop the stack
Mult, Add, and Sub replace the top two integers on the stack with the single integer result of the operation specified. For example, if the stack contains (from bottom to top) {1 2 3}, a Sub instruction would result in {1 -1}.
Push adds a new integer contained in the lower 28 bits of the instruction to the stack.

All branches are PC relative, not (PC + 4) relative.

378 instructions are encoded as 32-bit values. The high order four bits (bits 28 through 31) specify the opcode, as shown in the table. In all instructions other than Push, Bez , and Bgtz , the low order 28 bits are ignored. In the Push, Bez , and Bgtz instructions, the low order 28 bits contain a signed integer.

Your machine will implement the instruction execution cycle loop: it fetches the instruction specified by the PC, decodes it and performs its operation, and either increments the PC or changes it to a target address.

Implementing the HW3 Machine in SMOK

Designing the datapath and control is totally up to you, but here are some hints:

Every cycle, your machine should fetch, decode, and execute one instruction from memory. During decoding you'll want to tear apart the incoming instruction into its important fields (i.e., opcode, immediate, etc.). Some instructions write to the stack (Push and the arithmetic operators), while others do not. Figuring out where and when to write to the stack is a matter of control.
You'll need to implement some control lines: you'll want a control line that decides whether or not to write onto the stack and another that selects between an ALU result and an immediate extracted from the instruction.
You'll want to represent an Instruction Memory. To do that you'll use a Memory component and an IF component.
There are a variety of ways to represent a stack. The most general way is to add another interface to your Memory component. The easier way is to use a register file. Your stack pointer will then hold the number of a register that is the "top" of the stack. We recommend the latter approach. Your stack should be large enough to hold up to 8 items.

Running and Testing

In order to test your design, you'll need some test programs. Generating these is easy. Create a text file with this format:


// Comment line
<starting address in decimal>
<word1 in hex>
<word2 in hex>
...
<wordN in hex>

For example:

 

// My first program
0
F0000002
F0000003
F0000004
F0000005
A0000000
80000000
90000000
00000000

pushes four operands onto the stack and then does a Mult, Add, Sub, and finally a Stop. Double clicking the memory component will allow you to load a file like the above into memory.

Implementation

Here are some more hints to help you along the way:

Do not just sit down in front of SMOK and start building.
You'll have a much better experience if you draw your design on paper first. Figure out what units you need, what the control lines should be, what the control functions are.
Be iterative: Don't try to do everything on the first cut. A good starting point is to design a machine that just reads instructions from memory until it sees a Stop. Next add Push; this will mean adding a stack to your system. Next add the arithmetic operators; this will mean adding an ALU to your system, and more control.
To implement Show, use a DebugOutput component.

Error Checking

It is possible for the 378 machine to encounter error conditions. You should deal with stack overflow (pushing more data onto the stack than it can hold) and underflow (performing more operations than there are operand elements on the stack). Your machine should halt and place a value into a status register that indicates: 0 for normal termination, 1 for stack underflow, 2 for stack overflow. Use an error code of 3 to check for branches to out of bound instructions and 4 for invalid innstructions.

Evaluating Your Design

The SMOK system provides you with some important metrics that you should keep in mind. The first is the cycle time of your machine and the second is the "cost", which is a measure of how many transistors your components would consume. The team(s) that get the lowest cycle time and cost will receive a special prize!

Turn-In

Please turn in one copy of the following for your group:

A printout of your machine for exercises 1 and 2 above.
The .sloop file for exercises 1 and 2 above. We only want electronic versions of these and we'll send out more details as the due-date approaches.

If This is Too Easy

Do loads and stores for extra credit.