NOTICE: Past Exams
Past exams are provided as-is for reference only.
• The content of this exam reflects course content and learning outcomes as they were at the time this exam was administered.
• This course’s content, structure, and/or focus may have changed since this past exam was administered.
Copyright By PowCoder代写 加微信 powcoder
• As such, the content, structure and types of questions contained herein may differ from those in your final exam.
• If you plan on using this as a study resource, be sure to do so in conjuction with the current course’s syllabus and resources to ensure that your study covers the correct content.
Primary Examination, Semester 1, 2017
Computer Systems COMP SCI 2000, 7081
Official Reading Time: Writing Time:
Total Duration:
Answer all 12 questions
Instructions for Candidates
10 mins 120 mins 130 mins
120 marks 120 Total
• This is a Closed-book examination.
• Begin each answer on a new page.
• Examination material must not be removed from the examination room.
• Foreign Language Dictionaries are Permitted
DO NOT COMMENCE WRITING UNTIL INSTRUCTED TO DO SO
COMP SCI 2000, 7081
Page 2 of 14
Primary Examination, Semester 1, 2017
Basic Gates and Boolean Logic Question 1
i. Draw the truth table for the ̸= operator in terms of x and y.
ii. Draw an implementaton of the ̸= operator solely in terms of And, Or and
(a) Consider the expression:
which is true if the boolean values x and y are not equal. The expression is
false otherwise. Answer the following two questions:
Not gates.
Boolean Arithmetic and ALU design Question 2
[3 marks] [6 marks]
For the following questions you may find the information in Figure 2 useful.
(a) Look at the Hack ALU truth-table shown in Figure 2 in the Appendix. Note that it is possible to design the functionality of the ALU a few operations at a time. For this question, we will consider the last line of the table, which describes the Or operation. Answer the following:
i. In the ALU, the Or operation is implemented using an And chip and some other chips and wires. Give the logical expression for the Or operation implemented by the ALU. Your answer must include an And operation.
ii. Using a truth table, show that the expression you gave in part i above is equivalent to the Or operation.
iii. Draw an implementation of a 16-bit Or chip that uses a 16-bit And chip. [3 marks]
[Total for Question 2: 10 marks]
PLEASE SEE NEXT PAGE
[Total for Question 1: 9 marks]
COMP SCI 2000, 7081
Page 3 of 14
Sequential Logic Question 3
Look at the following diagram and text description for a program counter (PC)
Sequential Logic
from figure 3.5 of the textbook:
Primary Examination, Semester 1, 2017
inc load reset
in PC (counter) w bits
Chip name: PC // 16-bit counter Inputs: in[16], inc, load, reset Outputs: out[16]
Function: If reset(t-1) then out(t)=0
else if load(t-1) then out(t)=in(t-1)
else if inc(t-1) then out(t)=out(t-1)+1
else out(t)=out(t-1) Comment: “=” is 16-bit assignment.
“+” is 16-bit arithmetic addition.
Draw an implementation of the PC chip without the reset wire. That is, draw 47 47 0 0 1 2 3 4 527 528 529 530 530
an implementation of the PC that can handle signals from the inc and the load wires but doesn’t provide a reset function.
Note, you do not have to express your solution in terms of primitive gates such as Nand. You can use large scale chips such as Inc16.
527 527 527 527 527 527 527 527 527 527 527 527 527
22 23 24 25 26 27 28 29 30 31 32 33 34
We assume that we start tracking the counter in time unit 22, when its input and output happen to be 527 and 47, respectively. We also assume that the counter’s control bits (reset, load, inc) start at 0—-all arbitrary assumptions.
Figure 3.5 Counter simulation. At time 23 a reset signal is issued, causing the counter to emit 0 in the following time unit. The 0 persists until an inc signal is issued at time 25, causing the counter to start incrementing, one time unit later. The counting continues until, at time 29, the load bit is asserted. Since the counter’s input holds the number 527, the counter is reset to that value in the next time unit. Since inc is still asserted, the counter continues incrementing until time 33, when inc is de-asserted.
PLEASE SEE NEXT PAGE
[Total for Question 3: 10 marks]
[10 marks]
COMP SCI 2000, 7081
Page 4 of 14
Primary Examination, Semester 1, 2017
Hack Assembler and Machine Code
Question 4
For the following questions you may find the information in Figures 3, 4, 5, 6 and 7 in the appendix of this paper useful.
(a) Look at the following Hack machine code:
0000000000010000
1111110000010000
0000000000010001
1111000111001000
1111110000010000
0000000000000000
1110001100000001
Answer the following:
i. Using the instruction formats in Figures 3, 4, 5, 6, and 7 as a guide, write down the Hack assember instructions that are equivalent to this code.
ii. Describe what the machine code above does.
[7 marks] [3 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) Draw an implementation of the logic that implements the JNE (jump not- equal-to) part of the C-instruction. The interface for the JNE is:
[Total for Question 4: 10 marks]
j1j2j3 zrng
where the inputs are the jump wires from the C instruction and the zr and the ng wires from the ALU and the ouput is the load wire for the PC register. Note that you do not have to implement the logic for every type of jump – just JNE. Hint, in answering your question you may find the information in Figure 7 useful.
PLEASE SEE NEXT PAGE
COMP SCI 2000, 7081 Page 5 of 14 Primary Examination, Semester 1, 2017
(b) Consider the following diagram of the Hack CPU.
94 Chapter 5
ALU output
instruction inM
writeM addressM
Figure 5.9 Proposed CPU implementation. The diagram shows only data and address paths, The A/M wire, marked with an X, selects either the A-register or RAM as one
namely, wires that carry data and addresses from one place to another. The diagram does oftheinputvanolutsehsowfothreCaPUC’s-icnonsttrorlulocgtici,oenxc.epItnfortihnpeutHsaandckoutmpuatscohfcionnetroalbCits-,ilnabsetlerduwcithioan
circled ‘‘c’’. Thus it should be viewed as an incomplete chip diagram.
cannot access both the A-register and RAM as input in the same instruction. So, for example, the following instruction:
Naturally, the CPU will include an ALU capable of executing Hack instructions, a
set of registers, and some control logic designed to fetch and decode instructions.
Since almost all these hardware elements were already built in previous chapters, the
Is not a valid Hack instruction since it has both M and A as input.
key question here is how to connect them in order to effect the desired CPU opera-
Briefly describe why such access is unlikely to be useful even if it were permit-
tion. One possible solution is illustrated in figure 5.9.
ted by the HackTmheakcehyinelem.ent missing in figure 5.9 is the CPU’s control logic, designed to per-
mform the following tasks: Instruction decoding:
minstruction).
Instruction execution:
Figure out what the instruction means (a function of the
[Total for Question 5: 9 marks]
Signal the various parts of the computer what they should do in order to execute the instruction (a function of the instruction).
PLEASE SEE NEXT PAGE
COMP SCI 2000, 7081
Page 6 of 14
Virtual Machine – Expressions Question 7
Primary Examination, Semester 1, 2017
Assembler Question 6
(a) Look at the following Hack assembler code:
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.
(a) 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.
[Total for Question 7: 8 marks]
PLEASE SEE NEXT PAGE
[12 marks]
[Total for Question 6: 12 marks]
COMP SCI 2000, 7081
Page 7 of 14
Primary Examination, Semester 1, 2017
Virtual Machine – Subroutines
Question 8
(a) TheHackVirtualMachinelanguageprovidesthreefunctionrelatedcommands:
• function f n
i. Briefly describe the arguments to the function command.
ii. If the function command did not have the second argument, what alter- nate virtual machine code would need to be generated to implement: function c.x 2 ?
iii. Why does the second argument to the call command need to be pro- vided?
(a) How does the Jack compiler provided with the nand2Tetris tools ensure that a constructor, function or method from another class is being called correctly? Why does it do this?
(b) List the syntax errors in the following Jack class definition:
01 class x
03 function int xx(var int n)
05 if ( n <= 2 ) return 17 ;
06 return y.xxx(n--) ;
PLEASE SEE NEXT PAGE
[Total for Question 8: 10 marks]
[Total for Question 9: 8 marks]
COMP SCI 2000, 7081
Page 8 of 14
Primary Examination, Semester 1, 2017
Parsing Question 10
(a) Turn the following Jack code fragment into XML with one node for each non- terminal in the grammar.
let x[ix] = y ;
You should start with a node for a let statement and you may omit nodes for any keywords, identifiers or symbols. The grammar can be found in Figure 9 in the appendix.
[Total for Question 10: 8 marks]
PLEASE SEE NEXT PAGE
COMP SCI 2000, 7081
Page 9 of 14
Primary Examination, Semester 1, 2017
Code Generation Question 11
(a) Consider the following Jack method:
// class Complex contains 4 instance variables
// declared in this order: aa, bb, cc and dd, aa is an Array
method Complex useful(Complex a, Complex b)
What Hack Virtual Machine language code would implement the following Jack pro- gram fragments if they were in the body of the method useful?
i. let b = Complex.new(3,2) ;
ii. aa[7] = a ;
iii. return b ;
iv. let bb = dd ;
[4 marks] [6 marks] [2 marks] [3 marks]
(b) Show the two symbol tables for the following code just after the variable declaration in the method getSerial has been parsed.
class SerialNums
static int id ;
field int myid ;
constructor SerialsNums new(int key)
let myid = id ;
return this ;
method int getSerial(int password)
var int ignore_me ;
return myid ;
PLEASE SEE NEXT PAGE
[Total for Question 11: 19 marks]
COMP SCI 2000, 7081
Page 10 of 14
Primary Examination, Semester 1, 2017
S, Optimisation Question 12
(a) Why might implementing a 16-bit multiply operation in the ALU of the Hack machine significantly increase the time it takes to execute an instruction that sets the A and D registers to the value 0?
(b) What three aspects of a processor’s physical implementation determine the power consumption and how is this calculated?
[Total for Question 12: 7 marks]
PLEASE SEE NEXT PAGE
COMP SCI 2000, 7081
Page 11 of 14
36 Chapter 2
zx nx zy ny f no
Primary Examination, Semester 1, 2017
APPENDICES
Inputs: x[16], y[16], // Two 16-bit data inputs
Chip name: ALU
Figure 1: An interface diagram for the ALU. From figure 2.5 of the textbook.
Boolean Arithmetic
These bits instruct how to pfr,eset the x inpout
These bits instruct This bit selects This bit inst. Resulting how to//preFsuentction cobdeetw:ee1n for Addh,ow0tofor And ALU
zx, // Zero the x input
// Negate the x input
// Zero the y input
the y/i/npNuetgate the +o/utAnodutput postset out output
// Negate the y input
Outputs: out[16],
zx nx zy ny f
// 16-bit output
then ifx=n!xx th
then y=!/y/ B
6-bit zero co
else it-woiust=ex&nyegat
then ionout=!out
0 // 16-bit 1zero constant0 0 1// Bit-wis1e negation 1 1
if z0y then y 1= 0 if n1y then y1= !y
1 1 0 1 0 -1
if f then out = x + y // Integer 2's complement addition
else out = x & y // Bit-wise And
Figure 2.5 The Arithmetic Logic Unit.
0 0 1 1 1 0 x-1
1 1 0 0 1 0 y-1 0 0 0 0 1 0 x+y 0 1 0 0 1 1 x-y 0 0 0 1 1 1 y-x 0 0 0 0 0 0 x&y 0 1 0 1 0 1 x|y
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 !, &, and | to rep-
if no then out = !out // Bit-wise negation
0 1 1 0 1 !x if o1ut=0 then0 zr = 1 e0lse zr = 0 0// 16-bit eq1. compariso!ny
0 1 1 1 1 -x
if out<0 then ng = 1 else ng = 0 // 16-bit neg. comparison Comment: Overflow is neither detected nor handled.
1 1 0 0 1 1 -y
0 1 1 1 1 1 x+1 1 1 0 1 1 1 y+1
resent the operators Not, And, and Or, respectively, performed bit-wise). The complete ALU
Figure 2: The Hack ALU truth table. From figure 2.6 of the textbook.
truth table consists of sixty-four rows, of which only the eighteen presented here are of interest.
and !1. Since the f-bit is 1, the selected operation is arithmetic addition, causing the ALU to calculate x+(-1). Finally, since the no bit is 0, the output is not negated but rather left as is. To conclude, the ALU ends up computing x-1, 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 figure’s 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
// or a symbol referring to such number. value (v 1⁄4 0 or 1)
representation, a symbolic representation, and an effect on the computer, as we now
Page 12 of 14
COMP SCI 2000, 7081
4.2.2 The A-Instruction
The A-instruction is used to set the A register to a 15-bit value:
Primary Examination, Semester 1, 2017
A-instruction: @value // Where value is either a non-negative decimal number
4.2.3 The C-Instruction
Binary: 0vvv vvvv vvvv vvvv
The C-instruction is the programming workhorse of the Hack platform—the 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 A-instruction. 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 A-instruction, these specifications
dTehtermAi-ninesatrllutchtieopnoissibulsedopfeorratihorneseodfitfhferecnotmpurtepro.ses. First, it provides the only
jumpdestinationtotheAregister.cTomhepse usesaredemonstratedeisntfigure4j.u2m.p Binary: 1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
The leftmost bit is the C-instruction code, which is 1. The next two bits are not
used.FTighuerem4a:inTinhgebfoitrsmfoartmotfhareneCfie-lidnstrhuacttciornre.sFporondmtopathget6h6reeofpathrtes otefxthtebook.
instruction’s symbolic representation. The overall semantics of the symbolic instruc-
tion dest 1⁄4 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
way to enter a constant into the computer under program control. Second, it sets the C-instruction: dest1⁄4comp;jump // Either the dest or jump fields may be empty. stage for a subsequent C-instruction designed to manipulate a certain data memory
// If dest is empty, the ‘‘1⁄4’’ 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 C-instruction that specifies a jump, by first loading the address of the
(when a=0) (when a=1) 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 regi1sters1(wher1e M1stand1s for Memory[A]). The computed function is sp-ec1ified by1the a1-bit a1nd th0e six 1c-bits0comprising the instruc- tion’s comp field. This 7-Dbit 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 C0-instr0uctio1n is 111a c0ccc 1ccdd djjj. Suppose we want to have the ALU!cAompute1D-1,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 7-bit operatio-nAcode is 1in bol1d). To0 com0pute 1the va1lue of D-|M, we issue the instruction 1111 0101D0+100 0000. To1 com1pute 1the c1onsta1nt "1, we issue the in- struction 1110 1110 10A0+01 0000, a1nd so1 on. 0 1 1 1 M+1
D-1 001110
The Destination SpeciAfi-ca1tion T1he va1lue c0ompu0ted 1by th0e compMp-a1rt of the C- instruction can be storeDd+Ain severa0l dest0inatio0ns, a0s spec1ified 0by the inDs+trMuction’s 3-bit
D-A 010011 D-M A-D 000111 M-D D&A 000000 D&M D|A 010101 D|M
Figure 4.3 The compute field of the C-instruction. D and A are names of registers. M refers to Figure5t:heTmhemmoreyalonciantigonoafdCdr-eisnssedtrbuyctAio,namFieelyl,dtso.MFreommoryfi[Ag]u.rTehe4s.y3mobfoltshþeatnedxt"bodeonko.te 16-bit 2’s complement addition and subtraction, while !, |, and & denote the 16-bit bit-wise 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 d-bits code whether to store the com- PLEASE SEE NEXT PAGE
puted value in the A register and in the D register, respectively. The third d-bit codes whether to store the computed value in M (i.e., in Memory[A]). One, more than one, or none of these bits may be asserted.
Recall that the format of the C-instruction is 111a cccc ccdd djjj. Suppose
COMP SCI 2000, 7081
Page 13 of 14
68 Chapter 4
d1 d2 d3 Mnemonic
Destination (where to store the computed value)
The value is not stored anywhere
Memory[A] (memory register addressed by A) D register
Memory[A] and D register
A register
A register and Memory[A]
A register and D register
A register, Memory[A], and D register
syntax requires that wesoaluwracyesse.ffect some computation, we instruct the ALU to
text book.
Primary Examination, Semester 1, 2017
0 0 0 0 0 1
1 0 1 1 1 1
0 null 1 M
1 AM 0 AD 1 AMD
The dest field of the C-instruction.
Figure 6: The meaning of the destination bits of the C-instruction 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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com