MC28 Lab 2: SLIM Assembly Language Programming (Fall 1996)

Due: October 16, 1996

Introduction

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.

SLIME

allocate-registers a, b, one, factorial-product, end
   
li a, 1
read b
li one, 1
li factorial-product, factorial-product-label
li end, end-label

factorial-product-label:
;; computes a * b! into a and then jumps to end
;;  provided that b is a non-negative integer;
;;  assumes that the register named one contains 1 and
;;  the factorial-product register contains this address;
;;  may also change the b register's contents
jeqz b, end  ; if b = 0, a * b! is already in a

mul a, a, b   ; otherwise, we can put a * b into a
sub b, b, one ; and b - 1 into b, and start the
j factorial-product          ; iteration over

end-label:
write a
halt

The differences illustrated in the above example are as follows:

• There are no parentheses, no quote mark, no preprocess-or-assemble or define around the outside.
• The operands in each instruction (and names in the allocate-registers line) can be separated by commas as shown above, though that isn't required.
• The labels need to be followed by colons, though only where they are being used to label an instruction, not where they appear as an operand in an li instruction.

You will need to put each SLIM program in a separate file. You can use SchematiX for this, but any other text editor 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. The lab section will only have three groups in it, so David should be able to get you past these hurdles.

Getting acquainted

Programming exercises

1. Exercise 11.2 on page 362.
2. Exercise 11.4 on page 370. On page 73, 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)))))
   

3. Exercise 11.5 on page 370. Note that a large result such as (power 3 50) may result in an overflow. Feel free to ignore the overflows when counting instructions, but briefly discuss the effects (if any) this might have on your conclusions.
4. Exercise 11.9 on page 376.
5. Exercise 11.10 on page 381. 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

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.

Note that the Scheme code from which the three versions are written generate processes that are linearly iterative (11.4), logarithmically iterative (11.5), and linearly recursive (11.10). Do your results match these expectations? In the case of the linear versions, you might expect the number of instructions to be a linear function of the exponent n (that is, expressible as An + B for some values of A and B). Can you find such a pair of A and B for each of the iterative versions? How do the values of A and B for one version compare with the values of A and B for the other version? How could you check that the process generated by your program from exercise 11.5 has logarithmic growth?

If you have more time