SLIM Assembly Language Programming

MCS-178: Introduction to Computer Science II

Introduction

For this project, you will do some SLIM assembly language programming exercises from chapter 11 of Concrete Abstractions. For certain of these exercises, you are asked to gather statistics from the SLIM emulator in order to determine the relative efficiency of various SLIM programs that solve the same problem. You will also have the opportunity to see how the execution of a SLIM program progresses (how the registers and memory change in contents, how the PC steps, etc.), because the SLIM emulator we will be using provides a visual display of the execution.

Mechanics

You will run SLIME as a Java applet directly from your web browser, either by clicking on the link in this project assignment, or by navigating to it from the web site of Concrete Abstractions supporting materials.

SLIME has a text area for entering your program and a load button that loads the program into the instruction memory and pops up additional windows for interacting with the simulated SLIM. To include your program in your project report, and save it for later use, you can use the Copy and Paste features to copy it from the web browser to some editor. Conversely, if you edit your program using a text editor, you can then just Copy it and Paste it into the SLIME program text area in the web browser. That's probably the safer direction, since sometimes web browsers misbehave.

Another alternative if you find web-browser technical difficulties to be frustrating would side-step the web browser entirely. You can download a standalone copy of SLIME as the file SLIME.jar. You can then run this by clicking on the icon for the file you downloaded. If you run SLIME in this way, there is no text area for entering your program. Instead, the Load button opens up a panel in which you choose a text file to load in. You have to have previously saved your program into a file using a text editor.

Programming exercises

Note that the postlab section, below, asks you to analyze some instruction count data, so you will have to gather the data for that in lab as well as doing the programming (and testing and debugging). Specifically, for each exponentiation program, you should at least gather data using several exponents that are powers of two, such as 2, 4, 8, 16, and 32. Note that these are the exponents; the base you use is arbitrary, as it shouldn't effect the number of steps in each computation. You could just as well compute 3², 3⁴, 3⁸, etc. as 2², 2⁴, 2⁸, etc. The exercises you should do are as follows:

Exercise 11.4 on page 351. Here is a Python version of program:
```
def power(b, e):
    a = 1
    # compute a times b to the e power
    while e != 0:
        a = a * b
        e = e - 1
    return a
```
Your program should read in only the base and exponent from the user, and should itself provide the starting value of 1 for a.
Note that a large result such as power(3,32) may result in an overflow, that is, a value that differs from the correct one by some multiple of 2³². Feel free to ignore the overflows in this problem and also in the remaining problems. However, you should definitely check the correctness of your programs using some smaller values for which overflow won't be an issue and where you know the correct answer. For example, if any one of your programs doesn't tell you that 3²=9, you need to fix it.
Exercise 11.5 on pages 351-352. Here is a Python version:
```
def power(b, e):
    a = 1
    # compute a times b to the e power
    while e != 0:
        if e % 2 == 0:
            e = e / 2
            b = b * b
        else:
            a = a * b
            e = e - 1
    return a
```
Notice that this program treats even and odd exponents differently. For your performance data, you'll be using exponents such as 2, 4, and 8, but for testing your program's correctness, you should also include at least one other exponent.
Exercise 11.10 on pages 361. The recursive power procedure in Python is
```
def power(base, exponent):
    if exponent == 0:
        return 1
    else:
        return base * power(base, exponent-1)
```
The instructions for Exercise 11.10 say "Try not to save any more registers to the stack than are needed." I would weaken that a bit: don't save any register that isn't used after being restored. (It is possible to be even a bit more thrifty, but there are good reasons not to, which I can explain if you care.)

Postlab

This report should be scientific in nature, and should deemphasize the process of writing code and focus on the analysis of the running time of each procedure. Your project report should also explain the final products to an audience generally knowledgeable about Python and SLIM, but ignorant of specifically what you did.

Since the coding tasks are simple, the writeup describing the code will be short. In documenting your code, two things help to document assembly code: (1) Add comments describing blocks of a few statements, rather than a comment for each and every statement. (2) Choose your register names carefully, and (if not obvious) add a comment stating what each one is. (3) Add a comment at the top of each version of power describing any pre-conditions for your procedure; does your code work for all integer values of the arguments, or only some?

You are asked to compare the efficiency of the three different assembly language versions of power in exercises 11.4, 11.5, and 11.10. First, by visually counting instructions in each program and thinking about how many times each of those instructions will be executed, predict how many instructions will get executed by each program as a function of the exponent. Then, verify your predictions experimentally. You'll find that for 11.5, it's quite challenging to find a formula for the number of instructions when the exponent is not a power of 2. That's OK; give a formula that only works for powers of 2, and test your program with several such exponents (e.g., 2, 4, 8, 16, and 32). All experimental results should be presented in a single table or one or more graphs.

In your report, for each of the three exponentiation programs, be sure to (a) give a precise formula for the number of steps as a function of the exponent, (b) state your logic for why the formula should be the one you gave (i.e., by looking at your program), and (c) explain how your data matches or fails to match your formula (and, in the latter case, why?).

In presenting numerical data in a table, your presentation is important. If you are comparing the results of two experiments, make sure that you place the results in the same table so the reader can easily compare the numbers. Also, be sure to align the numbers in each column so that corresponding decimal places are directly under one another.

In presenting numerical data in a graph, be sure you choose appropriate axes. If you are predicting logarithmic or exponential running time, use semi-log paper to plot your results. An exponential such as cⁿ when plotted on semi-log paper (with the y-axis logarithmic) looks like a straight line, where the slope of the line depends on the base of the exponent c. When logarithmic data like log_b(n) is plotted with the x-axis on a logarithmic scale, the data appears straight. Lastly, to confirm that your data is a polynomial like n^c, use log-log paper, and see if the data appears on a line; the slope depends on the exponent c.

The gradesheet for the project is available in PDF format. (If you print a copy out, you can staple it to the front of your project report to save paper.)

If you have more time

You are likely to learn more if you do either or both of the following optional activities. (You can do them in either order.) Each can also earn you up to 10 extra credit points.

Additional programming: The following is another recursive exponentiation procedure, more efficient than the one given above for exercise 11.10.

def power(base, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        t = power(base, exponent/2)
        return t * t
    else:
        return base * power(base, exponent-1)

Translate this into SLIM assembly language. As with exercise 11.5, you can make analysis of this program easier by limiting yourself to exponents that are powers of two.

Additional analysis: In the postlab section, we suggested making measurements with exponents of 2, 4, 8, 16, and 32, all of which are powers of two. If you use exponents that aren't powers of two, then the analysis of the program from exercise 11.5 becomes more interesting. Suppose you write a number n in binary; for example 13 would be written as 1101 because it is 1*2³ + 1*2² + 0*2¹ + 1*2⁰, i.e., 8+4+1. Let a(n) be the number of zeros in this binary numeral (without any extra leading zeros tacked on at the left end), so that for example a(13)=1, and let b(n) be the number of ones in the binary numeral, so for example b(13)=3. Can you make a predication regarding how the number of instructions executed by the program from exercise 11.5 can be computed as a function of a(n) and b(n), where n is the exponent? Try experimentally verifying your prediction. The same issues also apply to the additional exponentiation program from the preceding optional activity. If you wrote that program, you can analyze it the same way and check your prediction for it as well.