多级存储器练习

Spring20026.823ComputerSystemArchitectureDatapathforDLXSpring2002ProblemSet#2Studentsareallowedtocollaborateingroupsofupto3people.Agrouphandsinonlyonecopyofthesolutiontoaproblemset.Homeworkassignmentsaredueatthebeginningofclassonthesuedate.Tofacilitategrading,eachproblemmustbestapledseparately.Homeworkwillnotbeacceptedoncesolutionsarehandedout.Problem1:MicroprogrammingandBus-BasedArchitecturesProblem1.AHowmanycyclesdoesittaketoexecutethefollowinginstructionsinthemicrocodedDLXmachine?UsethestatesandcontrolpointsfromDLX-Controller-2andassumeMemorywillnotassertitsbusysingal.lilStTLlCtlOUCyclesADDR3,R2,R1ADDIR2,R1,#4LW Rl,0(R2)BEGSRlflabel#(R1==0)BEG3Rl,label#(R1!=0)J labelJR R1JALlabelJALRR1Whichinstructiontakesthemostcyclestoexecute?Whichinstructiontakesthefewestcyclestoexecute?Problem1.BBenBitdiddleneedstocomputefactorialsforsmallnumbers.RealizingthereisnomultiplyinstructioninthemicrocodedDLXmachine,heusesthefollowingcodetocalculatethefactorialofanunsignednumbern.result.=1;for(iresult.=1;for(i=0;i<n; {二wrr一匸for(jresult;=0;jresult<i；j-+)ten'：：'；ThevariablesI,j,n,temp,andresultareunsigned32-bitvalues.WritetheDLXassemblythatimplementsBen'factorialcode.UseonlytheDLZinstructionsthatcanbeexecutedonthemicrocodedDLXmachine(ALU,ALUi,LW,SW,J,JAL,JR,JALR,BENQ,andBENS).ThemicrocodedDLXmachinedoesnothavetobepreserved.HowmanyDLXinstructionsareexecutedtocalculateafactorial?Howmanycyclesdoesittaketocalculateafactorial?Again,usethestatesandcontrolpointsfromDLX-Controller-2andassumeMemorywillnotassertitsbusysignal.Fh匚tenalCycles013NProblem1.CAlyssaP.HackertellsBenthathisfactorialcodewillrunmuchfasterifheimplementsanunsignedmultiplyinstructioninthemicrocodedDLXmachine.ThenBencanreplacetheinnerloopinstructionswiththenewmultiplyinstruction.ThedetailsofAlyssa'snewproposedunsignedmultiplyinstructionare:▼Rsl(Rs▼Rsl(Rs2times)ThevalueofRs1isaddedRs2timesandtheresultstoredintoRd.Rs1andRs2aretreatedasunsigned32-bitvalues.IfRs2orRs1is0,thentheresultofRdwillalsobe0.TheformatoftheMULUinstructionisR-type.InordertobeabletowritemicrocodeforMULU,Alyssaaddsanadditionalregister,TO(33),totheregisterfile.Thisregister,likethePCregister,isnotvisibletotheprogrammer.Shealsoadds33asaninputtotheregisterfilemultiplexer.UsingWorksheet1,writemicrocodetoimplementAlyssa 'snewunsignedmultiplyinstruction.InWorksheet1,therepresentationofthenextstateisdifferentfromwhatwaspresentedinlecture.Thelasttwocolumnsrepresentsa2-bitfieldwithfourpossiblevalues:N,J,Z,andD.IUBrisN(next),thenthenextstateissimply(currentstate=1).IfitisJ(jump),thenthenextstateisunconditionallythestatespecifiedintheNextStatecolumn(i.e.,it uhcontiitionalmicrobranch).IfitisZ(branch-if-zero),thenthenextstatedependsonthevalueoftheAL'zerooutputsignal(i.e.,it'aconditionalmicrobranch).Ifzeroisasserted(==1),thenthenextstateisthatspecifiedintheNextStatecolumn,otherwise,itis(currentstate+1).UBisD(dispatch),thentheFSMlooksattheopcodeandfunctionfieldsintheIRandgoesintothecorrespondingstate.Forthisproblemset,weassumethatthedispatchgoestothelabeled(DLX-instruction-name+”.Forexample,iftheinstructionintheIRisSW,thenthedispatchwillgotostateSW0.TheALUperformsoperationsspecifiedbytheALUOp,whichisdeterminedbytheALUcontrollogicblock.AssumetheALUcanperformthefollowingoperations:

