數(shù)字系統(tǒng)設計 - 期末復習與習題解答

DigitalSystemDesignII

數(shù)字系統(tǒng)設計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的數(shù)中出現(xiàn)最多次數(shù)的兩個數(shù)。t7存放出現(xiàn)最多的數(shù)所出現(xiàn)的次數(shù)，t6存放這個數(shù)的值；v1存放出現(xiàn)第二多次數(shù)的出現(xiàn)次數(shù)，v0存放這個數(shù)的值b.Whatisthetotalnumberofinstructionsthatareexecutedinthispieceofcode?Brieflyexplainthenumberofinstructionsexecutedineachloop(e.g.Thereare5instructionsthatareexecutedoncebeforeloopouter,thereare7instructionsinloopinnerthatareexecuted10times,etc.).Youneednotcalculatetheexactnumberofinstructions,aswearelookingonlyforaballparkfigure.Youcanmakeaworstcaseassumptionaboutthenumberofinstructionsexecutedincertaincases.b.outer循環(huán)外面有6條指令，它們只執(zhí)行一次。outer循環(huán)包括outer標簽之下的所有指令。其中，inner標簽之前的部分，skip標簽中的第3、4句，next標簽下的那2句指令，都要循環(huán)5000次，skip第5-9行和elsepart的執(zhí)行次數(shù)與數(shù)據(jù)的分布有關，當所有數(shù)據(jù)出現(xiàn)的次數(shù)相等時，skip第5-9行總是執(zhí)行，要循環(huán)5000次，這是最壞情況。

inner循環(huán)包括inner標簽開始到skip標簽下的第2個指令。其中，第5條指令（addi$t5,$t5,1）會隨著數(shù)據(jù)分布而改變，當所有數(shù)據(jù)都相等時，這條語句恒執(zhí)行，于是在最壞情況下，這7條要執(zhí)行5000*5000次。

下面總結一下，當所有數(shù)據(jù)都相等時，outer和inner循環(huán)都達到最壞情況，總共執(zhí)行的指令數(shù)為：6+（4+7*5000+7+2）*5000=175065006.c.Assumethatthecodefragmentisrunonamachinewitha500MHzclockthatrequiresthefollowingnumberofcyclesforeachinstruction.Intheworstcase,howmanysecondswillittaketoexecutethiscode?c.add,addi,sll,slt一共發(fā)生次數(shù)為：6+5*5000+4*5000+4*5000*5000=100045006lw一共發(fā)生次數(shù)為：5000+5000*5000=25005000bne，j一共發(fā)生次數(shù)為：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數(shù)變?yōu)?25160012，而每個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(原數(shù)據(jù)高位復制到新數(shù)據(jù)項多出來的高位)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搞清楚源操作數(shù)與目的操作數(shù)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“l(fā)w,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