Dec 1998 CS202: Computer Architecture and Data Communication (Question 3)

(a)	Define the following terms:	[6]
	(i) stack pointer;
	Address of last available stack location (2 marks).
	(ii) stack limit;
	Address of last data (i.e. most recently pushed) data on the stack (2 marks).
	(iii) stack overflow
	This is what happens when someone attempts to push data onto an already full stack (i.e. one where the stack limit and the stack pointer have the same value) (2 marks).
(b)	A subroutine call operation begins as:	[4]
	SP <-- SP + 1 (increment stack pointer)
	Mem[SP] <-- PC (pushes content to PC onto the stack)
	PC <-- Starting address of subroutine (transfer control to subprogram)
	Show, in similar terms, what operations take place when control returns from the subroutine to the main calling program.
	PC <-- Mem[SP] (causes a jump to the PC address stored on the stack) SP <-- SP - 1 (decrement stack pointer) Award (1 mark) for each the symbolic step, and (1 mark) for each explanation. Also allow credit for answers presented differently but containing the correct information.
(c)	State two difference between a subroutine and an interrupt.	[4]
	Interrupt: initiated by internal/external interrupt signal (1 mark). Subroutine: initiated through execution of instruction in program (1 mark). Address of interrupt service routine determined by hardware (1 mark), rather than from address which is part of instruction word in subroutine call (1 mark). In interrupt call, contents of PC, processor register contents and PSW are stored onto stack (1 mark); in subroutine only PC and possible processor register contents are stored onto stack (1 mark).
(d)	Stacks are often used to evaluate logical and arithmetic expressions. Given a stack in a O-Address format, write a program to evaluate the following expression: X := ((A B / C) + (D + C - F)) / (G - H)* What maximum stack size (stack depth) is needed in order to execute your program? Explain your answer.	[6]
	One solution is: PUSH A PUSH B PUSH C DIV MUL PUSH D PUSH C PUSH F SUB ADD ADD PUSH G PUSH H SUB DIV POP X Four marks for a fully correct answer. Deduct one mark for each wrongly-evaluated subexpression, or for failure to finish with POPX. Program needs a stack depth of 4 (1 mark), because after the PUSH F instruction above, there are four values on the stack (1 mark). Answers will vary if the expression is evaluated in a different order. Allow credit where appropriate.