Do Not Use!
001956 / 102691 Computer Systems – UG / PG COMP SCI 2000 / 7081
Official Reading Time: Writing Time:
Total Duration:
Copyright By PowCoder代写 加微信 powcoder
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 for Translation Only
DO NOT COMMENCE WRITING UNTIL INSTRUCTED TO DO SO
Course ID: 001956 / 102691 Page 2 of 13
Do Not Use!
Basic Gates and Boolean Logic Question 1
(a) Published in
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-bit selector. In your diagram assume that in remains as one bit.
[Total for Question 1: 4 marks]
PLEASE SEE NEXT PAGE
Course ID: 001956 / 102691 Page 3 of 13
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
The following is a diagram the interface of a 1 bit half-adder:
a” sum” carry”
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:
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.
[Total for Question 2: 13 marks]
Half” Adder”
sum” carry”
Full” Adder”
PLEASE SEE NEXT PAGE
Course ID: 001956 / 102691
Do Not Use!
Sequential Logic Question 3
(a) Published in
43 Sequential Logic
Look at the following diagram for an invalid design for a 1-bit register from
figure 3.1 of the textbook.
load inoutin outin out
Page 4 of 13
out(t) = in(t–1)
out(t) = out(t–1) ? out(t) = in(t–1) ?
if load(t–1) then out(t) = in(t–1) else out(t) = out(t–1)
Answer the following.
i. BrieflFyliepx-fplolpain what is wrongInwvailtihd dtehsiegndesign of the register1a-biot 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 fan-in 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
Figure 3.1 From a DFF to a single-bit 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 1-bit register above and write down the
is time-dependent.
equality that explains the relationship between the in and out wires.
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 we’ll 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
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 single-bit registers as needed, creating a register that holds multi-bit values (figure 3.2). The basic design parameter of such a register is its width—the number of bits that it holds—e.g., 16, 32, or 64. The multi-bit 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 downtheHacktaersmsermanbdoemrianccsetsrsumcteimoonrysdtheraivtesarfreomeqtuheivraeqleuinretmteonththiastcroeade/w.riteoperations
ii. Describe what the machine code does.
[7 marks] [3 marks]
[Total for Question 4: 10 marks]
PLEASE SEE NEXT PAGE
Course ID: 001956 / 102691 Page 5 of 13
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
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.
[Total for Question 5: 6 marks]
PLEASE SEE NEXT PAGE
Course ID: 001956 / 102691
Do Not Use!
Assembler Question 6
(a) Published in
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.
Virtual Machine – Expressions Question 7
(a) Published in
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
[Total for Question 6: 9 marks]
Page 6 of 13
Course ID: 001956 / 102691 Page 7 of 13
Do Not Use!
Virtual Machine – Subroutines Question 8
(a) Published in
The Hack Virtual Machine language provides three function related commands:
• function f n
i. Briefly describe what the function command does during program execu- tion.
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.
(b) Published in
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.
(a) Published in
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.
[Total for Question 9: 8 marks]
PLEASE SEE NEXT PAGE
[Total for Question 8: 26 marks]
Course ID: 001956 / 102691 Page 8 of 13
Do Not Use!
Parsing Question 10
(a) Published in
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 ;
Code Generation Question 11
[10 marks]
[Total for Question 10: 10 marks]
(a) Published in
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 ;
ii. return local0 + 1 ;
[6 marks] [4 marks]
[Total for Question 11: 10 marks]
PLEASE SEE NEXT PAGE
Course ID: 001956 / 102691 Page 9 of 13
Do Not Use!
S, Optimisation Question 12
(a) Published in
How do caches take advantage of temporal and spatial locality to improve the performance of a computer?
(b) Published in
What determines the minimum length of a clock cycle in a processor?
(c) Published in
The perating 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 S but are provided by Linux. In each case explain why the service is important.
[Total for Question 12: 10 marks]
PLEASE SEE NEXT PAGE
Course ID: 001956 / 102691
Page 10 of 13
36 Chapter 2
zx nx zy ny f no
Do Not Use! 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.
zx, // Zero the x input
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
// 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 specify.
Course ID: 001956 / 102691 Page 11 of 13
4.2.2 The A-Instruction Do Not Use! The A-instruction is used to set the A register to a 15-bit value:
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
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
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
// 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þeatnedxtbodeonko.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
Course ID: 001956 / 102691 Page 12 of 13
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.
Do Not Use!
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
dest d1 d2 d3 jump j1 j2 j3
Figure 4.4
is 7 (the so-called M register). The second instruction computes the value of M þ 1 and stores the result in both M and D.
The Jump Specification The jump field of the C-instruction tells the computer what
to do next. There are twnouplolssibilities:0The c0ompu0ter should eitnhuerlfletch and e0xecut0e 0
Mnemonic Effect
the next instruction in the program, which is the default, or it should fetch and exe-
(out < 0) (out 1⁄4 0) (Mout > 0) 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 out > 0 jump
Whether or not a jump should actually materialize depends on the three j-bits of
MD 011 JGE 011
0 1 0 JEQ If out 1⁄4 0 jump
the jump field and on thAe ALU output1value0(com0puted accordiJnLgTto the comp1field)0. 0
0 1 1 JGE If out b 0 jump
The first j-bit specifies whether to jump in case this value is negative, the second j-bit
AM 101 JNE 101
JLT If out < 0 jump
AD 110 JLE 110
in case the value is zero, and the third j-bit 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 C-iSnsytrmucbtionls. Out refers to the ALU output (resulting from
if Memory[3]=5 then goto 100 @3
the instruction’s comp part), and jump implies ‘‘co
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com