Exam 3 Solutions

22C:18, Fall 1996

Mean   = 14              X     X   X
Median = 13.9            X     X   X
                         X X   X   X
                         X X   X X X X X     X
                     X X X X   X X X X X X   X X
 __________X_____X___X_X_X_X_X_X_X_X_X_X_X___X_X________
    0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24
  1. Number Representations: 4310 is:

    1. 333416 or 00110011001101002 as an ASCII string packed into a 16 bit halfword on a Hawk machine. Half of the answers transposed the bytes of the the halfword, one in 4 had wrong answers.

    2. 010000112 as a BCD number with the most significant digit first. Few had any problem with this.

    3. 101011 as a binary number. Almost everyone did well on this.

    4. 2B as an 8-bit two's complement binary number shown in hexadecimal. One in 5 had problems here, with many who 2's complemented the value to get D5.

    5. AC16 as an 8-bit unsigned fixed point binary number with 2 places after the point.

    6. 01000110101011002 as a 16-bit floating point number with a sign bit for the mantissa, a 7 bit biased exponent, and an 8-bit fixed point binary fraction. Most had the format right, half got the exponent right, and three in 5 had the mantissa right.

  2. What is the difference between an interrupt, a trap and a procedure call?

    Procedure calls have an explicit reference to the called routine; with traps and interrupts, the routine is implicit (implied by the cause). Traps and procedure calls are both caused by actions of the executing program, interrupts are caused by external conditions. Traps and interrupts transfer control to system or monitor service routines, procedure calls transfer control to procedures in the same program or sphere of protection.

    The above answer addresses 3 issues, cause (or initiation), mechanism (how the routine is determined) and use. Nobody addressed all of these issues; most got roughly half credit for full coverage of traps and interrupts with regard to use and initiation while largely ignoring procedure calls.

  3. Recursion and calling sequences: The routine given can be translated as follows: 
    	; --------------------------
	; activation record format
	;RA	= 0	; return address
	T	= 4	; save location for parameter
	SZ	= 8	; size of AR

	; expects	R3 = parameter t

	REVERSE:
		TEST	R3		; test t
		BZS	QUIT		; go return if t null
		STORES	R1,R2		; save RA if t not null
		STORE	R3,R2,T		; save t also
		LOAD	R3,R3,LEFT
		ADDI	R2,SZ
		JSR	R1,REVERSE	; reverse( t->left )
		LOAD	R3,R2,T-SZ
		LOAD	R3,R3,RIGHT
		JSR	R1,REVERSE	; reverse( t->right )
		ADDI	R2,-SZ
		LOAD	R3,R2,T
		LOAD	R4,R3,LEFT	; exchange
		LOAD	R5,R3,RIGHT	;   t->left and t->right
		STORE	R4,R3,RIGHT
		STORE	R5,R3,LEFT
		LOADS	R1,R2		; restore return address
	QUIT:
		JUMPS	R1
    This was close to being the "perfect exam question," in that the distribution of grades on this question alone was very similar to the distribution for the whole exam and the whole course. The answer above is perhaps the most compact translation possible for the Hawk architecture, and a fair number gave either this or a slightly less optimal and more straightforward solution. At the other extreme, some students clearly failed to understand the recursion and failed to effectively exchange the left and right pointers.

  4. Arrays and multiplication: Given int A[5][9]; the following code will fetch A[i,j] into R3: 
    	; assume R4 holds i, R5 holds j (this was given!)

	ADDSL	R4,R4,3	  ; multiply i by 9
	ADD	R4,R4,R5  ; make 9i + j (1 dimensional offset)
	LOAD	R5,APOINT ; get base address of array
	ADDSL	R4,R5,2   ; addr of A[i,j] = A + 4*(9i + j)
	LOADS	R3,R4     ; fetch array element
    This was another "perfect exam question." Many forgot to multiply by 4 (the number of bytes per word) or worse yet, attempted to treat A as an array of bytes. Many forgot the order of array indices in C and Pascal (in both languages, A is an array of 5 sub-arrays, each of which holds 9 integers.) A few students managed to present answers with loops or other mysterious control structures that suggest a complete misunderstanding of the question.

  5. The IBM Model 1301 Disk Storage System had:

    1. 250 cylinders.
    2. 40 surfaces for data plus 8 others.
    3. 10,000 data tracks (40 times 250).
    4. 20 megabytes of storage (10,000 times 2 Kbytes).
    5. it took at least 5.55 minutes to read all 10,000 tracks (reading one track per revolution at 30 revolutions per second).
    6. 8 bits to specify one cylinder out of 250.
    7. 6 bits to specify one surface out of 40.

    This problem wasn't particularly difficult, but perhaps a third of the class managed to either read the question carelessly or study the material poorly. The hardest sub question involved the time to read the whole disk. Some had very strange answers, while some had answers that assumed that all tracks in one cylinder could be read in parallel.

  6. Macros for an odd architectures: The following macros provide a start at a civilized assembly language for the strange architecture presented in the question: 
    	MACRO	MOVE =A,=B
	 H B
	 H A
	ENDMAC

	MACRO	BR =A
	 MOVE	#FFFF,A
	ENDMAC

	MACRO	ADD =A
	 MOVE	#FFFB,A
	ENDMAC

	MACRO	BPOS =A
	 MOVE	#FFFE,#FFFA
	 BR	A
	ENDMAC
    Many students gave fairly good answers. The most common error was to permute the parameters to the MOVE macro so source and destination were interchanged. Many who completely wrecked the MOVE macro managed to give good definitions for BR, ADD and BPOS in terms of it. Some students interpreted the question oddly, giving Hawk instructions instead of instructions in the strange machine language of the proposed machine. Some students were obviously confused and attempted to use conditional assembly in the BPOS instruction.