数字系统设计 - 期末复习与习题解答

DigitalSystemDesignII

数字系统设计2计组习题讲解黄露

Xindian(High-Tech)Building30813516719473eliver8801@Chapter1

1、Introduction：SomeConcepts

2、Performance：SomeParameters

CPUExecutionTimeClockCycle,ClockRateCPIInstructionCountSpeedupRatePerformanceHW2Problem4Chapter21、ISA——InstructionSetArchitecture

2、AssemblyInstructions3、Conversion,TrueForm,ComplementForm,SignandUnsignMIPSISAOperationsHowmany?WhichonesOperandsHowmany?LocationTypesInstructionformatSizeHowmanyformats?RegisterNaming$zerocontainsthehardwiredvalue0$v0,$v1areforresultsandexpressionevaluation$a0-$a3areforarguments$s0,$s1,…$s7areforsavevalues$to,$t1,…$t9arefortemporaryvaluesPseudo-instructionWhatisPseudo-instruction?HowtotransferittoMIPSinstructions?Question1:AboutISASupposethatwemakethefollowingmodifications,dothesemodificationschangetheISA?Answerwithyesorno,andexplainyourreasons.1a.Changingtousing64-bitaddressesfrom32-bitaddresses.

1a.Yes.ThePCregister,andthewidthofallgeneral-purposeregistersmustchange(tohold64-bitaddressesforJR,LW,etc.),whichcan’tbehiddenfromthesoftware.1b.Addingabranch-targetbuffer,insteadofstaticallypredictingPC+4.

1b.No.Branchspeculationisjustpredictingwhichinstructiontofetchnext,anddoesn’taffecttheactualmachinestate(Regfile,Memory).Quiz1.Problem11c.Addingmoreregistersthatusercodecannowaddress.1c.Yes.Addingmoreregisterswouldrequirechanginginstruction,andthusbeachangetotheISA.HW1Problem3AssemblyInstructionsHowtoreadaAssemblyProgram(Sequence)?HowtotransferaCcodeintoAssembly?Howtomodify?Thefollowingcodefragmentprocessesanarrayandproducestwovaluesinregisters$v0and$v1: … …Assumethat:.Thearrayconsistsof5000indexed0through4999.Itsbaseaddressisstoredin$a0.Itssizeinwords,(5000)isstoredin$a1HW1Problem1#$v0=0;#$v1=0;#$t6=0;#$a2=$a1*4;#$t0=0;#$t7=0;outer:#$t4=$a0+$t0;->$t4=addressA[i];#$t4=A[i];#$t5=0;#$t1=0;inner:#$t2=$t1*4;#$t3=$a0+$t2;->$t3=addressA[j];#$t3=A[j];#if(A[i]!=A[j])skip;#$t5=$t5+1;skip:#$t1=$t1+1;#if($t1!=$a1)inner;#if($t5<$t7)#thengotoelsepart;#$v0=$t6;#$v1=$t7;#$t6=$t4;#$t7=$t5;#gotonextelsepart:#if($t5<$v1)#thengotonext;#$v0=$t4;#$v1=$t5;next:#$t0=$t0+4;#if($t0<$a2)outer;Describeinonesentencewhatthiscodedoes.Specifically,whatwillbereturnedin$v0and$v1?Hint:youshouldfirstfocusonthecontroloftheprogram(forandwhileloops,if-then-elsestatements,loopsindicesandexpressionsthatcontrolwhileandifstatements).本程序可以找出5000的数中出现最多次数的两个数。t7存放出现最多的数所出现的次数，t6存放这个数的值；v1存放出现第二多次数的出现次数，v0存放这个数的值b.Whatisthetotalnumberofinstructionsthatareexecutedinthispieceofcode?Brieflyexplainthenumberofinstructionsexecutedineachloop(e.g.Thereare5instructionsthatareexecutedoncebeforeloopouter,thereare7instructionsinloopinnerthatareexecuted10times,etc.).Youneednotcalculatetheexactnumberofinstructions,aswearelookingonlyforaballparkfigure.Youcanmakeaworstcaseassumptionaboutthenumberofinstructionsexecutedincertaincases.b.outer循环外面有6条指令，它们只执行一次。outer循环包括outer标签之下的所有指令。其中，inner标签之前的部分，skip标签中的第3、4句，next标签下的那2句指令，都要循环5000次，skip第5-9行和elsepart的执行次数与数据的分布有关，当所有数据出现的次数相等时，skip第5-9行总是执行，要循环5000次，这是最坏情况。

