Cs2100exam 1516s2 ans - Past year papper from CS2100. Question 7 to 11 PDF

Preview

Summary

NATIONAL UNIVERSITY OF SINGAPORECS2100 – COMPUTER ORGANISATION(Semester 2: AY2015/16)Time Allowed: 2 HoursINSTRUCTIONS TO CANDIDATES1.  Please write your  Student Number  on odd‐numbered pages of ...

Description





CS2100



Answer

NATIONALUNIVERSITYOFSINGAPORE

 

CS2100–COMPUTERORGANISATION (Semester2:AY2015/16)   TimeAllowed:2Hours

INSTRUCTIONS TO CANDIDATES 1. PleasewriteyourStudentNumberonodd‐numberedpagesoftheANSWERBOOKLET provided.Donotwriteyourname. 2. ThisassessmentpaperconsistsofELEVEN(11)questionsandcomprisesTEN(10)printed pages. 3. AnswerallquestionsandwriteyouranswersintheANSWERBOOKLETprovided. 4. ThisisaCLOSEDBOOKassessment.TwohandwrittenA4referencesheetsareallowed. 5. Calculatorsarenotallowed. 6. Youmayusepenciltowriteyouranswers. 7. Thelastthreepagesareforyourroughwork.Theycontainblank,K‐maps,statetableand timingchartsforyouruse. 8. YouaretosubmitonlytheANSWERBOOKLETandnootherdocument.



CS2100

Questions 1 ‐ 6: Each question has only one correct answer. Write your answers in the boxes provided in the Answer Booklet. One mark is awarded for a correct answerandno penaltyforwronganswer. 

1. Giventhefollowingjumpinstruction,originallyencodedas0x087B00A7: target: .............

#

j target  

Supposetheprogrammerlaterremove1oftheinstructionsin.Whatis thenewencodingforthejumpinstruction? A. B. C. D. E.

0x087B00A3 0x087B00A6 0x087B00A7 0x087B00A8 Noneoftheabove.

Commented [SYJ1]: Answer. The target instruction address is not affected.



2. Givenaprogramwith40%,40% and20%ofinstructiontypesA,BandCrespectively, whichofthefollowingchangesreducestheexecutiontimebyexactly40%ifCPIsforA, BandCare1,2and4respectively?  i. SpeedupexecutiontimeforinstructiontypeAby2xandtypeCby4x. ii. SpeedupexecutiontimeforinstructiontypesBandCby2x. iii. SpeedupexecutiontimeforinstructiontypesAandBby2x. A. B. C. D. E.

Commented [SYJ2]: Time proportion for A, B and C are 40x1 , 40x2, 20 x 4 = 40, 80, 80 = 20%, 40%, 40% Commented [SYJ3]: 20/2 + 40 + 40/4 = 10 + 40 + 10 = 60 (40% reduction) Commented [SYJ4]: 20 + 40/2 + 40/2 = 60 (40% reduction)

Only(i)isTRUE. Only(i)and(ii)areTRUE. Only(ii)and(iii)areTRUE. (i),(ii)and(iii)areallTRUE. Noneoftheabove.

Commented [SYJ5]: 20/2 + 40/2 + 40 = 10 + 20 + 40 = 70 (30% reduction) Commented [SYJ6]: Answer

 3. Suppose the cache index for the 16‐bit memory address 0xABCD is 0xE, which of the followingstatementsisTRUEregardingtheconfigurationofthiscache? 

 A. B. C. D. E.

Cachetag=4bits;Offset=8bits Cachetag=5bits;Offset=7bits Cachetag=6bits;Offset=6bits Cachetag=7bits;Offset=5bits Noneoftheabove.



Page2of16

Commented [SYJ7]: A B C D 1010 1011 1100 1101 E = 1110 The bolded portion is the only possibility.

Commented [SYJ8]: Answer





CS2100

4. Ifajumpinstruction,encodedas0x087B00A7isexecutedbythesinglecycle5‐stage MIPSprocessor,whatisthereadregisternumber2suppliedtotheregisterfileduring decode? A. B. C. D. E.

