Project 4: SLIM Assembly Language Programming

---

Started: Tuesday 3/15; Due: Friday 3/25, by the beginning of class

Overview

For this project, you will do some SLIM assembly language programming exercises from chapter 11 of the Concrete Abstractions book. For certain of these exercises, you are asked to gather statistics from the SLIM simulator 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 simulator we will be using provides a visual display of the execution.

You should work on this project individually. However, feel free to ask your neighbor for help when you are getting started.

Mechanics

You will run SLIME as a Java applet directly from your web browser. 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.

The SLIME web page also contains links to several example programs from the book. You can Copy and Paste any of these programs into SLIME's text area in order to try it out.

As with most activities involving the mouse, this is easier shown than described. Once in project, your lab instructor (or a neighbor) will help to get you past these hurdles.

Getting acquainted

Load in each of the example programs write-larger and count-to-ten and then try running them. In addition to running them at full speed with Start, be sure to Step through them in order to see how the registers change. Before doing exercise 2 below, you should also load, run, and understand iterative-factorial from the SLIME page.

Specific tasks

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 the various exponentiation programs, you should at least gather data using several exponents that are powers of two, such as 2, 4, 8, 16, and 32. The exercises you should do are as follows:

1. (Warm up, hand in) Exercise 11.2 on page 345. The code for this warm-up exercise should be included as an addendum to your project report, since it's obviously tangential to the rest of the assignment.

2. Exercise 11.4 on page 351. The program in section 3.2 which performs exponentiation using a Scheme procedure called power-product. Instead of learning Scheme for this lab, you should use the following Java method as a model for your SLIM code:

       public static double power(double b, int e) {
           double power = 1;
           while (e > 0) {
               power = power * b;
               e = e - 1;
           }
           return power;
       }
   							

   Your slim program should read in the base and exponent from the user, compute the power, and write out the answer.
   
   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.

3. Exercise 11.5 on pages 351-352. Instead of the Scheme code given there, use the following Java method as a model for your SLIM code:

       public static double power(double b, int e) {
           double power = 1;
           while (e > 0) {
               if ((e % 2) == 0) {
                   b = b * b;
                   e = e / 2;
               } else {
                   power = power * b;
                   e = e - 1;
               }
           }
           return power;
       }
   							

4. Exercise 11.10 on pages 361. The Java version of the recursive power procedure you should use as a model for your SLIM code is:

       public static double power(double b, int e) {
           if (e == 0) {
               return 1;
           } else {
               return b * power(b, e - 1);
           }
       }
   							

Your report

In addition to the programming you are asked to do, you will need to write a report analyzing the instruction count data for your procedures. 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 Java and SLIM, but ignorant of specifically what you did.

Since the coding tasks are simple, the writeup describing the code will be short. On the other hand, documenting your code is important. Here are three things you can do to help document assembly code: (1) Adding comments describing blocks of a few statements, rather than writing a comment for each and every statement. (2) Choosing your register names carefully, and (if not obvious) adding a comment stating what each one is. (3) Adding a comment at the top of each version of power describing any pre-conditions for your procedure, e.g., 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, looking at each program, 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.

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.

Extra credit

You can earn 5 extra credit points by implementing the recursive version of the choose method:

    public static int choose(int n, int k) {
        if (k < 0 || k > n) {
            return 0;
        } else if (k == 0 || k == n) {
            return 1;
        } else {
            return choose(n-1, k-1) + choose(n-1, k);
        }
    }
					

You do not need to do any analysis for this procedure, only write correct and reasonably documented code for it in Slim.

Gradesheet

We will use this gradesheet when grading your lab.

Submission

You should hand in a hard-copy of your written report described above, which includes the SLIM code you wrote in an appendix. Additionally, you should submit via moodle an electronic copy of your SLIM procedures, so that we can run them if needed to. The write-up needn't be fancy (in a word-processing sense), but it should contain the materials described above. You should also include appropriate graphs using semi-log papers, where you can fill in the data points by hand.

If you do the extra credit, put the code for it in your appendix and include it in your moodle submission.