inner循环包括inner标签开始到skip标签下的第2个指令。其中，第5条指令（addi$t5,$t5,1）会随着数据分布而改变，当所有数据都相等时，这条语句恒执行，于是在最坏情况下，这7条要执行5000*5000次。

下面总结一下，当所有数据都相等时，outer和inner循环都达到最坏情况，总共执行的指令数为：6+（4+7*5000+7+2）*5000=175065006.c.Assumethatthecodefragmentisrunonamachinewitha500MHzclockthatrequiresthefollowingnumberofcyclesforeachinstruction.Intheworstcase,howmanysecondswillittaketoexecutethiscode?c.add,addi,sll,slt一共发生次数为：6+5*5000+4*5000+4*5000*5000=100045006lw一共发生次数为：5000+5000*5000=25005000bne，j一共发生次数为：3*5000+2*5000*5000=50015000则总共有： (2*100045006+5*25005000+3*50015000)/500M=0.953sd.Considerthefollowingtwolinesintheinnerloop: add$t3,$a0,$t2 lw$t3,0($t3)Weneedregister$a0toholdthebaseofthearrayandregister$t1toholdtheindexofthearray.ConsideranarchitecturethatissimilartoMIPSexceptthatthetwolinesofcodeabovecanbecombinedintooneasfollows: lw$t3,$a0+$t2Theaddressingmodethatallowstworegisterstobeaddedtogetheriscalledindexedaddressing.ThisadditionaladdressingmodeisavailableinthePowerPCarchitecture.AssumethatwecanmodifyMIPSarchitecturetoprovideindexedaddressingmode.Thismeansthatforeachdatatransferinstructionthatusesthebaseandindexofanarray,onearithmeticinstructioncanbeeliminated.Unfortunately,toaccommodatethisnewaddressingmode,thecycletimeisincreasedby20%.Intheworstcase,howmanysecondswillittaketoexecutethecodelistedaboveusingthemodifiedMIPSarchitecture?HowmuchfasterorslowercomparedtotheoriginalMIPScode?Assumethatthemodifiedlwinstructionstilltakes5cycles

d.475170012-（2*5000+2)*5000=425160012总cycles数变为425160012，而每个cycle时间提高了20%，因此，总时间为： t=1.2*(425160012/(500*1000000))=1.0204s所以变慢了7%move$t0,$a0sll$t1,$a1,2add$t2,$a0,$t1addi$t3,$zero,1023addi$t4,$zero,1loop:sw$t3,0($t0)sub$t3,$t3,$t4addi$t0,$t0,4slt$t5,$t0,$t2bne$t5,$zero,loopfunc(int*array,intsize){ int*p; inta=1023;for(p=&array[0];p<&array[size];p=p+1,a=a-1)*p=a;}ConverttheCcodetoMIPSassembly.Thereferences‘array’and‘size’ofthefunctionarestoredinregisters$a0and$a1.Quiz1.Problem4Chapter31、Add,Sub,Multiply,Division2、FloatNumber——IEEE754Standrd3、FloatInstructionsHW43.10P225010010111(补码)-105011010110(补码)-42-10511101001(原码)-4211010110(补码)111010011101011010111111(-63)-105-（-42）=-63x=01000111110110000000000000000000twoandy=10110110011000000000000000000000two.Assumingxandyaretwo’scomplement,Whatdecimalnumbersdotheyrepresent?AssumingxandyaresingleprecisionIEEE754floating-pointnumbers.Whatdecimalnumbersdotheyrepresent?Performbinaryfloating-pointmultiplicationx×ybasedonquestion(2).ResultshouldbewritteninIEEE754floating-pointformat.Showeachstepofthecalculation.(1)x符号位为0，对应原码=补码，则 x=2^30+2^26+2^25+2^24+2^23+2^22+2^20+2^19=1205338112y符号位为1，对应原码为11001001101000000000000000000000，则 y=-1*（2^30+2^27+2^24+2^23+2^21）=-1235222528(2)X=[(-1)^0]*(1+2^-1+2^-3+2^-4)*2^(2^7+2^3+2^2+2+1-127)=1.6875*2^16Y=-1.75*2^-19Quiz1.Problem3(3)

x*y=-10.111101*2^-3=-1.0111101*2^-2=-1.0111101*2^（125-127）

