Course ID: 001956102691 Page 2 of 13
Mock Examination Do Not Use!
Basic Gates and Boolean Logic Question 1
a Published in Mock Exam
The following diagram shows a one bit demultiplexor 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 1bit dmux above, draw an implementation for a dmux with four outputs and a twobit selector. In your diagram assume that in remains as one bit.
4 marks
Total for Question 1: 4 marks
in
sel
PLEASE SEE NEXT PAGE
dmux
b
a
Course ID: 001956102691 Page 3 of 13
Mock Examination Do Not Use!
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 halfadder:
a sum carry
a halfadder sums its two input bits to produce a sum bit and a carry bit. Answer the following:
i. Draw an implementation of a fulladder chip composed from halfadder chips andor 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 fulladder 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
b
Half Adder
a
b c
sum carry
Full Adder
PLEASE SEE NEXT PAGE
Course ID: 001956102691
Mock Examination Do Not Use!
Sequential Logic Question 3
a Published in Mock Exam
43 Sequential Logic
Look at the following diagram for an invalid design for a 1bit register from
DFF
figure 3.1 of the textbook.
load inoutin outin out
Page 4 of 13
outtint1
outtoutt1 ? outtint1 ?
DFF
if loadt1 then outtint1 else outtoutt1
Answer the following.
i. BrieflFyliepxfplolpain what is wrongInwvailtihd dtehsiegndesign of the register1abiot rveegi.ster Bit 2 marks
Hack Assembler and Machine Code
Question 4
out wire. More generally, the rules of chip design dictate that internal pins must have a fanin of 1, meaning that they can be fed from a single source only.
The good thing about this thought experiment is that it leads us to the correct and
DFF
Figure 3.1 From a DFF to a singlebit register. The small triangle represents the clock input. This icon is used to state that the marked chip, as well as the overall chip that encapsulates it,
ii. Draw a correct design for the 1bit register above and write down the
is timedependent.
equality that explains the relationship between the in and out wires.
4 marks
Well, not so. The device shown in the middle of figure 3.1 is invalid. First, it is not
Total for Question 3: 6 marks
clear how well ever be able to load this device with a new data value, since there are no means to tell the DFF when to draw its input from the in wire and when from the
For the following questions you may find the information in Figures 3, 4, 5, 6, 7
elegant solution shown in the right side of figure 3.1. In particular, a natural way to
and 8 in the appendix ofrethsoilsvepoaupreinrputseamfubli.guity is to introduce a multiplexor into the design. Further, the
select bit of this multiplexor can become the load bit of the overall register chip:
a Published in Mock Exam
If we want the register to start storing a new value, we can put this value in the in
Look at the following Hack machine code:
0000000000010000
1111110010001000
1111110000010000
0000000000000000
1110001100000001
0000000000000101
1110101010000111
input and set the load bit to 1; if we want the register to keep storing its internal value until further notice, we can set the load bit to 0.
Once we have developed the basic mechanism for remembering a single bit over time, we can easily construct arbitrarily wide registers. This can be achieved by forming an array of as many singlebit registers as needed, creating a register that holds multibit values figure 3.2. The basic design parameter of such a register is its widththe number of bits that it holdse.g., 16, 32, or 64. The multibit contents of such registers are typically referred to as words.
Memories Once we have the basic ability to represent words, we can proceed to Answer the following:
build memory banks of arbitrary length. As figure 3.3 shows, this can be done by
i. Using the instruction formats in Figures 3, 4, 5, 6, and 7 as a guide, write
stacking together many registers to form a Random Access Memory RAM unit. The downtheHacktaersmsermanbdoemrianccsetsrsumcteimoonrysdtheraivtesarfreomeqtuheivraeqleuinretmteonththiastcroeadew.riteoperations
ii. Describe what the machine code does.
7 marks 3 marks
Total for Question 4: 10 marks
PLEASE SEE NEXT PAGE
Mux
Course ID: 001956102691 Page 5 of 13
Mock Examination Do Not Use!
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 c 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 figures in the appendix for some of the information you need.
6 marks
Total for Question 5: 6 marks
PLEASE SEE NEXT PAGE
Course ID: 001956102691
Mock Examination Do Not Use!
Assembler Question 6
a Published in Mock Exam
Look at the following Hack assembler code:
X
DM
END
D;JGE
X
MM
END
END
0;JMP
Handassemble 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.
Virtual MachineExpressions Question 7
a Published in Mock Exam
Translate the following Jack let statement into Hack Virtual Machine lan guage:
let d2xy5
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
PLEASE SEE NEXT PAGE
9 marks
Total for Question 6: 9 marks
Page 6 of 13
Course ID: 001956102691 Page 7 of 13
Mock Examination Do Not Use!
Virtual MachineSubroutines Question 8
a Published in Mock Exam
The Hack Virtual Machine language provides three function related commands:
callfm
function f n
return
i. Briefly describe what the function command does during program execu tion.
2 marks
ii. Briefly describe what the call command does during program execution. 7 marks
iii. Briefly describe what the return command does during program execu tion.
8 marks
b Published in Mock Exam
The Hack Virtual Machine allocates an area of the stack for each active func tion call. Briefly describe the structure of one of these stack frames immedi ately after the execution of the function command in a Jack method that is declared with N parameters and M local variables.
Jack Question 9
a Published in Mock Exam
Write a Jack program that calls a recursive function to calculate the 7th fi bonacci number. The result must be placed in an int variable x.
8 marks
Total for Question 9: 8 marks
PLEASE SEE NEXT PAGE
9 marks
Total for Question 8: 26 marks
Course ID: 001956102691 Page 8 of 13
Mock Examination Do Not Use!
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 transferint sum, BankAccount b2
var Date due ;
var int i,j ;
let isum ;
Code Generation Question 11
10 marks
Total for Question 10: 10 marks
a Published in Mock Exam
Consider the following Jack method:
method int uselessString 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 local17x ;
ii. return local01 ;
6 marks 4 marks
Total for Question 11: 10 marks
PLEASE SEE NEXT PAGE
Course ID: 001956102691 Page 9 of 13
Mock Examination Do Not Use!
Jack OS, Optimisation Question 12
a Published in Mock Exam
What determines the minimum length of a clock cycle in a processor?
3 marks
b 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
c Published in Mock Exam
What aspects of a processors physical implementation might prevent an in crease to the frequency of the processors clock?
3 marks
Total for Question 12: 10 marks
PLEASE SEE NEXT PAGE
Course ID: 001956102691
Page 10 of 13
36 Chapter 2
x
16 bits
y
16
bits
zx nx zy ny f no
Mock Examination Do Not Use! APPENDICES
fx,y
ALU
out
16 bits
zr ng
Inputs: x16, y16,Two 16bit data inputs
Chip name: ALU
Figure 1: An interface diagram for the ALU. From figure 2.5 of the textbook.
37
Boolean Arithmetic
These bits instruct how to pfr,eset the x inpout
These bits instruct This bit selects This bit inst. Resulting how topreFsuentction cobdeetw:ee1n for Addh,ow0tofor And ALU
zx, Zero the x input
nx,
zy,
Negate the x input
Zero the y input
ny,
Negate the y input
the yinpNuetgate the outAnodutput postset out O
output
utputs:
zx
out16,
nx
zy
16bit
ny
outputf
no
out
if zx
unction:
then x0
zr, ng
if nx
if zx th
then ifxn!xx th
if zy
nx0
then
n xy0 !x
True if
True if
if ny
1
then y!y B
f out0
if f then
f out0
outxy
6bit zero co
else itwoiustexnyegat
nstant
if no
then ionout!out
fx,y
omment:
1
1
1
0
1
0
1
0
1
0 1 0 1 0 0 0 0 0
if z0y th if n1y th
1
if f the 0 els
1
if no th
0
if o1ut0
0
if out0
1
Overflow
1 1
Figure 2.5
0 1 0 1 0 0 1
n y 1 0 n y 1 !y
outx
then ng
1
outx
1
1 then0 zr
0
n out
1
0
is neithe
1 0
The Arith
1 0 0 0 0 0 0
0 1
1 B
y 0 I
y 1 B 0
out 1 B 1 e0lse z
1
1 else n
0
r detecte
1 1
etic Logic U
1 0 0 0 1 0 1
6bit 1zero co
itwis1e negat
nteger12s co 0
itwise And
0
itwise negat
0
r0 0 16
g0 1 16 1
d nor handled
nit.
1 1 1 1 1 1 1 0 0
nstant0 ion 1
0
mplement addi
0
0
1
bit eq1. comp 1
1 1 1 0 0 0 1 1 0 1
ion
bit neg. com
.
0
1
1 tionx
y
!x ariso!ny
parison
x
y
x1
y1
x1
y1
xy
xy
yx
xy
xy
Fe e e e n e
C
e!
m
Figure 2.6 The ALU truth table. Taken together, the binary operations coded by the first six
columns effect the function listed in the right column we use the symbols !, , andto rep
resent the operators Not, And, and Or, respectively, performed bitwise. The complete ALU
Figure 2: The Hack ALU truth table. From figure 2.6 of the textbook.
truth table consists of sixtyfour rows, of which only the eighteen presented here are of interest.
and 1. Since the fbit is 1, the selected operation is arithmetic addition, causing the ALU to calculate x1. Finally, since the no bit is 0, the output is not negated but rather left as is. To conclude, the ALU ends up computing x1, which was our goal.
Does the ALU logic described in figure 2.6 compute every one of the other seven
teen functions listed in the figures right column? To verify that this is indeed the
case, the reader can pick up some other rows in the table and prove their respec
PLEASE SEE NEXT PAGE
tive ALU operation. We note that some of these computations, beginning with the
66
Chapter 4
or a symbol referring to such number. value v 14 0 or 1
representation, a symbolic representation, and an effect on the computer, as we now specify.
Course ID: 001956102691 Page 11 of 13
4.2.2 The AInstructionMock Examination Do Not Use! The Ainstruction is used to set the A register to a 15bit value:
Ainstruction: valueWhere value is either a nonnegative decimal number
4.2.3 The CInstruction
Binary: 0vvv vvvv vvvv vvvv
The Cinstruction is the programming workhorse of the Hack platformthe in This instruction causes the computer to store the specified value in the A register. For
struction that gets almost everything done. The instruction code is a specification
Figure 3: The format of an Ainstruction. From page 64 of the text book.
example, the instruction 5, which is equivalent to 0000000000000101, causes the that answers three questions: a what to compute, b where to store the computed
computer to store the binary representation of 5 in the A register.
value, and c what to do next? Along with the Ainstruction, these specifications
dTehtermAininesatrllutchtieopnoissibulsedopfeorratihorneseodfitfhferecnotmpurtepro.ses. First, it provides the only
way to enter a constant into the computer under program control. Second, it sets the Cinstruction: dest14comp;jumpEither the dest or jump fields may be empty. stage for a subsequent Cinstruction designed to manipulate a certain data memory
If dest is empty, the 14 is omitted;
location, by first setting A to the address of that location. Third, it sets the stage for
If jump is empty, the ; is omitted.
a subsequent Cinstruction that specifies a jump, by first loading the address of the
67
jumpdestinationtotheAregister.cTomhepse usesaredemonstratedeisntfigure4j.u2m.p
Binary: 1 1 1 a c1 c2 c3 c4
The leftmost bit is the Cinstruction code, which is 1. The next two bits are not
used.FTighuerem4a:inTinhgebfoitrsmfoartmotfhareneCfielidnstrhuacttciornre.sFporondmtopathget6h6reeofpathrtes otefxthtebook.
instructions symbolic representation. The overall semantics of the symbolic instruc
tion dest 14 comp;jump is as follows. The comp field instructs the ALU what to com Machine Language
pute. The dest field instructs where to store the computed value ALU output. The jump field specifies a jump condition, namely, which command to fetch and execute
c5 c6 d1 d2
d3 j1 j2 j3
when a0 when a1 next. We now describe the format and semantics of each of the three fields.
comp mnemonic c1 c2 c3 c4 c5 c6 comp mnemonic
TheComputationSpecific0ation T1heH0ackA1LU0isde1signed0tocomputeafixedset of functions on the D, A1, and M1 regi1sters1wher1e M1stand1s for MemoryA. The computed function is spec1ified by1the a1bit a1nd th0e six 1cbits0comprising the instruc tions comp field. This 7Dbit patte0rn ca0n pot1entia1lly co0de 1208 different functions, of which only the 28 listed inA figure 14.3 ar1e doc0umen0ted in0the l0anguageMspecification.
Recall that the forma!tDof the C0instr0uctio1n is 111a c0ccc 1ccdd djjj. Suppose we want to have the ALU!cAompute1D1,1the c0urren0t valu0e of1the D r!egMister minus 1. According to figure 4.3,tDhis can b0e do0ne by1issuin1g the1 instr1uction 1110 0011 1000 0000 the 7bit operationAcode is 1in bol1d. To0 com0pute 1the va1lue of DM, we issue the instruction 1111 0101D0100 0000. To1 com1pute 1the c1onsta1nt 1, we issue the in struction 1110 1110 10A001 0000, a1nd so1 on. 0 1 1 1 M1
D1 001110
The Destination SpeciAfica1tion T1he va1lue c0ompu0ted 1by th0e compMpa1rt of the C instruction can be storeDdAin severa0l dest0inatio0ns, a0s spec1ified 0by the inDstrMuctions 3bit
DA 010011 DM AD 000111 MD DA 000000 DM DA 010101 DM
Figure 4.3 The compute field of the Cinstruction. D and A are names of registers. M refers to Figure5t:heTmhemmoreyalonciantigonoafdCdreisnssedtrbuyctAio,namFieelyl,dtso.MFreommoryfiAgu.rTehe4s.y3mobfoltsheatnedxtbodeonko.te 16bit 2s complement addition and subtraction, while !, , anddenote the 16bit bitwise Boolean operators Not, Or, and And, respectively. Note the similarity between this instruction
set and the ALU specification given in figure 2.6.
dest part see figure 4.4. The first and second dbits code whether to store the com PLEASE SEE NEXT PAGE
puted value in the A register and in the D register, respectively. The third dbit codes whether to store the computed value in M i.e., in MemoryA. One, more than one, or none of these bits may be asserted.
Recall that the format of the Cinstruction is 111a cccc ccdd djjj. Suppose
Course ID: 001956102691 Page 12 of 13
68 Chapter 4
Mock Examination Do Not Use!
d1 d2 d3 Mnemonic Destination where to store the computed value
0 0 0 0 0 1
0 1
1 0
1 0 1 1 1 1
0 null 1 M
0 D
1 MD
0 A
1 AM 0 AD 1 AMD
The value is not stored anywhere
MemoryA memory register addressed by A D register
MemoryA and D register
A register
A register and MemoryA
A register and D register
A register, MemoryA, and D register
The dest field of the Cinstruction.
Figure 6: The meaning of the destination bits of the Cinstruction From figure 4.4 of
the textbook.The first instruction causes the computer to select the memory register whose address 110 Chapter 6
69 Machine Language
dest d1 d2 d3 jump j1 j2 j3
Figure 4.4
is 7 the socalled M register. The second instruction computes the value of M1 and stores the result in both M and D.
The Jump Specification The jump field of the Cinstruction tells the computer what
to do next. There are twnouplolssibilities:0The c0ompu0ter should eitnhuerlfletch and e0xecut0e 0
j1 j2 j3
Mnemonic Effect
the next instruction in the program, which is the default, or it should fetch and exe
out0 out 14 0 Mout0 0 0 1 JGT 0 0 1
cute an instruction located elsewhere in the program. In the latter case, we assume
0 0 D0 0nul1l0NojumpJEQ 010 that the A register has been previously set to the address to which we have to jump.
JGT If out0 jump
Whether or not a jump should actually materialize depends on the three jbits of
0 0 1
MD 011 JGE 011
0 1 0 JEQ If out 14 0 jump
the jump field and on thAe ALU output1value0com0puted accordiJnLgTto the comp1field0. 0
0 1 1 JGE If out b 0 jump
The first jbit specifies whether to jump in case this value is negative, the second jbit
AM 101 JNE 101
JLT If out0 jump
AD 110 JLE 110
1 0 0
in case the value is zero, and the third jbit in case it is positive. This gives eight
1 0 1 JNE If out 0 0 jump possible jump conditions, shown in figure 4.5.
1 1 AMD0 1 JLE1 1 Ifouta0JjMuPmp 1 1 1 The following example illustrates the jump commands in action:
1 1 1 JMP Jump
Logic Implementation
Figure 4.5 The jump field6o.f2t.h3e CiSnsytrmucbtionls. Out refers to the ALU output resulting from
if Memory35 then goto 100 3
the instructions comp part, and jump implies continue execution with the instruction adderlessedgboyttohe2A00register. DMDMemory3
Hack assembly5commands can refer to memory locations addresse DDADD5
either constants or symbols. Symbols in assembly programs arise fro The last instruction 0;JMP effects an unconditional jump. Since the Cinstruction
Figure 7: The meaning of the jump bits of the Cinstruction From figure 4.5 of the
textbook.
syntax requires that wesoaluwracyesse.ffect some computation, we instruct the ALU to
compute 0 an arbitrary choice, which is ignored.
100
D;JEQ If D0 goto 100
200
Predefined Symbols Any Hack assembly program is allowed to use the f 0;JMPGoto 200
Conflicting Uses of the A Register As was just illustrated, the programmer can use predefined symbols.
the A register to select either a data memory location for a subsequent Cinstruction
involving M, or an instruction memory location for a subsequent Cinstruction Label RAM address hexa
4.2.4 Symbols
involving a jump. Thus, to prevent conflicting use of the A register, in wellwritten programs a Cinstruction that may cause a jump i.e., with some nonzero j bits
SP 0 should not contain a reference to M, and vice versa.
0x0000
0x0001
0x0002
0x0003
LCL 1 ARG 2 THIS 3
AssemblycommandscaTnHrAeTfertomemorylo4cationsaddresses0xu0si0n0g4eithercon stants or symbols. Symbols are introduced into assembly programs in the following
R0R15 015 0x0000f SCREEN 16384 0x4000
text book.
mthree ways:
Predefined symbols: A special subset of RAM addresses can be referred to by
KBD 24576 0x6000 any assembly program using the following predefined symbols:
Virtualregisters: ToNsiomtpeliftyhastseemabclyhporongeramofmitnhge,thtoepsymfibvoelsR0AtMoR1l5oacraetions can be referred to u Figure 8: The predefined symbols in Hack Assembly language. From page 110 of the
predefined to refer to RAM addresses 0 to 15, respectively.
predefined symbols. For example, either R2 or ARG can be used to
Predefined pointers: The symbols SP, LCL, ARG, THIS, and THAT are predefined RAM2.
to refer to RAM addresses 0 to 4, respectively. Note that each of these memory
Label Symbols The pseudocommand Xxx defines the symbol Xxx to ref instruction memory location holding the next command in the program. A bPeLdEeAfinSeEdSoEnElyNoEnXceTaPnAdGcEan be used anywhere in the assembly program, ev the line in which it is defined.
s
s
l e
Course ID: 001956102691 Page 13 of 13
Lexical Elements
keyword
symbol
Mock Examination Do Not Use!
:: classconstructorfunctionmethod
fieldstaticvarintchar
booleanvoidtruefalsenull
thisletdoifelsewhile
return
:: .
,;
integerConstant :: A decimal number in the range 0 .. 32767
stringConstant::A sequence of Unicode characters not including
identifier
Statements
statements
statement
letStatement
ifStatement
double quote or newline
:: A sequence of letters, digits and underscore
not starting with a digit.
:: statement
:: letStatementifStatementwhileStatement
doStatementreturnStatement
:: let varNameexpression ?expression ;
:: ifexpression statements
elsestatements ?
whileStatement:: whileexpression statements
doStatement :: do subroutineCall ;
returnStatement :: return expression? ;
Expressions
expression:: term op term
term:: integerConstantstringConstant
keywordConstantvarName
varNameexpression subroutineCall
expressionunaryOp term
subroutineCall:: subroutineNameexpressionList
classNamevarName . subroutineNameexpressionList
expressionList:: expression , expression?
op::
unaryOp ::
keywordConstant :: truefalsenullthis
varName :: identifier
Figure 9: The Jack grammar. From figure 10.5 of the textbook.
END OF EXAMINATION PAPER
Reviews
There are no reviews yet.