CSE 378 HomeWork 3

Winter 2005

What to Turn In

You'll end up with a file containing your model. Call it peasant.smok. Turnin will be via turnin. Create a text file called peasant.txt. Save your group members' names and answers in this file. Use the command 'turnin -ccse378 peasant.smok peasant.txt' to submit your assignment.

Purpose

• become familiar with the SMOK toolkit.
• become familiar with your partner

Getting Started: Your Team

You should have received mail indicating who your partner is, and how to contact him or her. This assignment is easily small enough that you could each form a solution independently, but you might want to use it instead to work out how/when you'll work as a team.

Getting Started: SMOK Software

Documentation
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.

Lab Machines
SMOK executables are in O:\nt\courses\cse378\smok\SMOK. There are two - SMOK.exe and SMOKTrace.exe. Use the former.

Start menu shortcuts are being set up on the lab machines, but there continue to be problems. The easiest thing to do is to create shortcuts on your desktop, linking to the SMOK.exe file.

Other Machines
Download and install. (There is a download link on the SMOK homepage.)  Shortcuts will be created on your desktop.

Exercise

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. (Hint: most functions are available by right-clicking.) What is the cost of this machine? How many cycles are required to multiply two relatively large numbers (say 0x1234 by 0xABCD)?

There is nothing to turn in for this part.

Assignment

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?

OPTIONAL: Using cvs

You MIGHT want to consider using cvs, a source control system, to help you maintain and exchange copies of files. This page contains some additional information.

Note that this is entirely optional.