CSE 378 HomeWork 2

Spring 2002, Due: Wednesday 4/17/02

Purpose

The purpose of this stage of the project is to get familiar with the SMOK toolkit. We'll give you some exercises that will illustrate the capabilities of the toolkit.

Getting Started

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. What is the cost of this machine? 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 savy 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 is easy in a binary representation. Just look at the low order bit. Doubling and halving numbers is easily accomplished by shifting left or right, respectively. What is the cost of this new machine? How many cycles are required to multiply two numbers?

Exercise 2: Return of the Super Simple Machine

In this exercise, you'll implement the (modified) Simple Machine we discussed in class. In case you've forgotten, here's the basic rundown: (Please note: the opcodes have changed slightly from the original definition. We did this not to confuse you, but to make your lives easier, believe it or not.)

Opcode	Operation	Example	Meaning
00100000 (0x20)	ADD	0x20020205	Reg[2] = Reg[2] + Reg[5]
01100000 (0x60)	IMM	0x60020001	Reg[2] = 1
00010001 (0x11)	BNE	0x11230501	If (Reg[5] != Reg[1]) PC = 0x23
10100100 (0xA4)	LOAD	0xA4050400	Reg[5] = Mem[Reg[4]]
00001000 (0x08)	STORE	0x08000203	Mem[Reg[2]] = Reg[3]

ADD adds to register operands and places the result into a register. IMM takes an 8-bit immediate operand from the instruction and places that value into a register. BNE compares two registers, and possibly set the PC to the 8-bit immediate target address in the instruction. LOAD reads memory at an address specified by the contents of a register, and places the result into another register. STORE takes a value (from the register file) and stores it at an address specified by another register.

Registers in the Simple Machine are defined to be 32 bits wide. LOADs/STOREs operate on 32-bit words to/from memory. (Note: this is somewhat different from the machine we talked about in class, that just moved single bytes to/from memory. Again, this change makes your lives easier.) All Simple instructions are encoded as 32-bit values. The high order eight bits (bits 31 through 24) specify the opcode, as shown in the table. Bits 23-16 specify a register number to write (if the instruction does so) OR a target value for the PC if the instruction is a branch. Bits 15-8 specify a register number to read. Bits 7-0 specify either an immediate value to load into a register, or a second register to read.

Your machine will implement a fetch-increment-execute loop: it fetches the instruction specified by the PC, increments the PC to point to the next instruction, and then performs the operation specified by the instruction just fetched.

Implementing the Simple Machine in SMOK

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

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 just deal with a subset (say IMM and ADD) of the ISA. Write a test program to convince yourself that it works. Then add the branch instruction, and so on...
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 (ie. opcode, immediate, etc). Some instructions write a result to the register file, and some do not. Figuring out where and when to write to the stack is a matter of control.
You'll need to implement control. Fortunately it isn't that bad: We've shown you the truth table in class and it's mostly straightforward to implement control lines directly from the opcode.
To represent the instructions and data, use a single memory component connected to an InstructionFetch component and a MemoryInterface.
Standard SMOK register files have 16 registers. This should be more than enough (even though our ISA lets us address many more registers than that!).
Error checking: You do not need to worry about illegal instructions.

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
6001000A
60020010
20030201

Puts the immediate value 0x0A into register 1, the immediate value 0x10 into register 2 and then adds the contents of register 1 and register 2 and places the result into register 3. Double clicking the memory component will allow you to load a file like the above into memory.

Exercise 3: Add an Instruction

Add the STOP instruction to the ISA. STOP should have an opcode of zero, and cause your machine to stop executing. Modify your machine to handle this instruction. (You may just wire a HALT component to the appropriate place.)

Exercise 4: Write a Program

Write a SimpleISA program that multiplies two numbers by repeated addition (as in Exercise 0, above). It should read the first number from memory location 100, the second number from memory location 104, and store the product into memory location 108. When it is finished, it should STOP. We recommend writing the program in "assembly" code, hand-simulating it, and then hand-assembling it into machine code.

Exercise 5: Improve the ISA

Question 1: What's the largest address that your machine can branch to? Not very big. Can you think of a way to encode larger addresses in the provided 8 bits for the target? (HINT: Remember that instructions are always aligned on a "word" address, starting at zero. Does it look like we're wasting a few bits?) The easy way to answer this question is use a strategy similar to that used by the designers of the MIPS architecture for their branch instructions (Check out the book!).

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 person(s) who get the lowest cycle time and cost will receive a special prize!

Turn-In

Please stay tuned.

This is Too Easy

For extra credit: The biggest improvement you can make to the ISA would be to use fewer bits to specify the registers (4 ought to be more than enough, because it lets us address 16 registers). This means that we have plenty of other room in our instructions for other data (such as immediate values for the BNE or IMM instructions). Redefine the instruction set in this manner, and re-implement your machine to execute the new instruction set.

dugan@cs.washington.edu