project_2_spec

Project 2 EECS 370 (Fall 2022)

Worth: 30 Points
Assigned: 7:00 PM ET, Thursday, September 22
Part 2C Due: 11:55 PM ET, Thursday, October 6
Part 2Z Due: 11:55 PM ET, Thursday, October 20

0. Starter Code

        lw          0       1       n
        lw          0       2       r
        lw          0       4       Caddr        load combination function address
        jalr        4       7                    call function
        halt
        <Your function instructions here>
n       .fill       7
r       .fill       3
Caddr   .fill       <start_of_function>
        <Your function data here>
Stack   .fill       0

1. Assembly-Language Function to Compute Combination(n,r) (Part 2C)

You will create a recursive function which recursively computes combination(n,r), defined as:

combination(n,0) = 1
combination(n,n) = 1
combination(n,r) = combination(n-1,r) + combination(n-1,r-1);

0 <= r <= n

Here’s a C function to do this; your assembly-language program may follow this logic closely.

int combination(int n, int r)
{
    if (r==0 || n==r) {
        return 1;
    } else {
        return combination(n-1,r) + combination(n-1,r-1);
    }
}

Note that the definition of combination(n,r) is recursive. Your assembly-language function must also use a recursive function calls. That is, your function should call itself twice (to compute combination(n-1,r) and combination(n-1,r-1)) and add the results together. This isn’t the most efficient solution (e.g., n > 9 will take a LONG time), but using recursion will help you understand assembly-language procedure calls and stacks. Your program will be passed inputs n and r in registers 1 and 2 respectively. Your program should store the result in register 3, which acts as the function’s return value. Your program must be reasonably efficient, i.e., it must execute at most 5000 instructions for n=7, r=3 (this is several times slower than a good solution).

Your combination function must follow these guidelines:

  1. Accept n as an argument passed in register 1
  2. Accept r as an argument passed in register 2
  3. Use recursion by building a stack frame for each function called
  4. Return the result in register 3
  5. Use register 7 as the return address
  6. DO NOT use a global register

A global register is one that all recursive calls to a function use. For example, one could simply increment reg3 at every leaf function. While this would compute a correct result, it does not accurately simulate how a recursive function works; instead, we should be utilizing the stack to keep track of our computed values.

One difficult aspect of this program will be allocating variables in the 8 LC-2K registers. To make your job easier, here are the register assignments we used–some are enforced, others are not:

r0  value 0
r1  n input to function - ENFORCED
r2  r input to function - ENFORCED
r3  return value of function - ENFORCED
r4  local variable for function
r5  stack pointer
r6  temporary value (can hold different values at different times, e.g., +1, -1, function address)
r7  return address - ENFORCED

2. Competition (Part 2Z)

There is an optional competition for designing an efficient solution to the combination function. The fastest average across numerous inputs will win a prize. The only rule is as follows:

Note that your solution for 2z does NOT need to be recursive.

Confirmed for F22: Anyone who can beat a total executed instrucitions count of less than 110,000 for \(_{14}C_7\) will receive 5 bonus points to the project. Please note the competition will test more than just \(_{14}C_7\), this bar is just to encourage you to attempt this efficient solution.

Late days may NOT be used to submit to project 2Z functions — we will only accept submissions that come before the deadline.

The leaderboard, which shows the ranking and total executed instructions of the top student submissions, can be found at this link

3. Grading, Auto-Grading, and Formatting

To help you validate your project, your submission will be graded automatically, and the result will be available on the auto grader. You may then continue to work on the project and re-submit. To deter you from using the autograder as a debugger, you will receive feedback from the autograder only for the first THREE SUBMISSIONS for each project part on any given day. All subsequent submissions will be silently graded (this means the submission will be graded, but you will not have access to the grade nor the results of your submission). Your final score will be derived from your overall best submission to the autograder.

The feedback from the autograder will not be very illuminating; it won’t tell you where your problem is or give you the test programs. The purpose of the autograder is to let you know that you should keep working on your project (rather than thinking it’s perfect and ending up with a 0). The best way to debug your program is to generate your own test cases, figure out the correct answers, and compare your program’s output to the correct answer. This is also one of the best ways to learn the concepts in the project.

4. Turning in the Project

You will submit 1 file, combination.as. Your assembly files must be 60 lines or less.

Use autograder.io to submit your files. You should have been added as a student to the class, so you should see EECS 370 listed as a class.

5 Appendix

5.1 Example of subroutine call

Subroutines can be confusing in assembly language. Here is an example of a non-recursive subroutine. The subroutine calculates input * 4.

