CSE 378 - Winter 2002
Machine Organization and Assembly Language Programming
Homework 5: SMOK MIPS Design and an Introduction to SMOK
Due Wednesday, February 20
Purpose:
This assignment is
where the pieces of the CPU puzzle come together for you: instructions,
data path, and control. You will learn how to design the microarchitecture of a
real processor.
It is also an introduction to the SMOK design tool. SMOK allows you to
design and test architectures at a component abstraction level,
i.e., at the register transfer level. Finally this assignment requires you to
write a procedure in MIPS assembly (and either hand assemble it or use Spim to
assemble it to MIPS machine code*), so that
learning the mechanics of procedure
stack frames is also a component of this assignment.
For this assignment, you should work in teams of two and hand in one
homework for the two of you. Start now to find a partner. Both of you should
work on both parts, so that you both get experience in designing a
microarchitecture and working in the SMOK environment. The next assignment is
also in teams, but you'll need to partner up with different person for that
one.
Tasks:
Task 1: You are to build a singlecycle, smallscale MIPS
microprocessor.
This will be just like a commercial MIPS microprocessor (the R2000 vintage),
except that you will implement only a handful of instructions, and you
won't have to pipeline the machine (although you may think about how to do
that, since this will be Homework #6). For this assigment the
execution of each instruction will happen in one long clock cycle.
Task 2: Write a recursive function that calculates the n'th
Fibonacci
number. This function Fibonacci(i) will return an integer. You are to
write this function first in MIPS assembly language, and then you are to
hand assemble your code into binary form. You will then execute
this code
on the machine you build in Task 1. Because of this you will have to write
this function using only the set of instructions you actually implement in
Task 1, but these should be enough.
The Details:
- We are going to use the latest version of SMOK, which executes on
Windows only.
This version can be downloaded from
"http://www.cs.washington.edu/homes/zahorjan/homepage/Tools/SMOK/".
Please use the latest version since it has been updated specifically for
our class.
- The format of the instructions for your machine follow the real MIPS
encoding format (Rtype, Itype and Jtype). In addition, just like the
real MIPS architecture, your machine will have 32 integer registers, treat
register zero as 0*
, register 31 as ra, and other register conventions.
- The absolute reference for any details with this assignment is the real
MIPS documentation, and any other documentation on the real MIPS
microprocessor (unless otherwise explicitly modified in this handout, or
we tell you otherwise). Now having said this, we are going to make a
modification to the memory layout of the process the MIPS processor you
build executes. This is only a small hack to make things easier for the
SMOK tool and yourselves, but it should be easy to see how to modify
things to work like the real microprocessor. The hack is as follows:
- The real MIPS processor has a protected and privileged operating mode.
This is to support process level protection mechanisms that are
conventional on modern operating systems. For this assignment there is no
operating system, and no protection modes.
- While your microprocessor operates with 32 bit addresses, in order to not
make SMOK explode, you are going to work with only a 256 word (1024 byte)
memory.
- By convention, a process starts at 0x04000000. However, your initial PC
should be set to 0x00000000, i.e., your code should start at address 0.
- By convention, a process stack pointer is set to 0x7ffxxxxx (near the 2
gigabyte boundary). You should set your stack pointer at 1024 bytes (256
words), i.e. just at the end of the memory in the machine.
- By convention, a process stores static and dynamic data starting at
0x10000000. If you need static and dynamic data, you should start storing them
at the 512 byte (128 word) boundary.
- The real MIPS processor contains delay slots
behind branches and delays on load instructions (to account for additional
latencies in executing these instructions). Your processor will operate in a
single cycle, and so there will
be no delay slots.
- You should understand the following code, and
place it at address 0 (load the .smokmem file into your memory unit):
0x00000000: addiu $sp, $0, 1024 # effectively a li $sp, 1024
0x00000004: addiu $sp, $sp, -4 # effectively a sub $sp, $sp, 4
0x00000008: addiu $a0, $0, 10 # effectively a li $a0, 10, set subroutine arg to 10
0x0000000C: jal fibonacci # begin your subroutine
0x00000010: addiu $sp, $sp, 4 #restore stack
0x00000014: beq $0, $0, -4 # effectively a hold
0x00000018: place your fibonacci program here
This code sets up the stack pointer, and then makes a procedure call into
the fibonacci procedure that you are to write. After returning from
fibonacci it removes the stack frame and halts the machine by having a
branch instruction jump to itself*.
The smokmem file is here.
- Your implementation should support the following instructions:
- Arithmetic:
- ADDU, ADDIU, SUBU, SLTI, SLT
- Load/Store:
- LW, SW
- Control:
- JAL, JR, BEQ, BNE
- Fibonacci numbers are a rather famous sequence of numbers that go
something like this:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
The basic pattern is F(n) = F(n1) + F(n2), with F(0)=0 and F(1)=1. So
your function should be like this:
def fibonacci(n):
if n==0:
return 0
if n<=2:
return 1
return fibonacci(n-1)+fibonacci(n-2)
Note that the function is recursive, so you will need to be careful about
how you handle registers. Follow MIPS conventions. Remember to use only
the instructions your machine supports. They should be more than enough.
Do not worry about improper inputs.
Please do not be too fancy in how you implement this function. We have to
grade it!
- It will behoove both of you to work on all
parts of this assignment. In other words, you can expect questions on the
midterm about designing datapath and control.
- Write a short report (one page is plenty) describing:
- how you planned and designed your machine, especially
mentioning anything you thought was tricky or that you found a
partiticularly nice solution for;
- how you tested your machine, and how you debugged it;
- what you learned, and what you had trouble with;
- describe your fibonacci algorithm. How many cycles does it take?
- the distribution of work between partners.
- Turn in your code online, using
this form,
and turn in your written report in class. Please submit as only one
person--there is no need for you and your partner to submit code (or
written reports) separately. Just make sure to indicate both partners'
information on the turnin, so you will both get a grade. Both written and
code parts are due by class on 2/20. I suggest you finish the code
part early, and leave time to describe it in the written report.
Grading
You will be graded on:
- functionality of the fibonacci code on your machine
- correctness of your machine
- design of your machine (is it understandable, reasonably fast?)
- your written report
Hints
- Chapter 5 gives an almost complete machine design in gory detail. It
is a good starting point, but there are a few differences to note: The
given machine has two memories, because they can't do two memory operations
in one cycle. With SMOK, you can have one memory unit, and use two
interfaces (one for fetching instructions, the other for loading and storing
data). Either implementation is acceptable.
- SMOK's ALU has different opcodes than the one described in the book. That
being said, you should not feel bound to the design in chapter 5. If there is
something else that makes sense to you, feel free to go that route as long
as it is functional.
- It will probably take over 1000 cycles of your machine to compute
fibonacci(10), so you might want to start with a smaller input.
- All operations you're implementing that use the immediate field do
sign extension.
In reality, although dealing with unsigned numbers, ADDIU and
other math operators indeed do sign extension, but logical operators (ORI)
do not.
- In MIPS, register 0 is hardwired to 0. For this project it
acceptable to simply have all registers initialized to zero, and never
write anything to register zero. Alternatively, you can devise a
scheme to keep register 0 at 0.
- To know SMOK is to love SMOK. But, just like Al Capone when he said
the secret to winning elections is to "vote early and often", the secret
to loving SMOK is to "save early and often". I have also seen SMOK
develop odd behavior, which reinitializing the machine did not fix, but
quitting SMOK and reloading the file did. Keep in mind that SMOK is a work in
progress.
- Unlike SPIM, which is used by universities across the country and is
therefore pretty much free of bugs, SMOK is a homebrew design. So if you find
a reproducable error, make note of it, and let others know as well.
Additionally, versions of SMOK may change during this assignment. This
should not introduce any incompatibilities, but you may find that later
versions have new features that help you.
- If you use SPIM to assemble your code to binary, note that (in the
default configuration) it doesnt calculate branch offsets from PC+4, and
that jump addresses will be very different
- To facilitate testing, you may add a 'halt' component that will
trigger when the self-looping branch instruction is detected.
- The component reference page is useful:
www.cs.washington.edu/homes/zahorjan/homepage/Tools/SMOK/ComponentRef/index.htm
- You will want to understand what a container/control is and how to
use one. It will make your design considerably easier to navigate.