Homework 2

22C:122, Fall 1998

Douglas W. Jones
  1. 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
    

  2. 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
    

  3. 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.

  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 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.