Homework 2

22C:122, Fall 1998

Due Wednesday Sept 9, 1998, in class

1. Suggest a calling sequence, receiving sequence and return sequence for parameterless procedure calls on the Minimal Ultimate RISC. This should be packaged as a series of macros named CALL x, ENTRY x and RETURN (where x is the procedure name), so that CALL x will call the procedure x, and the body of x can be bracketed by ENTRY x and RETURN. Use an informal style, based on the SMAL style of macro definition used in the paper.

2. Write a code fragment for the Minimal Ultimate RISC to compute the GCD of two numbers using Euclid's algorithm. The inputs should be the variables X and Y; the algorithm must leave the GCD in X and may leave Y with any value.

   Background: Euclid's GCD algorithm is given here as a recursive function:

   GCD(x,y) = if x = y

   then x
   else GCD( min(X,Y), max(X,Y)-min(X,Y) )

   Note that you will have a far easier time coding this on the Minimal Ultimate RISC if you first convert it to iterative form and then optimize it a fair amount before even imagining using assembly or machine language.

3. Consider Euclid's GCD algorithm used to compute the GCD of 27 and 6 as a benchmark applicaton to be used in evaluating the Minimal Ultimate RISC. Since we only have the instruction set, without an implementation, we cannot evaluate the machine's run time, but we can evaluate the instruction count, program size, and number of memory cycles (instruction fetches, operand loads, operand stores -- excluding moves to or from the ALU) required to execute the program. Compute these figures of merit for this benchmark application using your code from the previous problem. (refer to section 1.6 of the text for the motivation behind this exercise!)

4. A well chosen benchmark will be representative of the class of computation that is of interest to users. Euclid's GCD algorithm applied as above is unlikely to be a good choice as a benchmark! Explain why, listing some of the typical computational structures that it fails to include.