Registernumber=2710 Registernumber=2210 Registernumber=1110 Registernumber=710 Noneoftheabove

Commented [SYJ9]: 0 8 7 B 0 …….. 0000 1000 0111 1011 0000 ……….. The bolded portion is the read register number 2, i.e. 27 Commented [SYJ10]: Answer

  

5. The nop is a MIPS instruction that does nothing at all (i.e. the execution does not change the register / memory content in any way). Which of the following control signalsshouldbean'X'(don’tcare)forthenopinstruction? i. ALUSrc ii. MemToReg iii. RegDst A. B. C. D. E.

Only(i)isTRUE. Only(i)and(ii)areTRUE. Only(ii)and(iii)areTRUE. (i),(ii)and(iii)areallTRUE. Noneoftheabove.

Commented [SYJ11]: Answer

  

6. Suppose the "isBranch" control signal generated by a faulty control unit is always '1'. Which of the following instructions will cause this processor to branch to instruction addressotherthan(PC+4)afterexecution?YoucanassumethePCoftheinstructionis at0x04000000. i.

xor $t0, $s0, $s0#$s0containsrandomvalue

ii. andi $t0, $zero, 0xABCD iii. lw $s0, 0( $zero ) A. B. C. D. E.

Commented [SYJ14]: result is zero and immediate field is not 0

Commented [SYJ16]: Answer.

  Page3of16 

Commented [SYJ13]: result is zero and immediate field is not 0

Commented [SYJ15]: result is zero but immediate field is 0, i.e. BTA = PC+4 + Immd x 4 = PC+4.

Only(i)isTRUE. Only(i)and(ii)areTRUE. Only(ii)and(iii)areTRUE. (i),(ii)and(iii)areallTRUE. Noneoftheabove.





Commented [SYJ12]: Essentially looking for instructions where calculation result is 0 AND the immediate field is not 0.

CS2100

7. [12marks] Design a sequential circuit that takes a 1‐bit input X. When X = 0, the circuit cycles throughthe3‐bitGraycodesasfollow: 000001011010110111101100000….(repeats) WhenX=1,thecircuitcyclesthroughthesame3‐bitGraycodesequencebutinreverse order: 000100101111110010011001000….(repeats) Thestatesarerepresentedby3‐bitvaluesABC.Implementthesequentialcircuitusinga Dflip‐flopfor A,aTflip‐flopforB,andaJKflip‐flopfor C.Usethepartiallyfilledstate tablegivenonpage8tohelp. a. WriteoutthesimplifiedSOPexpressionsforalltheflip‐flopinputs.

[4marks]



b. ImplementDAusinga4‐to‐1Multiplexer.TheselectorlineshavebeenfixedtoS1=C andS0=X,soyouonlyneedtofillintheinputlines.Theinputsarerestrictedtonon‐ primedliterals,primedliteralsandconstants(0/1)only. [4marks] 

Commented [SYJ17]: Seepage11forworking. DA=B.C'.X'+B'.C'.X+A.C TB=A'.B'.C.X'+A'.B.C.X+A.B.C.X'+A.B'.C.X JC=A'.B'.X'+A'.B.X+A.B.X'+A.B'.X KC=A'.B'.X+A'.B.X'+A.B.X+A.B'.X' Commented [SYJ18]: See page 12 for (b), (c) and (d).