ALUOpALUResultOutputCOPYAACOPYBBrINCA1A+lDECA1A-l1INCA4A+4DECA4A-4ADDA+BSUBA-BHowmanycyclesdoesitfortheMULUinstructionfordifferentvaluesofRs2?Rs2Cycles013NProblem1.DWithAlyssa'snewunsignedmultiplyinstruction,Beneliminatestheinnerloopofhisoriginalfactorialcodeandsimplifiesittothefollowing.result=1;for(i=1;1<=n;i++}{result-result*1；}HelpBenwriteDLXassemblycodetoimplementfactorialusingthenewMULUinstruction.Again,useR1fornandR2forresult.Attheendofyourcode,R2mustcontainthecorrectvalue.Youdonothavetopreservethevaluesofanyotherregisters.HowmanyDLXinstructionsareexecutedtocalculateafactorial?Howmanycyclesdoesittaketocalculateafactorial?Again,assumeMemorywillnotassertitsbusysignal.FactorialCycles0123NProblem1.ECombiningamicrocontrollerandtheDLXbus-baseddatapath(L4-5)givesusacompleteworkingcomputerthatcanrunasubsetoftheDLXISA.Besidesrequiringmuchmorememory,AlyssatellsBenanotherreasonwhyusingtheoriginalDLXMicrocontroller(L4-9)wasavadidea.AmachinewiththeoriginalcontrollerwouldhaveamuchIongercycletimethanamachineusingthesecondmicrocontroller(L4-15).Benca'understandwhythisistrue.BelowarethedelaysofthehardwarepartsusedtoimplementtheDLXbus-baseddatapachandthefirstversionoftheDLXMicrocontroller(L4-9).Lehi?-紀mpmiwofregistersIR.A:B.N1A,pPCte-q-clock-to-qtmieofregistersIR,AB,MA.pPCtAiu一timeALUtakestogenerateresultmidzerot„ceud-delayofasignextendertgcc—delayofamultiplexertt-,—delayfromwhendataisrittentobustowhenitbecomesstablet亦為花—delayrofarn-UatebufferCrf-delayoftheregisterfileMm-delayofmemory-trom-delayoftheROMtALV_c0EtioL-delayforALUControlAssumethattALU,tROM,tMEN,havecomparablevaluesandthatthesedelaysarebiggerthanthedelaysforothercomponents.Usingthefirstversionofthemicrocontroller,whichmicrocodeinstructioninvokesthecriticalpathofthemachine?Describethecriticalpath.WhatistheminimumclockperiodthatthecompleteDLXbus-basedmachinecanrunat?AssumeMemorywillnotassertitsbusysignal.Problem2:PipelineHackingInspiredbyhissuccesswiththeMACCinstructioninthelastproblemset,BenBitdiddlecomesupwiththefollowingnewinstructionformatcalledBIF(forBen'InstructionFormat)thathewantstoaddtotheDLXISA:opcodelrf1rf2opcode2rf4rf565 5 65 5Thesemanticsofthenewinstructionwouldbethis:rf5<-(=floplWhereop1andop2areALUoperations.Forexample,ADDR1,R2:ADDR3,R4wouldbecomputedasfollows:RT<-(R1+R2)+R3Toimplementthenewinstructionformat,BendecidestoaddanALUtothememoryphaseofthepipelined,fully-bypassedimplementationoftheDLXdatapathdiscussedinlecture.Old-styleDLXinstructionswouldstillusetheALUintheexecutephasewhileBIFinstructionswouldusebothALUs.ThefirstALUinthememorypahse.Thenewpipelinewouldlooklikethis:IFIDEXMAWBFetchphaseDecodeandregisterfetchphaseExecutephase withonfilialALUMemoryphase withnewALUWrite-backphaseInaddition,theregisterfileintheolddatapathisreplacedwitharegisterfilewiththreereadportsandonewriteportsothatallthreeoperandscanbereadatthesametime.Problem2.AGiveacodeexamplethatshowshowtoycangetbetterperformaneeusingBIFinstructions.Provideboththeoriginalols-styleDLX,codeandthecodethatusestheBIFinstructions.Theoriginalcodeshouldcontainatleastsixinstructions.WhatisthemaximumpossibleimprovementinperformaneeusingBIFinstructions?Problem2.BShowalldatahazardsthatcancausestallsandprovideacodeexampleforeachcase.Youshouldconsiderbothold-styleDLXinstructionsandinstructionsusingBensnewformat.Youmayassumethatthedatapathisfully-bypassed.Donotconsiderjumpsorbranchesfornow.Stillignoringjumpsandbranches,howperformaneechangeifnon-BIFinstructionsusedthenewALUintheMAphaseinstasdoftheoriginalALUintheexecutephase?Problem2.CWritetheequationsforws,we,re1,re2forthenewdatapathwithnon-BIFinstructionsusingtheoriginalALUintheexecutephase.Writethestallsignalusingws,we,re1,andre2.Youmayneedothersignals.Thesignalsfortheoriginaldatapathareprovidedhereforyourconvenience.Again,donotconsiderjumpsorbranchesfornow.ws二caseopcodeALU => rf3ALUi’LW刁rf2JAL.JALRnR31we二caseopcodeALUtALUi,LW (wsRO)JALrJALR ron… noffrel二caseopcodeALU.ALUi„LW.SW.BEQZ,J尺JALRnonJ.JAL 0offre2=caseopcodeALU.SW =>on( (offcstallstall=(rfID=wsE)((opcodeE=LWE)((wsE(R0)(relD+(rf2D=w5E)((opcodeE=LWE)((w^E(R0)(re2DProblem2.DNowconsiderjumpsandbranches.Whatadditionalhazardscanoccur?Giveanexampleforeachcase.Withthenewinstructionformat,Benthinksthatwecanspeedupconditionalbranchesifweallowaninstructionthatcombinesthecomparewiththebranch.Forexample,5LTR1.K21 labelwouldmean:il(R1<R2)thenbranchtoLabelThefirstinstruction(inthisexample,theSLTinstruction)wouldbeperformedontheSLUintheEXpahse.Theresult(a0or1),insteadofbeingwrittentotheregisterfile,wouldbepassedtotheMAphasewherethezerotestwouldbeperformedonthenewALU.Howmanydelayslotswillthistypeofinstructionrequiretoavoidanystalls?精品文档Howcouldyoureducethenumberofdelayslotsthatareneeded,withoutintroducinganynewstallconditionsorkillinginstructionsinthepipeline?Foreachcasethatyouconsider,arguewhateffectitwillhaveontheclockperiod.Eachcaseshouldcorrespondtoanimplementationwithadifferentnumberofdelayslots.Giventheoptionsyouinvestigatedabove,argueinafewsentenceswhichoftheseoptionsisthebest.Considerdelayslots,stalls,circuitsize,andclockperiod.Problem2.EBenfindsthattheadditionalreadportintheregisterfileisincreasingthelengthofthecriticalpathintheprocessor,andthattheycannotclockthenewdatapathatashighaspeedastheoriginal.Totryandsolvetheproblem,heisgoingtotryandusetheoriginalregisterfile.Sincetheoriginalregisterfileonlyhastworeadports,onlytwooftheoperandscanbereadintheIDphase.ThethirdoperandisgoingtobereadintheEXphase,inparallelwiththefirstALUoperation.Whatotherchangesareneededtomakethisschemework?Howdothesechangesaffecttheperformaneeoftheprocessor?AlyssathinksthatBencansolvehisproblembyaddingasecondregisterfile,identicaltothefirst.Howwouldthisschemework?HowdoestheperformanceofAly'aBchemecompatrtothetwothatBentried?Problem2.FWiththenewBIFinstructions,howwillcodesizechange?Willthishaveaneffectonperformanee?Problem3:CacheAccess-Time&PerformanceBenistryingtodeterminethebestcacheconfigurationforanewprocessor.Heknowshowtobuildthreekindsofcaches:direct-mappedcaches,2-wayser-associativecaches,andsmallfullyassociativecaches.Thegoalistofindthebestcacheconfigurationwiththegivenbuildingblocks.Problem3.ASinceheonlyknowshowtobuildverysmallfullyassociativecaches,Bendecidedtouseeitherdirect-mappedor2-wayset-associativeasthebasiccacheconfiguration.Hewantstoknowhowthesetwodifferentconfigurationsaffecttheclockspeedandthecachemiss-rate,andchoosetheonethatprovidesbetterperformaneeintermsofaveragelatencyforaload.Problem3.AAccesstimeiDMThefollowingdiagramshowshowadirect-mappedcacheisorganized.Toreadawordfromthecache,theinputaddressissetbytheprocessor.Thentheindexportionoftheaddressisdecodedtoaccesstheproperrowinthetagmemoryarrayandinthedatamemoryarray.Theselectedtagiscomparedtothetagportionoftheinputaddresstodetermineiftheaccessisahitornot.Atthesametime,thecorrespondingcacheblockisreadandtheproperlineidselectedthroughaMUX.Inthememoryarray,eachrowcorrespondstoarowinthecache.Forexample,arowinthetagmemoryarraycontainsonetagandtwostatusbits(validanddirty)forthecacheline.Fordirect-mappedcaches,arowinthedataarrayholdsonecacheline.Nowwewanttocomputetheaccesstimeofthecache.Assumea32-KBcachewith8-word(32-byte)cachelines.Theaddressis32bits,andtwoLSBoftheaddressisignoredsinceacacheaccessisword-aligned.Thedataoutputisalso32bits,andtheMUXselectsonewordoutoftheeightwordsinacacheline.UsingthhedelayequationsgiveninTable3-1,fillinthecolumnforthedirect=mapped(DM)cacheinTable3-1.Intheequationforthedataoutputdriver,associativity”referstotheassociativityofthecache(1ordirect-mappedcaches,AforA-wayset-associativecaches).ComponentDelayequation(ps)DM(ps)SA(ps)Decoder200k(#ofindexbits)—1000TagDataMeniorsrarray200xlogj ofrows)-200xlog：侍ofbirsmarow)+1000TagDaraComparator200x(#oftagbits)+1000[N-to-1MUX500xlog2N+1000BufFerdriver2000D自祐outputdriver500<(as5ociari\iiv)+1000Validoutput1000Table3-1:DthyofeachCacheComponentWhatidthecriticalpathofthisdirect-mappedcacheforacacheread?Whatistheaccesstimeofthecache(thedelayofthecriticalpath)?Tocomputetheaccesstime,assumethatagate(AND,OR)delayis500(ps).IftheCPUclockis150MHz,howmanyCPUcyclesdoesacacheaccesstake?Problem3.B Accesstime:SATheimplementationofa2-wayset-associativecacheisshowninthefollowingdiagram.Theindexpartoftheinputaddressisagainusedtofindtheproperrowinthedatamemoryarrayandthetagmemoryarray.Inthiscase,however,eachrowcorrespondstotwocachelines(onecacheset).Arowinthedatamemoryholdstwocachelines(for32-bytescachelines,64bytes),andarowinthetagmemoryarraycontainstwotagsandstatusbitsforthosetags(2bitspercacheline).Thetagmemoryandthedatamemoryareaccessedinparallel,buttheoutputdatadriverisenabledonlyifthereisacachehit.Assumethetotalcachesizeis32-KB(eachwayis16-KB)andallotherparameters(suchastheinputaddress,cacheline,etc.)arethesameaspart3.A.Computethedelayofeachcomponentandfillinthecolumnfora2-wayset=associativecacheinTable3-1.Whatisthecriticalpathofthe2-wayset-associativecache?Whatistheaccesstimeofthecache(thedelayofthecriticalpath)?Whatisthemainreasonthatthe2-wayset-associativecacheisslowerthanthedirect-mappedcache?IftheCPUclockis150MHz,howmanyCPUxyxlesdoesacacheaccesstake?

InputAddressProblem3.CMiss-rateanalysisInputAddressProblem3.CNowBenisstudyingtheeffectofset-associativityonthecacheperformanee.Sincehenowknowstheaccesstimeofeachconfiguration,hewantstoknowthemiss=rateofeachone.Forthemiss-rateanalysis,Benisconsideringtwosmallcaches:adirect=mappedcachewith4lineswith16bytes/line,anda2-waqyset-associativecache,usingaleastrecentlyusedreplacementpolicy,with4lineswith16bytes/line.Benteststhecachebyaccessingthefollowingsequeneeifhexadecimalbyteaddress,startingwithemptycaches.Completethefollowingtablesforboththedirect-mappedcacheandthe2-wayset-associativecacheshowingtheprogressionofcachecontainsasaccessesoccur(inthetable,my”=