Here are the key things to notice:

  1. sub4n writes its return value, input * 4 to register 3. This is done on line 7: add 1 1 3

  2. main passes its inputs to the subroutine using r1. This is done on line 1: lw 0 1 input

  3. The function is called using jalr 4 7 on line 2.
    • We first load the address of the function lw 0 4 SubAdr and then use that register to jump to the function.
    • We save the address of the next instruction we should execute in register 7 which acts as our link register.
  4. We are callee saving register 7 and register 1 to the stack.
    • The callee save is done on lines 5-9
    • Callee save preserves the values of register 1 and register 7 when we return to main. This is because we load the correct values before we return on lines 12-16. Notice how add 1 1 1 overwrites our original value in main, however when we return back to main, register 1 will have the original input value.
        lw         0        1      input        r1 = memory[input]
        lw         0        4      SubAdr       prepare to call sub4n. r4=addr(sub4n)
        jalr       4        7                   call sub4n; r7=return address r3=answer
        halt
sub4n   lw          0       6       pos1        r6 = 1
        sw          5       7       Stack       save return address on stack
        add         5       6       5           increment stack pointer
        sw          5       1       Stack       save input on stack
        add         5       6       5           increment stack pointer
        add         1       1       1           compute 2*input
        add         1       1       3           compute 4*input into return value
        lw          0       6       neg1        r6 = -1
        add         5       6       5           decrement stack pointer
        lw          5       1       Stack       recover original input
        add         5       6       5           decrement stack pointer
        lw          5       7       Stack       recover original return address
        jalr        7       4                   return.  r4 is not restored.
input   .fill      10
pos1    .fill       1
neg1    .fill       -1
SubAdr  .fill       sub4n                         contains the address of sub4n
Stack   .fill       0                           definition for the start of the stack (value does not matter)

5.2 The Stack label

On the last line of your assembly file put Stack .fill 0.

In LC-2K, the Stack label is a special label that should be defined at the bottom of an assembly file. Like the example above. This allows the stack to grow without affecting the instructions or data.

As discussed in lecture, programs build up stack frames as they execute. The stack is important for storing data that can’t fit within a machine’s registers, such as call frames and local data. As seen in the below example, this can be accomplished in LC2K by using a label Stack.

Additionally, LC-2K’s use of the Stack label doesn’t reflect how all assembly languages use the stack. ARM, for example, has special instructions such as push and pop that directly interface with the stack, providing a layer of abstraction to assembly programmers. The stack is typically allocated by an operating system that passes the stack pointer to an executing program.

5.3 The jalr instruction

jalr, which means “Jump and Link Register” allows us to create programs with function calls. Consider the following program written in C:

int add(int x, int y){
        return x + y;
}

int main(){
        int value = add(5,2);
        printf("The value is %d", value);
        return 0;
}

If we were to assemble this down into LC-2K, when we are within ‘main’ and call the function ‘add’, we need to change our PC so that the next instruction we execute is within the ‘add’ function. Once we execute ‘return regA + regB’, we need to know what PC we are returning to; luckily, Jalr handles this for us.

Jalr regA regB means:

  1. Set the value of regB to our current PC + 1
  2. set our current PC to the value of register A.

In the example above, when we call the function add, we would first store our PC + 1 into regB (our “return address”) and set our current PC equal to the address where add is defined. Remember, we can load in the address of a label to regA to denote the start of a function. Once we are finished executing ‘add’ we will call Jalr again, but this time, we will ‘jump’ to the PC + 1 we stored in regB in the previous Jalr call; since we saved our return address, we can safely return to where we left off.

5.4 Tips

If you are struggling to write code for this project, draw out a tree diagram which shows all of the recursive calls your program will make.

                                 C(3,2)
                                /     \
                            C(2,2)  C(2,1)
                                    /     \
                                C(1,1)   C(1,0)

Consider what happens at each of the recursive calls: what values does each recursive call need to make progress? What’s special about C(2,1) in the above example?

Debugging can be a bit tricky, but it is doable. First, let’s discuss the steps you’ll need to take to debug the project.

  1. Assemble your combinations.as file with your P1A assembler. If you did not finish this project, don’t worry, you can submit your combination.as file to the autograder and we will produce a correct machine code file.
  2. Simulate the program using your project 1S.

Note: you may need to edit your simulator to account for the ever growing stack (this will allow us to see variables on the stack). To do this, you can either add a constant to your memory size to have it print out more or can alter the logic in your simulator program.

A simple way to do this is to add this code to your SW logic in P1S:

 if(state.numMemory <= calculatedAddress) //if we are trying to store something on the stack
	state.numMemory = calculatedAddress + 1; //expand our 'memorysize' so that printstate shows the stack

This code will increase the amount of information that is output in printstate, which will now show variables on the stack. You will need to change the name for calculatedAddress to match your code.

Remember, the stack begins below our data section, so pay special attention to the values on the stack when debugging.