inIEEE754: 10111110101111010000000000000000X=1.6875*2^16Y=-1.75*2^-19二进制表示X=1.1011*2^16Y=-1.1100*2^-19Chapter41、SingleCycleCPU:DataPath,Control2、Instructionrealization3、Pipeline:Concept,Principle,Dependence,HazardandItsEliminationSingleCycleCPUDataPathHowtosetup?Howmanytypes?ControlHowmany?LogicrelationInstructionRealizationCombineDataPathandControlWhat’sCrucialPath?LatencyDifference

indifferentinstructionHW34.7P348Sign-extend(原数据高位复制到新数据项多出来的高位)00000000000000000000000000010100Shiftleft-2Instruction[25-0]01100010000000000001010000011000100000000000010100SWRt,20(RS)SWR2,20(R3)[ALUOp1-ALUOp0]=00Instruction[5-0]=010100PC+4

Lookatthecontrolonthedatapathbelow;figureoutwhatinstructionisbeingexecuted.Writethatinstructiononthelinebelow.Quiz1.Problem2PC=PC+4rsInst[15:0]=8Inst[20:16]=2Inst[25:21]=7寄存器Num：2:$v07:$a3搞清楚源操作数与目的操作数addi$v0,$a3,8PipelinePipelineConceptsClockCycleTimeDataPathandControlHazardWhatisStructuralhazard?WhatisDatahazard?WhatisControlhazard?OptimizationorEliminationDataHazard•RAW（写后读）•WAW（写后写）•WAR（读后写）•RAR（读后读）-DependencyWhichkindofdependencedocausehazard?-Elimination——Stalling•WithoutForwarding•WithALU-ALUonlyForwarding•WithFullForwardingWhatistheadvantagebyforwarding?ControlHazard•PC+4•Branches•Jump-CalculatingthenextPCWhichofdocausehazard?-Elimination•stallonbranches•Predictnot-taken(stillPC+4)•PredicttakenQuiz1.Problem5IFIDEXMEMWBPipelineregister180ps100ps170ps220ps60ps10ps1.Eachindividualpipelinestagehassomelatency.Additionally,pipeliningintroducesregistersbetweenstages,andeachoftheseaddsanadditionallatency.Thelatencyisshowninthechartbelow:Assumingtherearenostalls,whatisthespeed-upachievedbypipeliningasingle-cycledatapath?(1)forsingle-cycle,itconsumes: t1=180+100+170+220+60=730psforpipeline,eachstageconsumes: t2=max(180+10,100+10,170+10,220+10,60+10)=230psSpeedup:730/230=3.1742.Forthefollowingcodeexecutedbyafive-stagepipelinedprocessor:Assumethereisnoforwardinginthispipelinedprocessor.Indicateallthedatahazardsandaddnopinstructionstoeliminatethem.Weassumethattheregisterwriteisdoneinthefirsthalfoftheclockcycleandthatregisterreadsaredoneinthesecondhalfofthecycle.L1andL2existRAWhazardfor$2L3andL4existRAWhazardfor$5

