 |
CS2200 Intro to Systems and Networks
Homework 1
Spring 2003 |
This assignment serves as a warmup: an introduction to the LC-2200
processor assembly language and review of finite state machines
(FSMs). There are three problems:
- Intro to LC-2200 assembly
- Assembly programming: Fibonacci program
- Finite state machines
Useful information:
Problem 1: Assembly Programming Warmup
This problem introduces the LC-2200 assembly language and has you
hand- and machine- assemble a few instructions.
The LC is a 32-bit computer with 16 general registers plus a separate
program counter (PC) register. All addresses are word addresses.
Register R0 always reads as zero and writes to it are ignored.
There are four instruction formats (bit 0 is the least-significant
bit):
R-type instructions (add, nand):
bits 31-28: opcode
bits 27-24: reg A
bits 23-20: reg B
bits 19-4: unused (should be all 0s)
bits 3-0: reg DST
I-type instructions (addi, lw, sw, beq):
bits 31-28: opcode
bits 27-24: reg A
bits 23-20: reg B
bits 19-0: OFFSET (a 20-bit, 2s complement number with a range
of -524288 to +524287
J-type instructions (jalr):
bits 31-28: opcode
bits 27-24: reg A
bits 23-20: reg B
bits 19-0: unused (should be all 0s)
O-type instructions (halt, noop):
bits 31-28: opcode
bits 27-0: unused (should be all 0s)
Registers indicated with a '$' sign. The register names in assembly
are according to their use in the assembly convention:
regno name use callee-save
----- ---- ------------------------- -----------
0 $zero always zero (by hardware) n.a.
1 $at reserved for assembler n.a.
2 $v0 return value no
3 $a0 argument or temporary no
4 $a1 argument or temporary no
5 $a2 argument or temporary no
6 $a3 argument or temporary no
7 $a4 argument or temporary no
8 $s0 saved register YES
9 $s1 saved register YES
10 $s2 saved register YES
11 $s3 saved register YES
12 $k0 reserved for OS/traps n.a.
13 $sp stack pointer YES
14 $fp frame pointer YES
15 $ra return address YES
The LC-2200 has supports eight instructions:
-----------------------------------------------------------------
Description of Machine Instructions
-----------------------------------------------------------------
Assembly language Opcode in binary Action
name for instruction (bits 31/30/29/28)
-----------------------------------------------------------------
add (R-type format) 0000 add contents of A with
ex: add $v0, $a0, $a1 contents of B, store results in
DST. Ex: $v0 := $a0 + $a1
nand (R-type format) 0001 nand contents of A with
ex: nand $v0, $a0, $a1 contents of B, store results in
DST. Ex: $v0 := ~($a0 & %a1)
addi (I-type format) 0010 Add OFFSET to the contents of A
ex: addi $v0, $a0, 25 and store the result in B.
Ex: $v0 := $a0 + 25
lw (I-type format) 0011 load B from memory. The memory
ex: lw $v0, 0x42($fp) address is formed by adding
OFFSET to the contents of A.
Ex: $v0 := memory[$fp + 0x42]
sw (I-type format) 0100 store B into memory. The memory
ex: sw $a0, 0x42($fp) address is formed by adding
OFFSET to the contents of A.
Ex: memory[$fp + 0x42] := $a0
beq (I-type format) 0101 compare the contents of A and B.
ex: beq $a0, $a1, done If they are the same, then
branch to the address
PC+1+OFFSET, where PC is the
address of the beq instruction.
Ex: if ($a0 == $a1)
PC := PC+1+OFFSET
*** NOTE ***
For programmer convenience (and
implementor confusion), the
assembler *computes* the OFFSET
value from the number or symbol
given in the instruction and the
assemblers idea of the PC. In the
example, the assembler stores
done-(PC+1) in OFFSET so that
the machine will branch to label
"done" at run time.
jalr (J-type format) 0110 First store PC+1 into B,
ex: jalr $at, $ra where PC is the address of the
jalr instruction. Then branch to
the address now contained in A.
Note that if A is the same as B,
the processor will first store
PC+1 into that register, then end
up branching to PC+1.
Ex: $ra := PC+1; PC := $a0
halt (O-type format) 0111 halt the machine: i.e. do nothing
ex: halt and let the simulator notice that
the machine halted.
noop (pseudo-op) n.a. No operation: does nothing (actually
ex: noop Emits "add $zero, $zero, $zero")
.word (pseudo-op) n.a. fill word with a value.
ex: .word 32 Ex: fill the current location
.word fib with the 32-bit represenation of
the number "32" or the value of
the symbol "fib".
There is an assembler available for the LC-2200. Source code is
available on the web site (assemble.c);
compile it with gcc assemble.c -o assemble. The
assembler understands the instructions and .fill
pseudo-op listed above as well as labels and comments.
Here's an example code fragment illustrating the various features:
!*****************************************************!
! !
! static int data[5] = { 1, 2, 3, 4, 5 }; !
! int limit = 5; !
! int index; !
! !
! for (index = 0; index != limit; index++) !
! data[index] = - data[index]; !
! !
! we'll assign the variables to registers as follows: !
! !
! $a0 = limit !
! $a1 = index !
! $a2 = temporary used in computing !
! !
!*****************************************************!
addi $a0, $zero, 5 ! int limit = 5;
add $a1, $zero, $zero ! for (index = 0; ...
loop: beq $a1, $a0, break ! ... index != limit; ...
lw $a2, data($a1) ! temp = data[index]
nand $a2, $a2, $a2 ! temp = ~temp
addi $a2, $a2, 1 ! temp = temp + 1 (i.e. temp = -data[index])
sw $a2, data($a1) ! data[index] = temp
addi $a1, $a1, 1 ! ... index++) (i.e. end of for loop)
beq $zero, $zero, loop ! branch-always to the top of the loop
break: noop
noop
halt
! Data area:
data: .fill 1 ! data array that we will use
.fill 2
.fill 3
.fill 4
.fill 5
Referring to the example code above, do the following:
A. [10 points] Translate the first four
symbolic assembly instructions to machine code by hand. Assume the
code fragment is loaded at address zero. Note that since the fields
in the machine code are four bits the machine code is particularly
beautiful if written in hexadecimal...
B. [0 points] Enter the code fragment into a file
test.s and assemble it with the assembler:
assemble test.s
The result is written to a file test.lc. The file is
ASCII (human-readable) and contains the translated machine codes as a
sequence of hexadecimal numbers, one per line. Check that the
assembler output matches your hand translations. In particular, check
the OFFSET fields in the beq instructions.
This problem has you use the LC-2200 assembly language to write a
simple program.
A. [10 points] Define a procedure calling
convention for the LC-2200 assembly language and machine model. The
answer should be in the form of a written specification in enough
detail so that one person could write a procedure (or a procedure
call) to be used as part of another person's program. Be sure to
explicitly address the standard issues:
- define how the registers are used
- define how the stack is accessed
- define the mechanics of the call, including:
- what the caller does to initiate a procedure call,
- what the callee does at the beginning of a procedure,
- what the callee does at the end of a procedure to
return to the caller and
- what the caller does to clean up after the return
from a procedure.
Hints: Section 3.6 in the text discusses the MIPS calling convention.
Also, since jalr (irritatingly) doesn't take an immediate
offset, plan on loading a constant for the procedure address with
addi when using jalr.
B. [40 points] Write a program in LC-2200
assembly to compute the nth element in the Fibonacci series given n
using the classic, double-recursive algorithm (below) and your
procedure calling convention. The value of n should be taken from $a0
so that we can compute, e.g., fib(6), like this:
int fib_main(void)
{
int i = 6;
return fib(i);
}
int fib(int i)
{
int ret_val;
if (i == 0)
ret_val = 0;
else if (i == 1)
ret_val = 1;
else
ret_val = fib(i - 1) + fib(i - 2);
return ret_val;
}
Hints: You can find similar problems in Chapter 3 of Patterson and
Hennessy
You may assume that fib_main()'s return address has
been saved in $ra.
The return value should be saved in $v0.
Problem 3: Finite State Machines
The LC-2200 hardware uses a finite state machine (FSM) as a sequencer
to control the datapath. The bulk of Project 1 consists of filling in
the states (the "microcode") of this FSM. The problem asks a few
FSM questions as a warmup.
An FSM with n inputs and m inputs like this:
------------
n | | m
inputs --/->| FSM |--/-> outputs
| |
------------
Is traditionally implemented with ROMs and registers in one of two
ways:
------------ m
| |--------------/----->
| |
| ROM | ---
Mealy n | | k |R| k
machine: inputs --/->| |--/->|E|--/--\
/-->| | |G| |
| ------------ --- |
| k |
\---------/------------------/
------------ --- ------------
Moore n | next | k |R| k | | m
machine: inputs --/->| state |--/->|E|--/->| output |--/->
/-->| ROM | |G| | | ROM |
| ------------ --- | ------------
| k |
\---------/----------------/
A. [10 points] Aside from the physical
difference between the Moore and Mealy machines, what's the
logical difference? I.e. why might you prefer one over the
other?
B. [10 points] Given an FSM with S states,
how many bits in the register (k) are required as a function of S?
C. [10 points] Given n inputs, k register
bits and m outputs, how many bits of ROM storage are required for the
Mealy form? For the Moore form?
D. [10 points] The FSM in project 1 has
these parameters:
- n = 5 inputs: four bits of opcode plus one "Z" bit for testing
when data equal zero.
- m = 17 outputs: control signals to the datapath
- k = 8 state bits, although that we won't need them all.
The Project 1 code actually uses the Mealy form. How many bits of ROM
does that imply? How many bits would be required for the Moore form?
End of CS2200 Spring 2003 Homework 1