c. ImplementJCusingnomorethantwo2‐inputgates(AND,OR,XORorXNOR).Only non‐primedliteralsandconstantsareavailable. [3marks]  d. Using an additional 2‐input XOR or XNOR gate, implement KC by utilizing the JC function (i.e. use JC as one of the possible inputs). Only non‐primed literals and constantsareavailable. [1mark]    8. [5marks]IEEE‐754singleprecisionformatencodesafloatingpointvaluein32bits: 

  SupposeanIEEE‐754floatingpointvalueisstoredinregister$s0,attemptthefollowing. a. Use1MIPSinstructiontoextractthesign‐bitintoregister$t0,i.e.$t0stores0or1 attheend. [1marks]  b.Useatmost3MIPSinstructionstoextractthebias‐127exponentintoregister$t1, i.e.$t1stores‐127to128attheend. [2marks]  c. Recall that the mantissa was normalized to 1.X and only the fraction X (23 bits) is stored in the IEEE754 format. Suppose someone extracted the fraction bits and addedtheleading'1'inregister$t2foryou(i.e.$t2nowstoresa24‐bitvaluewith leading zeroes).  Use the sign bit $t0 from part (a) and $t2 to produce a 2s complementof themantissa inregister $s1. Fillin thetwo missinginstructions in thepartialcodingintheanswersheet. [2marks] Page4of16

Commented [SYJ19]: srl $t0, $s0, 31

Commented [SYJ20]: sll $t0, $s0, 1 #drop sign bit srl $t0, $t0, 24 #drop fraction addi $t1, $t0, -127 #bias

Commented [SYJ21]: add $s1, $zero, $t2 #make a copy beq $t0, $zero, end #check for negative sub $s1, $zero, $t2 #get 2s end: #2s complement of mantissa in $s1





CS2100

9. [8marks] # $s0 initialized to a user given value # $s1 initialized to 0 addi $t2, $zero, 0x1004 #I1 add $t0, $zero, $zero #I2 Loop: bne $t0, $zero, end #I3 slti $t3, $t2, 0x101C #I4 beq $t3, $zero, end #I5 lw $t1, -4($t2) #I6 bne $s0, $t1, lEnd #I7 addi $t0, $t0, 1 #I8 lw $s1, 0($t2) #I9 lEnd: addi $t2, $t2, 8 #I10 beq $zero, $zero, Loop #I11 end: .............. #irrelevant instruction not shown  (a) Givetheinstructionencodinginhexadecimalforthebne $t0, $zero, end and slti $t3, $t2, 0x101C instructions.Opcodefor bne = 0x5,slti = 0xA and registers $t0 to $t7 == $810 to $1510. The register ordering for sltiissimilartolwduringencoding.     [2marks]  (b) GivetheALUSrcandRegDstsignalsforthesltiinstruction.

[2marks]

 (c) Translate instructions #I3 to #I5 into high level programming language equivalent.Usetheregisternameasthevariablename. [2marks]  

Commented [SYJ22]: bne 8, 0, 8 = 000101 01000 00000 0000000000001000 = 0001 0101 0000 0000 0000 0000 0000 1000 = 0x1500 0008 slti 10, 11, 0x101c #note ordering =001010 01010 01011 0001000000011100 =0010 1001 0100 1011 0001000000011100 =0x294B101C Commented [SYJ23]: ALUSrc = 1 (immediate value) RegDst = 0 (Rt) Commented [SYJ24]: while ($t0 == 0 AND $t2 < 0x101c)

(d)Giventhememorymap(addressandcontentinhexadecimal)ontheright,givethe resultin$s1 forthefollowingcases.  i)

$s0is0x1004.[1mark]

ii)

$s0is0x102C.[1mark]

     



Page5of16 

Address 0FFC16

Content 101816

100016

0FFC16

100416

101416

100816

100C16

100C16

102016

101016

100416

101416

102C16

101816

100816

101C16

100016

102016

101416

Commented [SYJ25]: This code is a {key,value} lookup table. -4($t2) is the key 0 ($t2) is the value $s1 = 0x102C Commented [SYJ26]: Key 0x102C cannot be found $s1 = 0

CS2100

10. [10marks]  ThisquestionusesthesamecodefromQ9,reproducedbelowforyourconvenience. # $s0 initialized to a user given value # $s1 initialized to 0 addi $t2, $zero, 0x1004 #I1 add $t0, $zero, $zero #I2 Loop: bne $t0, $zero, end #I3 slti $t3, $t2, 0x101C #I4 beq $t3, $zero, end #I5 lw $t1, -4($t2) #I6 bne $s0, $t1, lEnd #I7 addi $t0, $t0, 1 #I8 lw $s1, 0($t2) #I9 lEnd: addi $t2, $t2, 8 #I10 beq $zero, $zero, Loop #I11 end: .............. #irrelevant instruction not shown  Considerthefollowingexecutionscenario:   

