Description
1 Problem 1: Getting Started with the RAMA-2200
In this homework, you will be using the RAMA-2200 ISA to complete a Fibonacci function. Before you begin, you should familiarize yourself with the available instructions, the register conventions and the calling convention of RAMA-2200. Details can be found in the section, Appendix A: RAMA-2200 Instruction Set
You can use the following C code snippet as a guide to implement this function:
int mod(int a, int b) {
int x = a; while (x >= b) {
x = x – b;
}
return x;
}
There is no turn-in for this portion of the assignment, but it is recommended that you attempt it in order to familiarize yourself with the ISA.
2 Problem 2: Fibonacci Number
For this problem, you will be implementing the missing portions of the Fibonacci Number program we have provided for you.
You’ll be finishing a recursive implementation of the Fibonacci Number program that follows the RAMA2200 calling convention. Recursive functions always obtain a return address through the function call and return to the callee using the return address.
You must use the stack pointer ($sp) and frame pointer ($fp) registers as described in the textbook and lecture slides.
Here is the C code for the Fibonacci Number algorithm you have been provided:
int fib(int n) { if (n <= 1) { if (n < 0) {
n = 0;
}
return n;
}
else {
return fib(n-1) + fib(n-2);
}
}
3 Problem 3: Short Answer
Please answer the following question in the file named answers.txt:
- The RAMA-2200 instruction set contains an instruction called goto that is used to go to a certain location within the code, specified by a label. However, this functionality could be emulated using a combination of other instructions available in the ISA. Describe a sequence of other instructions in the RAMA-2200 ISA that you may use to accomplish the functionality of goto.
5 Appendix A: RAMA-2200 Instruction Set Architecture
The RAMA-2200 is a simple, yet capable computer architecture. The RAMA-2200 combines attributes of both ARM and the LC-2200 ISA defined in the Ramachandran & Leahy textbook for CS 2200.
The RAMA-2200 is a word-addressable, 32-bit computer. All addresses refer to words, i.e. the first word (four bytes) in memory occupies address 0x0, the second word, 0x1, etc.
All memory addresses are truncated to 16 bits on access, discarding the 16 most significant bits if the address was stored in a 32-bit register. This provides roughly 64 KB of addressable memory.
5.1 Registers
The RAMA-2200 has 16 general-purpose registers. While there are no hardware-enforced restraints on the uses of these registers, your code is expected to follow the conventions outlined below.
Table 1: Registers and their Uses
| Register Number | Name | Use | Callee Save? |
| 0 | $zero | Always Zero | NA |
| 1 | $at | Assembler/Target Address | NA |
| 2 | $v0 | Return Value | No |
| 3 | $a0 | Argument 1 | No |
| 4 | $a1 | Argument 2 | No |
| 5 | $a2 | Argument 3 | No |
| 6 | $t0 | Temporary Variable | No |
| 7 | $t1 | Temporary Variable | No |
| 8 | $t2 | Temporary Variable | No |
| 9 | $s0 | Saved Register | Yes |
| 10 | $s1 | Saved Register | Yes |
| 11 | $s2 | Saved Register | Yes |
| 12 | $k0 | Reserved for OS and Traps | NA |
| 13 | $sp | Stack Pointer | No |
| 14 | $fp | Frame Pointer | Yes |
| 15 | $ra | Return Address | No |
- Register 0 is always read as zero. Any values written to it are discarded. Note: for the purposes of this project, you must implement the zero register. Regardless of what is written to this register, it should always output zero.
- Register 1 is used to hold the target address of a jump. It may also be used by pseudo-instructions generated by the assembler.
- Register 2 is where you should store any returned value from a subroutine call.
- Registers 3 – 5 are used to store function/subroutine arguments. Note: registers 2 through 8 should be placed on the stack if the caller wants to retain those values. These registers are fair game for the callee (subroutine) to trash.
- Registers 6 – 8 are designated for temporary variables. The caller must save these registers if they want these values to be retained.
- Registers 9 – 11 are saved registers. The caller may assume that these registers are never tampered with by the subroutine. If the subroutine needs these registers, then it should place them on the stack and restore them before they jump back to the caller.
- Register 12 is reserved for handling interrupts. While it should be implemented, it otherwise will not have any special use on this assignment.
- Register 13 is your anchor on the stack. It keeps track of the top of the activation record for a subroutine.
- Register 14 is used to point to the first address on the activation record for the currently executing process.
- Register 15 is used to store the address a subroutine should return to when it is finished executing.
Table 2: RAMA-2200 Instruction Set
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0000 | DR | SR1 | unused | SR2 |
| 0001 | DR | SR1 | unused | SR2 |
| 0010 | DR | SR1 | immval20 | |
| 0011 | DR | BaseR | offset20 | |
| 0100 | SR | BaseR | offset20 | |
| 0101 | 0000 | unused | PCoffset20 | |
| 0110 | RA | AT | unused | |
| 0111 | unused | |||
| 1000 | mode | SR1 | unused | SR2 |
| 1001 | DR | unused | PCoffset20 |
ADD
NAND
ADDI
LW
SW
GOTO
JALR
HALT
SKP
LEA
5.2.1 Conditional Branching
Conditional branching in the RAMA-2200 ISA is provided via two instructions: the SKP (“skip”) instruction and the GOTO (“unconditional branch”) instruction. The SKP instruction compares two registers and skips the immediately following instruction if the comparison evaluates to true. If the action to be conditionally executed is only a single instruction, it can be placed immediately following the SKP instruction. Otherwise a GOTO can be placed following the SKP instruction to branch over to a longer sequence of instructions to be conditionally executed.
5.3 Detailed Instruction Reference
5.3.1 ADD
Assembler Syntax
ADD DR, SR1, SR2
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0000 | DR | SR1 | unused | SR2 |
Operation
DR = SR1 + SR2;
5.3.2 NAND
Assembler Syntax
NAND DR, SR1, SR2
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0001 | DR | SR1 | unused | SR2 |
Operation
DR = ~(SR1 & SR2);
| HINT: A logical NOT can be achieved by performing a NAND with both source operands the same.
For instance, NAND DR, SR1, SR1 …achieves the following logical operation: DR←SR1. |
5.3.3 ADDI
Assembler Syntax
ADDI DR, SR1, immval20
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0010 | DR | SR1 | immval20 |
Operation
DR = SR1 + SEXT(immval20);
.
5.3.4 LW
Assembler Syntax
LW DR, offset20(BaseR)
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0011 | DR | BaseR | offset20 |
Operation
DR = MEM[BaseR + SEXT(offset20)];
5.3.5 SW
SW SR, offset20(BaseR)
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0100 | SR | BaseR | offset20 |
Operation
MEM[BaseR + SEXT(offset20)] = SR;
5.3.6 GOTO
Assembler Syntax
GOTO LABEL
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0101 | 0000 | unused | PCoffset20 |
Operation
PC = PC + SEXT(PCoffset20);
5.3.7 JALR
JALR RA, AT
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0110 | RA | AT | unused |
Operation
RA = PC;
PC = AT;
.
5.3.8 HALT
Assembler Syntax
HALT
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 0111 | unused |
5.3.9 SKP
SKPE SR1, SR2
SKPLT SR1, SR2
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 1000 | mode | SR1 | unused | SR2 |
mode is defined to be 0x0 for SKPE, and 0x1 for SKPLT.
Operation
if (MODE == 0x0) { if (SR1 == SR2) PC = PC + 1;
} else if (MODE == 0x1) { if (SR1 < SR2) PC = PC + 1;
}
5.3.10 LEA
Assembler Syntax
LEA DR, label
Encoding
31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0
| 1001 | DR | unused | PCoffset20 |
Operation
DR = PC + SEXT(PCoffset20);
