Basic Gates and Boolean Logic

Question 1

(a) Published in Mock Exam

The following diagram shows a one bit de-multiplexor (dmux) chip.

This chip directs the signal from in to either a or b depending on the value of sel. The non selected ouput is zero.

Now, given the 1-bit dmux above, draw an implementation for a dmux with four outputs and a two-bitselector. In your diagram assume that in remains as one bit. [4 marks]

[Total for Question 1: 4 marks]

Boolean Arithmetic and ALU design

Question 2

For the following questions you may find the information in Figures 1 and 2 in the appendix of this paper useful.

(a) Published in Mock Exam

The following is a diagram the interface of a 1 bit half-adder:

a half-adder sums its two input bits to produce a sum bit and a carry bit. Answer the following:

i. Draw an implementation of a full-adder chip composed from half-adder chips and/or other gates. Recall that the interface for a full adder is:

[7 marks]

ii. Write the code in the PARTS section of a HDL file describing the full-adder you defined in your answer to part (i) above.   In your code you must assume that the inputs to the full adder are as labelled in the diagram above. [6 marks]

[Total for Question 2:  13 marks]

Computer Architecture

Question 5

For the following questions you may find the information in Figures 1, 2, 3, 4, 5, 6, 7 and 8 in the appendix of this paper useful.

(a) Published in Mock Exam

Look at the following partial diagram of a Hack CPU taken from Figure 5.9 of the textbook:

Some of the control logic is missing from this diagram.  These missing gates and wires are marked with a Oc symbol.  In the diagram one such section of missing control logic is marked with a large X. Given what you know about Hack instruction formats and ALU design, describe in detail what this missing control logic is.

Hint: feel free to use the figuresin the appendix for some of the information you need. [6 marks]

[Total for Question 5: 6 marks]

Assembler

Question 6

(a) Published in Mock Exam

Look at the following Hack assembler code:

@X

D=M

@END

D;JGE

@X

M=-M

(END)

@END

0;JMP

Hand-assemble this code by writing out the binary machine code the assembler would produce. For this question you may find the information in Figures 3, 4, 5, 6, and 7 useful. [9 marks]

[Total for Question 6: 9 marks]

Virtual Machine - Expressions

Question 7

(a) Published in Mock Exam

Translate the following Jack let statement into Hack Virtual Machine lan- guage:

let  d  =  ((2  -  x)  *  y)  +  5

The variables d, x and y are in memory segment local at indexes 2,5 and 7 respectively.  Assume there is a function named multiply that will take two arguments and return the result of multiplying the two numbers together. [8 marks]

[Total for Question 7: 8 marks]

Parsing

Question 10

(a) Published in Mock Exam

Show the two symbol tables for the following code just ater the last variable declaration in the method has been parsed.

class  BankAccount

{

//  Class  variables

static  string  key  ;

static  int nAccounts  ;

//  Instance  variables  ;

field  string  owner  ;

field  int balance  ;

method  void  transfer(int  sum,  BankAccount b2) {

var  Date  due  ;

var  int  i,j  ;

let  i  =  sum  ;

}

}

[10 marks]

[Total for Question 10:  10 marks]

Code Generation

Question 11

(a) Published in Mock Exam

Consider the following Jack method:

method  int useless(String  x,  String  y)

{

var  Array  local1  ;

var  int  local0  ;

var  string  local3  ;

}

What Hack Virtual Machine language code would implement the following

Jack program fragments if they were in the body of the method useless? i.              let  local1[7]  =  x  ; [6 marks]

ii.               return  local0  +  1  ; [4 marks]

[Total for Question 11:  10 marks]

Jack OS, Optimisation

Question 12

(a) Published in Mock Exam

How do caches take advantage of temporal and spatial locality to improve the performance of a computer? [4 marks]

(b) Published in Mock Exam

What determines the minimum length of a clock cycle in a processor? [2 marks]

(c) Published in Mock Exam

The Jack Operating System provides a small number of libraries that extend the functionality of the Jack programming language.  Excluding support for graphical user interfaces, identify two operating system services that are not provided by the Jack OS but are provided by Linux. In each case explain why the service is important. [4 marks]

[Total for Question 12:  10 marks]