OneiterationfromInstructionsI1toI11 BranchesI3andI5arenottaken. BranchI7istaken.



Forthefollowingparts,totalnumberofcyclesincludesthecyclesneededforthelast instruction(I11)toreachwrite‐back(W)stage. 



a) If there is no mechanism for handling data and control hazards, what is the total numberofcyclesneededbytheexecutionscenario?   [2marks]   b) Supposedataforwardingandearlybranchareused,answerthefollowing: i. InstructionI6isfetchedonwhichcycle? ii. Whatisthetotalcycleneededbytheexecutionscenario? [3marks]   c) Supposedataforwardingandpredict‐takenbranchpredictionisusedwithoutearly branching,answerthefollowing: i. InstructionI6isfetchedonwhichcycle? ii. Whatisthetotalcycleneededbytheexecutionscenario? [3marks]  d) Using the configuration in (c), what is the total cycle needed for the entire execution? The execution starts from I1 and eventually takes the branch at I5. RemembertoincludethecyclesneededforthelastI5toreachwrite‐backstage. [2marks]  Page6of16

Commented [SYJ27]: See working and answers on page 13





CS2100

11. [9marks]  Given below are two equivalent codes for modifying the elements of array A[]. The threearraysA[],B[]andC[]areall32‐bitintegerarrayswith64elements. VersionX:

VersionY:

for (i = 0; i < 64; i = i+2)

for (i = 0; i < 32; i = i+1) {

A[i] = B[i] + C[i];

j = i*2; A[j] = B[j] + C[j];

for (i = 1; i < 64; i = i+2)

A[j+1] = B[j+1] – C[j+1];

A[i] = B[i] - C[i]; }

Furthermore, we know that array A[] is allocated starting at 0x1000DDA0, B[] at 0x1000EE68andC[]at0x1000FF30.Attemptthefollowingquestionsassumingadirect‐ mappedcachewith4blocks,eachblockcontaining4words(eachwordis32‐bit).  (a) GivethecacheindicesforthecacheblocksholdingB[0]andC[4]. [2marks] (b) IgnoringthewriteaccessesofA[],andconsideringonlythereadaccessesonB[] andC[],whatisthetotalcachemissesforcodeversionsXandY? [3marks]  (c) We will now consider the impact of write accesses of A[]. Suppose the cache implements write‐allocate policy, what is the number of cold and conflict cache missesforcodeversionsXandY? [4marks]

Commented [SYJ28]: Cache Tag = 26 bits Cache Index = 2 bits Offset = 4 bits B[0] is at 0x1000EE68 0x6 = 0110 Index = 2 C[4] is at 0x1000FF30 + 4 x 4 = 0x1000FF40 0x4 = 0100 Index = 0



              ~~ENDOFPAPER~~~ (BlankK‐maps,partialstatetableandtimingchartsareprovidedinthenextthreepages.) 

 Page7of16



Commented [SYJ29]: See page 15 for working and answer. Commented [SYJ30]: See page 16 for working and answer.

CS2100

A

B

C

X

A+

B+

C+

0

0

0

0

0

0

1

0

0

0

1

1

0

0

0

1

0

0

1

0

0

1

1

0

0

1

0

0

0

1

0

0

1

1

0

1

1

TB

JC

KC









0









1









0

0























1















0















1

1















0

0

0















1

0

0

1















1

0

1

0















1

0

1

1















1

1

0

0















1

1

0

1















1

1

1

0















1

1

1

1















  DA

C

DA

C



TB

















































B

















A

B A

X

X

C

JC

C

KC

































B







B



A

















A





 X

 Page8of16

X





CS2100

Thispageisforyourroughwork.     

 





























































































 































































































