Homework 2

22C:122, Fall 1998

Here are a calling sequence, a receiving sequence and a return sequence for parameterless procedure calls on the Minimal Ultimate RISC.

	MACRO CALL proc
             MOVE xra,ra'proc  ; move return address into place
             MOVE x'proc,pc    ; jump to procedure
          xra: 
             WORD ra
          ra:
        ENDMAC

        MACRO ENTRY proc
	  x'proc:
             WORD proc
	  ra'proc:      ; global label on return address
          ra = .        ; local name of return address
             WORD .-.   ; space for return address
          proc:
        ENDMAC

        MACRO RETURN
             MOVE ra,pc ; use local name, global name unknown!
        ENDMAC

Here is a code fragment for the Minimal Ultimate RISC to compute the GCD of two numbers using Euclid's algorithm:

	; the variables of the algorithm
	X:    WORD .-.	; argument to and result of GCD
	Y:    WORD .-.  ; argument to GCD
	temp: WORD .-.  ; temporary

	xGCD: WORD GCD
	GCD:		; branch here to compute GCD of X, Y
	      MOVE X,ac
	      MOVE Y,sub
	      MOVE ac,temp
	      MOVE ccZ,ac     ; see if X = Y
	      MOVE xeq,sub
	      MOVE ac,pc
        ; A   ; 6 instrs, 12 fetches + 4 operands = 16 RAM references

	xeq:  WORD -eq
	eq:
	      MOVE xexit,pc   ; yes, X = Y, exit loop!
        ; B   ; 1 instrs, 2 fetches + 1 operands = 3 RAM references

	      MOVE temp,ac    ; no
	      MOVE ccN,ac     ; see if X-Y < 0 or X < Y
	      MOVE xlt,sub
	      MOVE ac,pc
        ; C   ; 4 instrs, 8 fetches + 2 operands = 10 RAM references

	xlt:  WORD -lt
	lt:
	      MOVE xlta,pc    ; yes, X < Y
        ; D   ; 1 instrs, 2 fetches + 1 operands = 3 RAM references

	      MOVE temp,X     ; no, X > Y
	      MOVE xGCD,pc    ;    iterate!
        ; E   ; 2 instrs, 4 fetches + 3 operands = 7 RAM references

	xlta: WORD lta
	lta:                  ; yes, X < Y
	      MOVE ac,sub     ; clear ac
	      MOVE temp,sub   ; negate X-Y to make Y-X
	      MOVE ac,Y	
	      MOVE xGCD,pc    ;    iterate!
        ; F   ; 4 instrs, 8 fetches + 3 operands = 11 RAM references

	xexit:WORD exit       ; pointer to where to go when done

The above code for Euclid's GCD algorithm requires 18 instructions or 36 words of code, plus 4 constants, 1 auxiliary variable and the 2 parameters, one of which serves to hold the result, for a total of 43 words.
Computing the GCD of 27 and 6 proceeds as follows:
```
   X     27  21  15   9   3   3
   Y      6   6   6   6   6   3
   temp  21  15   9   3   3

   path   a   a   a   a   b   c
```
Path a is followed when X > Y; this involves blocks A C and E for a total of 12 instructions which make a total of 33 RAM references, 24 for fetching the instructions and 9 for referencing operands in RAM.
Path b is followed when X < Y; this involves blocks A C D and F for a total of 15 instructions which make a total of 40 RAM references, 30 for fetching the instructions and 10 for referencing operands in RAM.
Path c is followed when X = Y; this involves blocks A and B for a total of 7 instructions which make a total of 19 RAM references, 14 for fetching the instructions and 5 for referencing operands in RAM.
Taking the sum of these figures, for 4 iterations of path a, plus one each of path b and c, we get a total of 70 instructions executed, using 191 references to RAM, 140 for fetching instructions and 51 for operand references.
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 because it does not make use of many typical computations. Among the typical computations it does not represent are those involving pointers, records and arrays, those involving procedure and function calling, and those involving text manipulation. It also has no floating point and makes no use of multiply or divide operations.