CS2200 Homework 2 Solved

In this problem, you will be introduced to the 16 bit LC (Little Computer) 2200 assembly language. You will learn the syntax and semantics that underlie each of the supported operations. Although our instruction set is not as extensive as MIPS (Microprocessor without Interlocked Pipeline Stages) or x86, it is still able to solve a multitude of problems. In a LC-2200 computer, the word size is two bytes (16 bits), and there are 16 registers. We restrict memory to be addressable by words.

Register Conventions

Although the registers are for general-purpose use, we shall place restrictions on their use for the sake of convention and all that is good on this earth. Here is a table of their names and uses:

Table 1: Registers and their Uses

Register 0 This register is always read as zero. Any values written to it are discarded.
Register 1 is a general purpose register, you should not use it because the assembler will use it in

processing pseudo-instructions.
Register 2 is where you should store any returned value from a subroutine call. Registers 3 to 5 are used to pass arguments into subroutines.

Registers 6 to 8 are used to store temporary values. Note that 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 (the subroutine) to trash.

Registers 9 to 11 are the saved registers. The caller may assume that these registers are never tam- pered with by the subroutine. If the subroutine needs these registers, then it should palce them on the stack and restore them before they jump back to the caller’s code.

HW 2 Question 4 CS 2200 – Systems and Networks Fall 2017

Register 12 is used to handle interrupts (something we’ll get to in a few weeks).
Register 13 is your anchor on the stack. It keeps track of the top of the activation record for some

subroutine.

Register 14 is used to point to the first address on the activation record for the currently executing process. You do not need to worry about using this register.

Register 15 is used to store the address a subroutine should return to when it is finished executing. It is only supposed to be used by the JALR (Jump And Link Register) command.

Instruction Formats

There are four types of instructions: R-Type (Register Type), I-Type (Immediate value Type), J-Type (Jump Type), and S-Type (Special Type).

Here is the instruction format for R-Type instructions (ADD, NAND):

Here is the instruction format for I-Type instructions (ADDI, LW, SW, BEQ):

Here is the instruction format for J-Type instructions (JALR):

Here is the instruction format for S-Type instructions (HALT):

Symbolic instructions follow the same layout. That is, the order of the registers and offset fields align with the order given in the instruction format, ie. instructions in assembly are written as:
instruction RX, RY, RZ or
instruction RX, [optional offset](RY).

HW 2 Question 4 CS 2200 – Systems and Networks Fall 2017

Table 2: Assembly Language Instruction Descriptions

LC 2200 provides a number of pseudo-instructions.
Table 3: Assembly Language Pseudo-Instructions

Play around with the simulator. Try writing some simple programs to copy values from one register to another or to load/store values from memory. You should get familiar with the syntax for the assembler.

When you extract the archive, you will have access to an assembler (assembler.py), a python file that defines the ISA for the assembler (lc2200hw1-isa.py), and a simulator (lc2200hw1-sim.py). The assembler and simulator run on any version of Python 2.6+. Here is the suggested workflow for writing and running your assembly programs on the simulator:

1. Edit and save your assembly file with your favorite text editor.
2. Assemble your code via the assembler. The command below will generate a file called myFile.bin by using a myFile.s assembly file and the ISA for this homework:

        python assembler.py -i lc2200_16-isa --sym myFile.s
   

3. You can run your .bin file with the simulator by typing python lc2200_16-sim.py myFile.bin. Some useful commands are ‘r’ for run, ‘q’ for quit, ‘break [line # or label]’, and ‘help’.

Exercise: Fibonacci Test Program

In this problem, you have to use the LC 2200 assembly language to write a simple program.

Write a function in LC-2200 to compute fibonacci(num). Your implementation must be recursive and follow the LC-2200 calling convention introduced in lecture. For a review of the calling convention, see the “LC-2200 Calling Convention” slides under Resources on T-Square.

You may find the following pseudocode helpful:

fibonacci(n) = fibonacci(n − 1) + fibonacci(n − 2) fibonacci(0) = 0 and fibonacci(1) = 1

Purely iterative implementations will receive no credit. Points will be deducted for not following the calling convention correctly.

NOTE: Your function should work for any n ≥ 0. You do not have to handle detecting integer overflow. When your program exits, the result should be in the $v0 register.

Hints

• We recommend starting with a solution in a higher level language such as C, and then moving to assembly.
• Comment your code. Assembly is hard to read, and comments aid in debugging while providing clarity.
• When you make a recursive call, you will have to overwrite the current arguments stored in the $a0-$a2 registers. If you need to access those again, you can either (1) treat them like $t registers and push them to the stack, or (2) copy the arguments into local variables or $s registers.

  Feel free to ask us questions in our office hours, on Piazza, or in the weekly recitation. Make sure that fib.s is in a UNIX-readble format (no DOS/Windows nonsense).

  Deliverables

  Turn in the following files to T-Square:
  • fib.s, which has your assembly code.

  Be sure to put your name in a comment at the top of the file.

  The TAs should be able to type python assembler.py -i lc2200_16-isa –sym fib.s and then lc2200_16-sim.py fib.bin to run your code. If you cannot do this with your submission, then you have done something wrong.