MC28 Lab 2: SLIM Assembly Language Programming (Spring 1997)

Due: March 10, 1997

Introduction

For this lab, you will do some SLIM assembly language programming exercises from chapter 11 of our 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 versions of 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, the PC steps, etc.), because the SLIM simulator we will be using provides a visual display of the execution. (The simulator is called SLIME, the SLIM Emulator. It is discussed in the sidebar on pages 386-387.)

You will work on this lab as a member or a two-person (or if need be, three-person) team. Each team is to submit a single jointly-authored lab report.

Mechanics

You will need to put each SLIM program in a separate file. You can use SchematiX for this, but any other text editor (such as jot or emacs) would also work. You then will run SLIME as a separate program, as described below. It has a ``load'' button that pops up a file selection panel, in which you would select the SLIM program you want to load in. You would then use other features of SLIM to run the program and observe its execution.

To actually run SLIME on an SGI, the most easy approach would be to first put the SLIME icon on your desktop, and then whenever you wanted to run it, you could just double click it. To get the icon, you can use the ``Find Icon'' feature of the SGI's ``toolchest'' (the menu usually displayed in the upper left of the screen), and then in the panel that presents type in ~max/MC28/SLIME and drag the resulting icon onto your desktop.

As with most activities involving the mouse, this is easier shown than described. Each lab section will only have a handful of groups in it, so Karl should be able to get you past these hurdles.

Getting acquainted

The next thing to do once you have SLIME running is to try it out on some simple programs from the book, maybe starting with the one that just writes out 314. The key thing to know is that you can not only run the program full speed ahead by pressing the start button, but can also step through it one instruction at a time using the step button. This is very helpful for seeing what is happening. The highlighted line in the instruction panel is always the instruction that is about to be executed, not the one that was just executed.

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). The exercises you should do are as follows:
  1. Exercise 11.2 on page 383.
  2. Exercise 11.4 on page 392. On page 74, the program which performs exponentiation uses power-product: 
    (define power-product
  (lambda (a b e)     ; returns a times b to the e power
    (if (= e 0)
        a
        (power-product (* a b) b (- e 1)))))

    Note that a large result such as (power 3 50) may result in an overflow, that is, a value that differs from the correct one by some multiple of 232. Feel free to ignore the overflows (also in the remaining problems).

  3. Exercise 11.5 on pages 392-393.
  4. Exercise 11.10 on pages 403-404. As you might expect, the recursive power procedure looks like: 
    (define power
  (lambda (base exponent)
    (if (= exponent 0)
        1
        (* base
           (power base (- exponent 1))))))

Postlab

Each group should write a single lab report, authored by all members of the group. As usual, write up a lab report that explains all of what you did to an audience generally knowledgeable about Scheme (and also SLIM for this lab), but ignorant of specifically what you did.

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. You should do this by comparing how many instructions the three versions execute for various exponents. For example, you might test each version with exponents 2, 4, 8, 16, and 32, and report your results in a table. Or you could graph the results. You should also compare the results to specific predictions from your analysis of the programs. That is, for each of the three programs, you should work out a formula in terms of the exponent that specifies exactly how many instructions will be executed, and then check that the numbers you measure match the formula's prediction.

If you have more time

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*23 + 1*22 + 0*21 + 1*20, 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.

Course web site: http://www.gac.edu/~max/courses/S97/MC28/
Instructor: Max Hailperin <max@gac.edu>
Other lab instructor: Karl Knight <karl@gac.edu>