指令123456789101112L1IFIDEXMEMWBL2**IFIDEXMEMWBL3IFIDEXMEMWBL4**IFIDEXMEMWBadd$2,$3,$1nopnopsub$4,$2,$0lw$5,110($2)nopnopadd$6,$2,$53.Assumingthepipelinehasfullforwardingsupport.Thenwhichhazard/hazardscanberesolvedbyusingforwardingandwhichcannot?Addnopinstructionstoeliminatethem.thefirstonecanbeeliminated,butthesecondonecan’t add$2,$3,#1 sub$4,$2,$0 lw$5,110($2) nop add$6,$2,$5指令123456789L1IFIDEXMEMWBL2IFIDEXMEMWBL3IFIDEXMEMWBL4*IFIDEXMEMWB4.Wehaveanotherprogramof104instructionsintheformatof“lw,add,lw,add...”Theaddinstructiononlydependsonthelwinstructionrightbeforeit.Thelwinstructiononlydependsontheaddinstructionrightbeforeit,too.WhatwouldbetheCPIwithoutforwarding?lw,nop,nop,add,nop,nop,lw,nop,nop,add….SoCPI=(104+2*104)/104=3指令1234567891011L1IFIDEXMEMWBL2**IFIDEXMEMWBL3**IFIDEXMEMWBL4**IFID指令1234567891011L1IFIDEXMEMWBL2*IFIDEXMEMWBL3IFIDEXMEMWBL4*IFIDEXMEMWB5.WhatwouldbetheactualCPIwithfullforwarding?lw,nop,add,lw,nop,add….SoCPI=(104+0.5*104)/104=1.5HW54.10P350指令1234567891011Swr16,12(r16)IFIDEXMEMWBlwr16,8(r6)IFIDEXMEMWBbeqr5,r4,LabelIFIDEXMEMWBaddr5,r1,r4**IFIDEXMEMWBsltr5,r15,r4IFIDEXMEMWB指令123456789Swr16,12(r6)IFIDEXMEMWBlwr16,8(r6)IFIDEXMEMWBbeqr5,r4,LabelIFIDEXMEMWBaddr5,r1,r4IFIDEXMEMWBsltr5,r15,r4IFIDEXMEMWB指令12345678910Addir7,r6,12IFIDEXWBSwr16,r7IFIDMEMWBAddir7,r6,8IFIDEXWBlwr16,r7IFIDMEMWBbeqr5,r4,LabelIFIDEXWBaddr5,r1,r4IFIDEXWBsltr5,r15,r4IFIDEXWB指令(ID阶段)12345678910Swr16,12(r16)IFIDEXMEMWBlwr16,8(r6)IFIDEXMEMWBbeqr5,r4,LabelIFIDEXMEMWBaddr5,r1,r4*IFIDEXMEMWBsltr5,r15,r4IFIDEXMEMWB指令(EX阶段)1234567891011Swr16,12(r16)IFIDEXMEMWBlwr16,8(r6)IFIDEXMEMWBbeqr5,r4,LabelIFIDEXMEMWBaddr5,r1,r4**IFIDEXMEMWBsltr5,r15,r4IFIDEXMEMWBChapter51、Locality:TemporalLocality,SpatialLocality2、Cache:Concepts,Performance,addressmapping,missorhit,replacement3、VirtualMemory:Concept,TLBCacheAddressesMappingWhatistheTag?WhatistheIndex?Whatistheoffset?PlacementPolicyDirectMappedFullyAssociativeN-waySetAssociativePerformanceEvaluationHitisgreat,Buthowtohandlemisses?AMATReplacementPolicyRANDLRUMRUWhenreplacementhappen?DifferentWritePolicyHit——WriteBack,

WriteThroughMiss——WriteAllocate,NoWriteAllocateHW75.3P4731.2.3.cacheAddr041613223216010243014031001802180000475320496568Index000475004054Hit/missMHHMMMMMHMHMReplaceNNNNNNYYNYNYAddr041613223216010243014031001802180000475320496568Index000475004054Hit/missMHHMMMMMHMHMReplaceNNNNNNYYNYNYIndexTagdata03Mem[3100]42Mem[2180]50Mem[180]70Mem[232]HW85.13P480AddresssofmemoryblockaccessedHit\missEvixtedblockContentscacheblocksafterreferenceSet0Set0Set1set10MMEM[0]2MMEM[0]MEM[2]4M0MEM[4]MEM[2]8M2MEM[4]MEM[8]10M4MEM[10]MEM[8]12M8MEM[10]MEM[12]14M10MEM[14]MEM[12]16M12MEM[14]MEM[16]0M14MEM[1]MEM[16]AddresssofmemoryblockaccessedHit\missEvixtedblockContentscacheblocksafterreferenceSet0Set0Set1set10MMEM[0]2MMEM[0]MEM[2]4M2MEM[0]MEM[4]8M4MEM[0]MEM[8]10M8MEM[0]MEM[10]12M10MEM[0]MEM[12]14M12MEM[0]MEM[14]16M14MEM[0]MEM[16]0HMEM[0]MEM[16]最多命中一次，当且仅当每次第二个块被替换掉AddresssofmemoryblockaccessedHit\missEvixtedblockContentscacheblocksafterreferenceSet0Set0Set1set10MMEM[0]2MMEM[0]MEM[2]4M2MEM[0]MEM[4]8M4MEM[0]MEM[8]10M8MEM[0]MEM[10]12M10MEM[0]MEM[12]14M12MEM[0]MEM[14]16M14MEM[0]MEM[16]0HMEM[0]MEM[16]HW75.7P475Addr318043219188190141814486253Block1902119544957902293126Set121130332212Hit/missMMMHMMHMHMMMTagSetOffset31-54-32-0ADDRSetTAGBLOCKOFFSETHIT/MISS30101M18010220M430151M20100H19111231M8800110M19011230H141110M18110221H441050M18601230M2531031MSet0088Set01243186Set1018044253Set1119014Fullyassociativecache,noindexbitBlocksizeisone-word,noblockoffsetNorepeateda