CSE 378 HomeWork 2

Winter 2003, Due: Wednesday 1/22/03

Teams

You are encouraged, but not required, to work in teams of two. Further, you are encouraged to adopt an extreme programming methodology, pair programming. Rather than partitioning the homework and then working in isolation, work together on all parts of it (where by "together" I mean within a few feet of each other - at the same workstation when working online, and within talking distance when working offline).

Teams should turn in only a single solution, listing the team members.

(It wouldn't be much of a stretch to guess that this model of doing homeworks is a harbinger of things to come.)

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 homepage. Look at the documentation, so you know what's there. Possibly run through 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 SMOK, 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?

ISA Implementation Warm-up

Download this zip file, which contains files ssi-0.smok and ssi-0.smokmem. The former is the SMOK model from class that implements SSI-0, the latter the sample SSI-0 program from lecture expressed in a file that can be loaded by SMOK into the memory component of the SSI-0 model.

Run SMOK and read the model (.smok) file. (The model is set up to load memory with the contents of the .smokmem file.) Single-step through the model and make sure you understand how it works. Edit the .smokmem file to run a different program.

Exercise 2: Implementing Another Variant of the Super Simple Machine

In this exercise, you'll implement another version of the Super Simple Machine, SSI-3. Do not try to simply edit the SSI-0 machine into one that implements SSI-3. Instead, start from scratch, using what you learned from the SSI-0 to your advantage.

SSI-3 is/has:

ADD adds to register operands and places the result into a register. IMM takes an 16-bit immediate operand from the instruction, sign-extends it to 32-bits, and places that value into a register. BNE compares two registers, and possibly sets the PC to the 8-bit immediate target address in the instruction shifted left two bits. (Because all instructions are 4-bytes long, and because the architecture insists that instructions be word aligned, the lowest-order two bits of all instruction addresses must be 00. So, we don't store those two bits 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. All 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 the fetch-increment-execute loop: it fetches the instruction specified by the PC, increments the PC to point to the next instruction, and performs the operation specified by the instruction just fetched. The "steps" happen in parallel in the implementation.

Implementing the Simple Machine in SMOK

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

Running and Testing

In order to test your design, you'll need some test programs. Generating these is easy. Create a text file with name anyoldname.smokmem 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 0x000A into register 1, the immediate value 0x0010 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 an SSI-3 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.

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:

  1. zip your files into a .zip. The archive should contain files whose names clearly indicate one of the following:
  2. Send the .zip in a mail message to me (zahorjan@cs) with subject "378 hw3 submission".  Include the names of the members of your team in the body of the mail message.