会员注册 | 登录 | 微信快捷登录 支付宝快捷登录 QQ登录 微博登录 | 帮助中心 人人文库renrendoc.com美如初恋!
站内搜索 百度文库

热门搜索: 直缝焊接机 矿井提升机 循环球式转向器图纸 机器人手爪发展史 管道机器人dwg 动平衡试验台设计

18-A Study of Branch Prediction Strategies.pdf18-A Study of Branch Prediction Strategies.pdf -- 5 元

宽屏显示 收藏 分享

资源预览需要最新版本的Flash Player支持。
您尚未安装或版本过低,建议您

ASTUDYOFBRANCHPREDICTIONSTRATEGIESJAMESE.SMITHControlDataCorporationArdenHills.MinnesotaABSTRACTInhighperformancecomputersystems.performancelossesduetoconditionalbranchinstructronscanbeminrmizedbypredictingabranchoutcomeandfetching,decoding,and/orissuingsubsequentinstructionsbeforetheactualoutcomeisknown.Thispaperdiscussesbranchpredictionstrategieswrththegoalofmaxtmizingpredictionaccuracy.First.currentlyusedtechniquesarediscussedandanalyzedusinginstructiontmcedata.Then,newtechniquesareproposedandareshowntoprovidegreateraccuracyandmoreflexibilityatlowcost.INTRODUCTIONItiswellknown13,10thatInahighlyparallelcomputersystem,branchinstructionscanbreakthesmoothflowofinstructionfetchingandexecution.Thisresultsindelay,becauseabranchthatistakenchangesthelocationofinstructionfetchesandbecausetheissuingofinstructionsmustoftenwaituntilconditionalbranchdecisionsaremade.Toreducedelay,onecanattempttopredictthedirectionthatabranchinstructionwilltakeandbeginfetching,decoding,orevenissuinginstructionsbeforethebranchdecisionismade.Unfortunately,awrongpredictionmayleadtomoredelayif,forexample,instructionsonthecorrectbranchpathneedtobefetchedorpartiallyexecutedinstructions0,thewrongpathneedtobepurged.Thedisparitybetweenthedelayforacorrectlypredictedbranchandanincorrectlypredictedbranchpointstotheneedforaccuratebranchpredictionstrategies.Thispaperdiscussesbranchpredictionstrategieswiththegoalofmaximizingthelikelihoodofcorrectlypredictingtheoutcomeofabranch.First.previouslysuggestedbranchpredictiontechniquesarediscussed.Owingtothelargenumberofvariationsandconfigurations,onlyafewrepresentativestrategieshavebeensingledoutfordetailedstudy,althoughseveralarementioned.Then,newtechniquesareproposedthatprovidemoreaccuracy,lesscost,andmoreflexibilitythanmethodsusedcurrently.Becauseofthewidevariationinbranchingbehaviorbetweendifferentapplications,differentprogramminglanguages,andevenindividualprograms,thereisnogoodanalyticmodelforstudyingbranchprediction.Forthisreason,weusedinstructiontracedatatomeasureexperimentallytheaccuracyofbranchpredictionstrategies.Originally,tenFORTRANprograms,primarilyscientific,werechosen.Itwasfound,however,thatseveralwereheavilydominatedbyinnerloops,whichmadethemverypredictablebyeverystrategyconsidered.Twoprograms,SC12andADVAN,werechosenfromthisinnerloopdominatedclass.Fourotherprogramswerenotasheavilydominatedbyinnerloopsandwerelesspredictable.Allwerechosenforthestudy.ThesixFORTRANprogramsusedinthisstudywere1.ADVANCalculatesthesolutionofthreesimultaneouspartialdifferentialequations2.SCl23.SINCOSPerformsmatrixinversionConvertsaseriesofpointsfrompolartoCartesiancoordinates4.SORTSTSortsalistof10,DDOintegersusingtheshellsortalgorithm95.GIBSONAnartificialprogramthatcompilestoinstructionsthatroughlysatisfythesocalledGIBSONmix56.TBLLNKProcessesalinkedlistandcontainsavarietyofconditionalbranchesTheprogramswerecompiledforaCDCCYBEB170architecture.NotethatotherthanADVANandSC12.thetestprogramswerechosenfortheirunpredictability.andthatamoretypicalscientificmixwouldcontainmoreprogramslikeADVANandSCl2.0149711llBl/oooO/O135.75Q1981IEEE202Becauseofthemethodusedforevaluatingpredictionstrategres,anyconclusionsregardingtheirrelativeperformancemustbeconsideredinlightoftheapplicationareaandthelanguageusedhere.Nevertheless,thebasicconceptsandthestrategiesareofbroaderInterest,becauseitisrelativelystraightforwardtogenerateinstructiontracesandtomeasurepredictionaccuracyforotherapplicationsorlanguages.ResultspublishedpreviouslyinthisareaappearinShustek6,whousedinstructiontracedatatoevaluatestrategiesfortheIBMSystem360/370architecture.1bbettdescribedtheinstructionpipelineoftheMU5computerandgaveexperimentalresultsforaparticularbranchpredictionstrategy.ArathersophisticatedbranchpredictorhasbeendescribedfortheSlprocessor,sbutasofthiswriting,noinformationappearstohavebeenpublishedregardingitsaccuracy.Branchpredictionstrategieshavealsobeenusedinotherhighperformanceprocessors,but,again,experimentalresultshavenotbeenpublished.Ourstudybeginsinthenextsection,withtwobranchpredictionstrategiesthatareoftensuggested.Thesestrategiesindicatethesuccessthatcanreasonablybeexpected.Theyalsointroduceconceptsandterminologyusedinthispaper.Strategiesaredividedintotwobasiccategories,dependingonwhetherornotpasthistorywasusedformakingaprediction.Insubsequentsections,strategiesbelongingtoeachofthecategoriesarediscussed,andfurtherrefinementsintendedtoreducecostandincreaseaccuracyarepresented.ievelsofconfidenceareattachedtobranchpredictionstominimizedelaywhentherearevaryingdegreestowhichbranchoutcomescanbeanticipatedforexample,prefetchinginstructionsisonedegree,preissuingthemisanother.Conclusionsaregiveninthefinalsection.TWOPRELIMINARYPREDICTIONSTRATEGIESBranchinstructionstestaconditionspecifiedbytheinstruction.Iftheconditionistrue,thebranchistakeninstructionexecutionbeginsatthetargetaddressspecifiedbytheinstruction.Iftheconditionisfalse,thebranchisnottaken,andinstructionexecutioncontinueswiththeinstructionsequentiallyfollowingthebranchinstruction.Anunconditionalbranchhasaconditionthatisalwaystruetheusualcaseorisalwaysfalseeffectively,apass.Becauseunconditionalbranchestypicallyarespecialcasesofconditionalbranchesandusethesameoperationcodes,wedidnotdistinguishthemwhengatheringstatistics,andhence,unconditionalbrancheswereincluded.Astraightforwardmethodforbranchpredictionistopredrctthatbranchesareeitheralwaystakenoralwaysnottaken.Becausemostunconditionalbranchesarealwaystaken,andloopsaretermrnatedwithbranchesthat,aretakentothetopoftheloop,predictingthatallbranchesaretakenresultstypicallyinasuccessrateofover50.Strategy1lPredictthatallbrancheswillbetaken.Figure1summarizestheresultsofusingstrategy1onthesixFORTRANbenchmarks.FromFigure1,itisevidentthatthemajorityofbranchesaretaken,althoughthesuccessratesvarywidelyfromprogramtoprogram.Thispointstoonefactorthatmustbeconsideredwhenevaluatingpredictionstrategiesprogramsensitivity.Thealgorithmbeingprogrammed,aswellastheprogrammerandthecompiler,caninfluencethestructureoftheprogramand,consequently,thepercentageofbranchesthataretaken.Highprogramsensitivitycanleadtowidelydifferentpredictionaccuracies.This,inturn,canresultinsignificantdifferencesinprogramperformancethatmaybedifficultfortheprogrammerofahighlevellanguagetoanticipate.Strategy1alwaysmakesthesamepredictioneverytimeabranchinstructionisencountered.Becauseofthis,strategy1iscalledsfafic.Ithasbeenobservedanddocumented,6however,thatthelikelihoodofaconditionalbranchinstructionataparticularlocationbeingtakenishighlydependentonthewaythesamebranchwasdecidedpreviously.Thisleadstodynamicpredictionstrategiesinwhichthepredictionvaries,basedonbranchhistory.Strategy2lPredictthatabranchwillbedecidedthesamewayasitwasonitslastexecution.Ifithasnotbeenpreviouslyexecuted,predictthatitwillbetaken.TheresultsFigure2ofusingstrategy2,indicatethatstrategy2generallyprovidesbetteraccuracythanstrategy1.Unfortunately,strategy2isnotphysicallyrealizable,becausetheoretically,thereisnoboundon203thenumberonrndrvidualbranchrnstructronsthataprogrammaycontain.Inpractice.however,itmaybepossrbletorecordthehistoryofalimitednumberofpastbranchessuchstrategresarediscussedinasubsequentsectron.Strategies1and2providestandardsforjudgingotherbranchpredictionstrategres.Strategy1issimpleandinexpensivetoimplement,andanystrategythatisseriouslybeingconsideredforuseshouldperformatleastatthesamelevelasstrategy1.Strategy2iswidelyrecognizedasbeingaccurate,andifafeasiblestrategycomesclosetoorexceedstheaccuracyofstrategy2.thestrategyisaboutasgoodascanreasonablybeexpected.Strategy1isapparentlymoreprogramsensitivethanstrategy2.Evidenceofthisisthewidevariationinaccuracyforstrategy1andthemuchnarrowervariationforstrategy2Figures1and2.Strategy2hasakindofsecondorderprogramsensitivity,however,inthatabranchthathasnotpreviouslybeenexecutedispredictedtobetaken.Lowerprogramsensitivityfordynamicpredictionstrategiesistypical,asresultsthroughoutthispapershow.Finally,itisinterestingthatoneaspectofbranchbehaviorleadsoccasionallytobetteraccuracywithstrategy1thanstrategy2.Often,aparticularbranchinstructionispredominatelydecidedonewayforexample,aconditionalbranchthatterminatesaloopismostoftentaken.Sometimes,however,itisdecidedtheotherwaywhenfallingoutoftheloop.Theseanomalousdecisions,aretreateddifferentlybystrategies1and2.Strategy1,ifitisbeingusedonabranchthatismostoftentaken,leadstooneincorrectpredictionforeachanomalousnottakendecision.Strategy2leadstotwoincorrectpredictionsonefortheanomalousdecisionandoneforthesubsequentbranchdecision.Thehandlingofanomalousdecisionsexplainsthoseinstancesinwhichstretegy1outperformsstrategy2andindicatesthattheremayexistsomestrategiesthatconsistentlyexceedthesuccessrateofstrategy2.STATICPREDICTIONSTRATEGIESStmtegy1alwayspredictthatabranchistakenanditsconversealwayspredictthatabranchisnottakenaretwoexamplesofstaticpredictionstrategies.Afurtherrefinementofstrategy1istomakeapredictionbasedonthetypeofbranch,determined,forexample,byexaminingtheoperationcode.ThisisthestrategyusedinsomeoftheIBMSystem360/370models9andattemptstoexplortprogramsensruvmesbyobservrng,forexample,thatcertainbranchtypesareusedtoterminateloops,whileothersareusedinIFTHENELSEtypeconstructs.Strategyla.Predictthatallbrancheswithcertainoperationcodeswillbetakenpredictthattheotherswillnotbetaken.ThesixCYBER170FORTRANprogramswereexamined,anditwasfoundthatbranchifnegative,bmnchifequal,andbranchifgreaterthanorequalareusuallytaken,sotheyarealwayspredictedtobetaken.Otheroperationcodesarealwayspredictedtobenottaken.Thisstrategyissomewhattunedtothesixbenchmarks,becauseonlythebenchmarkswereanalyzedtodeterminewhichopcodesshouldbepredictedtobetaken.Forthisreason,theresultsforstrategylamaybeslightlyoptimistic.Figure3showstheresultsforstrategylawhenitwasappliedtotheCY170programs.Generally,greateraccuracywasachievedwithstrategylathanwithstrategy1.ThelargestincreasewasintheGIBSONprograminwhichthepredictionaccuracywasimprovedfrom65.4to98.5.TheonlyprogramshowingadecreaseinaccuracywastheSINCOSprograminwhichtherewasadropfrom80.2to65.7.ThechangesinboththeGIBSONandSINCOSprogramscanbeattributedtopredictingthatbranchifpluswasnottaken.Ifithadbeenpredictedastaken,theaccuracyoftheGIBSONprogramwouldhavedroppednearlytoitsoriginalvalue,andtheaccuracyoftheSINCOSprogramwouldhaverisennearlytoitsoriginalvalue.Otherstaticstrategiesarepossible.Forexample,predictionsbasedonthedirectionofthepotentialbmnchoronthedistancetothebranchtargetcanbemade.Followingisadetaileddescriptionofoneofthesestrategies.Strategy3.Predictthatallbackwardbranchestowardloweraddresseswillbetakenpredictthatallforwardbmncheswillnotbetaken.Thethoughtbehindstrategy3isthatloopsareterminatedwithbackwardbranches,andifallloop204branchesarecorrectlypredicted.theOVaraIlaccuracywillbehrgh.Figure4rndrcatesthatstrategy3oftenworkedwell,somehmesexceedingstrategy2probablybecauseoftheanomalousdecisioncase.Thereis,however,oneprogramInwhichitsperformancewaspoorintheSINCOSprogram,theaccuracyforstrategy3wasabout35.Thisindicatesthatprogramsensitivityissignificantandthatperformancecansufferconsiderablyforsomeprograms.Adisadvantageofstrategy3,andofotherstrategiesusingthetargetaddress,isthatthetargetaddressmayneedtobecomputedorcomparedwiththeprogramcounterbeforeapredictioncanbemake.Thistendstomakethepredictionprocessslowerthanforotherstrategies.DYNAMICPREDICTIONSTRATEGIESSomestrategiesbasepredictionsonpastbranchhistory.Strategy2isanidealizedstrategyofthistype,becauseitassumesknowledgeofthehistoryofallbranchinstructrons.Thestrategiesdiscussedinthissectionareactuallyrealizable,becausetheyuseboundedtablestorecordalimitedamountofpastbranchhistory.Branchhistorycanbeusedinseveralwaystomakeabranchprediction.Onepossibilityistousetheoutcomeofthemostrecentexecutionofthebranchinstructionthisisdonebystrategy2.Anotherpossibilityistousemorethanoneofthemorerecentexecutionstopredictaccordingtothewayamajorityofthemweredecidedthisisdonebystrategy7.Athirdpossibilityistouseonlythefirstexecutionofthebranchinstructionasaguideastrategyofthistype,althoughaccurate,hasbeenfoundtobeslightlylessaccuratethanotherdynamicstrategies.First,strategiesareconsideredthatbasetheirpredictionsonthemostrecentbranchexecutionstrategy2.Themoststraightforwardstrategyistouseanassociativememorythatcontainstheaddressesofthenmostrecentbranchinstructionsandabitindicatingwhetherthebranchwastakenornottaken.Thememoryisaccessedwiththeaddressofthebranchinstructiontobepredicted,andthetakenornottakenbitisusedtomaketheprediction.Ifabranchinstructionisnotfoundinthetable,twoissuesmustbeconsidered1thepredictionthatistobemade,and2thetableentrythatshouldbereplacedtomakeroomforthenewbranchinstruction.First,ifabranchInstructIonISnotinthetable.somestaticstrategymustberevertedtoforadefaultprediction.AgoodchoiceIStopredictthatthebranchIStakenasInstrategy2.Amorecomplexdefaultstrategycouldbeusedstrategyla,forexample,butusingthesimpleralwayspredicttakenstrategyhasapositivesideeffect.Inparticular,onlybranchinstructronsthatarenottakenneedtobeputintothetablethen,theexistenceofabranchinthetableimpliesitwaspreviouslynottaken.Branchesthatwererecentlytakenaregiventheproperpredictionbydefault.Onebitofmemoryissaved,butmoreimportantly,historiesofmorebranchinstructionsareeffectivelyremembered.Forexample,iftwooutoftheeightmostrecentbranchinstructionsexecutedarenottaken,thenalleightconsumeonlytwotableentries,althoughallarepredictedtohavethesameoutcomeasontheirpreviousexecutions.Adualstrategyistouseadefaultpredictionofbranchnottakenandtomaintainatableofbranchesmostrecentlytaken.Becausemostbranchinstructionsaretaken,however,thisstrategyisgenerallylessaccurate.Asfarasreplacementstrategies,firstinfirstoutFIFOandleastrecentlyusedLRUseemtobetworeasonablealternatives.Fortheapplicationhere,inwhichthesequenceofbranchinstructionstendstobeperiodicbecauseoftheiterativestructureofmostprograms,thereisactuallylittledifferencebetweentheFIFOandLRUstrategiesasfaraspredictionaccuracy.TheLRUstrategydoesappeartobemorecompatiblewiththeschemementionedpreviouslyinwhichonlybranchesthatwerenottakenarerecorded.Then,ifabranchinthetableistaken,itispurgedfromthetable,andthattablelocationisrecordedasbeingleastrecentlyused.Abranchthatistakensubsequentlyfillsthevacancyinthetableratherthanreplacingagoodtableentry.SuchaschemeforfillingvacanciesinthetablefitsnaturallywiththeLRUreplacementstrategy.Strategy4lMaintainatableofthemostrecentlyusedbranchinstructionsthatarenottaken.Ifabranchinstructionisinthetable,predictthatitwillnotbetakenotherwisepredictthatitwillbetaken.Purgetableentriesiftheyaretaken,anduseLRUreplacementtoaddnewentries.Figure5indicatestheaccuracyofstrategy4fortablesof1,2,4,and8entries.Insomecases,theaccuracy205wasclosetostrategy1forsmalltablesizesandbecameclosetostrategy2asthetablesizegrew.Thisisbecausesmalltablesizesarenotbigenoughtocontainallactivebranchinstructiohs,andtheykeepreplacingeachother.Asaresult,fewbranchinstructionsareeverfoundinthetable,andmostbranchesarepredictedastaken.Asthetablesizebecomeslargeenoughtoholdallactivebranches,theyareallpredictedasinstrategy2.Avariation7allowsearlierpredictionsthanwiththestrategiesdiscussedthusfar.Inthisvariation,instructionwordsbeingfetchedarecomparedwithanassociativememorytoseewhetherthefollowingwordwasinsequenceoroutofsequencethelasttimethewordwasaccessed.Ifitisoutofsequence,amemoryalongsidetheassociativememorygivestheaddressoftheoutofsequenceword,andinstructionfetchingcanbeginattheoutofsequencelocation.Inthisway,thepredictionis,ineffect,madebeforedecodinganinstructionasabranchandevenbeforedecomposingtheinstructionwordintoseparateinstructions.Theaccuracyofthisstrategy757islowerthanmanyofthestrategiesgivenhere,partlybecausethedefaultpredictioniseffectivelythatthebranchwillnotbetaken.Theprediction,however,canbemadeearlierintheinstructionfetchingsequence,andcanthereforeleadtoasmootherstreamofprefetchedinstructions.Anotherpossibilityforimplementingadynamicstrategywhenthesystemcontainscachememoryistostorepreviousbranchoutcomesinthecache.6sStrategy5lMaintainabitforeachinstructioninthecache.Ifaninstructionisabranchinstruction,thebitisusedtorecordifitwastakenonitslastexecution.Branchesarepredictedtobedecidedasontheirlastexecutionifabranchhasnotbeenexecuted,itispredictedtobetakenimplementedbyinitializingthebitcachetotakenwhenaninstructionisfirstplacedincache.Figure6showstheresultofusingstrategy5whenthereisa64wordinstructioncachewith4blocksof16wordseachreplacementinthecacheistheLRUstrategy.Theresultsareclosetostrategy2,asexpected,becauseaninstructioncachehitratioisusuallyatleast90.Thereisalsoastrategythatissimilartostrategy5exceptinitsimp1ementation.sAbitismaintainedforeachinstructioninthecache,butthebitisnotdirectlyusedtomakeabranchprediction.First,astaticpredictionbasedontheoperationcodeismade.Then,thepredictionISexclusiveORedwiththecachepredictionbit.Thischangesthepredictionifthebitisset.Wheneverawrongpredictionismade,thecachepredictionbitiscomplemented.Inthisway,branchesarepredictedasinstrategy5,butthepredictionmemoryonlyneedstobeupdatedwhenthereisawrongprediction.Thisisanadvantageifthereisatimepenaltyforupdatingthememory.IMPROVEDDYNAMICSTRATEGIESSeveraldynamicstrategiesintheprecedingsectionarequiteaccurate.Inthissection,theyarerefinedtoIuserandomaccessmemoryinsteadofassociativememoryand2dealwithanomalousdecisionsmoreeffectively.Inanyofthestrategies,thereisalwaysthepossibilitythatapredictionmaybeincorrect,andtheremustbeamechanismforreversingawrongprediction.Thisimpliesthatthereisroomforerror,andthisfactcanbeusedtoreplaceassociativememorywithrandomaccessmemory.Insteadofusingtheentirebranchinstructionsaddressforindexingintoatable,itcanbehasheddowntoasmallnumberofbits.Morethanonebranchinstructionmighthashtothesameindex,butatworst,anincorrectpredictionwouldresult,whichcouldbecompensatedfor.Thehashedaddresscanbeusedtoaccessasmallrandomaccessmemorythatcontainsabitindicatingtheoutcomeofthemostrecentbranchinstructionhashingtothesameaddress.Hashingfunctionscanbequitesimpleforexample,thelowordermbitsoftheaddresscanbeused,orthelowordermbitscanbeexclusiveORedwiththenexthighermbits.Withthesemethods,branchinstructionsinthesamevicinitywilltendtohashtodifferentindices.Strategy6lHashthebranchinstructionaddresstombitsandusethisindextoaddressarandomaccessmemorycontainingtheoutcomeofthemostrecentbranchinstructionindexingthesamelocation.Predictthatthebranchoutcomewillbethesame.206Althoughitcontributesnegligiblytotheresults,thedefaultpredictionwhenalocationisaccessedthefirsttimecanbecontrolledbyinitializingthememorytoallosorall1s.Figure7indicatestheresultsofusingstrategy6formequals4arandomaccessmemoryof16onebitwords.TheexclusiveORhashwasused.Theresultsaresimilartothoseofstrategy2.Avariationofstrategy6canbeusedtodealwithanomalousbranchdecisionsmoreeffectively.Thisvariationusesrandomaccessmemorywordsthatcontainacountratherthanasinglebit.Saythecountsareinitially0andthewordlengthisnthemaximumcountis21,andtheminimumcountis2twoscomplementnotation.Whenabranchinstructionistaken,thememoryworditindexesisIncrementeduptothelimitof21whenitisnottaken,thememorywordisdecrementeddowntothelimitof2.Whenabranchinstructionistobepredicted,itsaddressishashed,andthepropercountisreadoutofrandomaccessmemory.Ifthesignbitis0apositivenumberor0.thebranchispredictedtobetaken.Ifitis1,thebranchispredictedtobenottaken.Inthisway,thehistoriesofseveralofthemorerecentbranchexecutionsdetermineapredictionratherthanjustthatofthemostrecentbranchexecution.Inthecaseofananomalousbranchdecision,otherprecedingdecisionstendtooverridethemostrecentanomalousdecision,soonlyoneincorrectpredictionismaderatherthantwo.Strategy7Usestrategy6withtwoscomplementcountsinsteadofasinglebit.Predictthatthebranchwillbetakenifthesignbitoftheaccessedcountis0predictthatitwillnotbetakenifthesignbitis1.Incrementthecountwhenabranchistakendecrementitwhenabranchisnottaken.Notethatstrategy6isactuallyaspecialcaseofstrategy7withacountofonebit.Also,usingacounttendstocauseavotewhenmorethanonebranchinstructionhashestothesamecount.Figure8summarizestheresultsofusingstrategy7withcountsof2and3bitsandwithahashindexof4bits.Theaccuracyisquitegoodinfact,itisusuallyasgoodasorbetterthananystrategieslookedatthusfar.Alsd,acountof2bitsoftengivesbetteraccuracythanacountofonebit,butgoingtolargercountersthan2bitsdoesnotnecessarilygivebetterresults.Thisispartiallyattributedtotheinertiathatcanbebuiltupwithalargercounterinwhichhistoryinthetoodistantpastisused,orthehistoryofanearlierbranchinstructionhashingtothesameaddressinfluencespredictionsforalaterbranchinstruction.HIEARCHIALPREDICTIONGenerally,thefartheraninstructionisprocessedfollowingapredictedbranch,thegreaterthetimepenaltyifthepredictioniswrong.Forexample,ifonlyinstructionorefetchesarebasedonaconditionalbranchprediction,thetimepenaltywillprobablybelessthanifinstructionsarenotonlyprefetchedbutalsopreissued.Thatis,thetimeneededtoredirectinstructionprefetchesisprobablylessthanthecleanuptimeforinstructionsissuedincorrectly.Ofcourse,therewardsaregreaterthefartheraninstructionisprocessedwhenthepredictionturnsouttoberight.Ifalevelofconfidencecanbeattachedtoabranchprediction,thenperformancecanbeoptimizedbylimitingtheprocessingofaninstructionbasedontheconfidencethatabranchpredictioniscorrect.ExampleAssumethatforCPU,ifinstructionprefetchesarebasedonabranchprediction,anincorrectpredictionleadstoa6clockperiodcpdelaytofetchthecorrectinstructions.Ifthepredictioniscorrect,butinstructionsarenotissuedbeforetheoutcomeisknown,thereisa3cpdelaytowaitforthebranchdecision.Ifinstructionsarepreissuedanyway,andthepredictioniscorrect,thereisnodelayatall,butifthepredictionisincorrect,thereisatoralofa12cpdelay.Assumethatoverall,70ofthebranchescanbepredictedcorrectly.HalfofthebranchesSetAcanbepredictedwith50accuracy,andtheotherhalfSet8canbepredictedwith90accuracy.Further,assumethatitisknownatthetimeapredictionismadewhetherthebranchinstructionbelongstosetAorsetB.Thethreepossiblestrategiesandtheiraveragedelaysareasfollows1.Prefetchforallbranches0.3x6cp0.7x3cp3.9cp2.Prefetchandpreissueforallbranches0.3x12cp0.7x0cp3.6cp3.PrefetchforbranchesInsetAprefetchandprelssueforbranchesInset60.5x0.5x3cp0.5x6cp,0.5x0.1x12cp0.9x0cp,2.85cpThethirdstrategyISbest,becauseitrisksthehigh12clockperiodpenaltyonlywhenthereIShigherconfidenceofbeingcorrect.Strategy7providesanaturalwayofimplementingsuchahiearchicalpredictionstrategy.Ifacounterofatleast2bitsisatitsmaximumvaluewhenapredictionistobemade,thelastpredictionmusthavebeenthatthebranchwouldbetaken,anditmusthavebeencorrect.Afollowmgsimilarpredictionwouldthenseemlikelytobecorrect.AnanalogousstatementholdsifacountISatitsminlmumvalue.Consequently,apredictionbasedonanextremalcountervalueisahighconfidenceprediction,andapredictionbasedonanyothercountervalueisalowerconfidenceprediction.Figure9summarizestheresultsofusingsuchanapproach.A16wordRAMisusedwithacountof3bits.Inallcasesstudied,thepredictionsmadeatthecounterextremesweremoreaccurate.ThegreatestvariationinaccuracywasintheSORTSTprograminwhich78.5ofthepredictionsweremadeatthecounterextremes4,3,andabout92werecorrect.Ofthe21.5ofthepredictionsmadeawayfromthecounterextremes,onlyabout58wereaccurate.TheleastvariationwasintheADVANprograminwhichthecounterswerevirtuallyalwaysattheirmaximumvalues,andhiearchicalpredictionwouldhavebeenofnorealvalue.Thecountermethodusuallyachievedwhatwasanticipatedinmakingpredictionswithtwoconfidencelevels.Thismethodcouldbegeneralizedifcounterrangeswerebrokenintoseveralintervals,adifferentconfidencelevelbeingattachedtoeach.CONCLUSIONSThispaperstudiedtheaccuracyofbranchpredictionmethodsproposedelsewhereaswellasnewmethodsproposedhere.Asummaryofthestrategiesfollows.Inthecasesofstrategieswithseveralvariations,onlyoneortworepresentativesareindicated.Figure10givesasummaryoftheresults.Strategy1StrategylaStrategy2SWategy3Strategy4Strategy5Strategy6Strategy7Predictthatallbrancheswillbetaken.Predictthatonlycertainbranchoperationcodeswillbetaken.AlwayspredictthatabranchwillbedecidedasonItslastexecution.Predictthatonlybackwardbrancheswillbetaken.Maintainatableofthemmostrecentbranchesnottaken.Predictthatonlybranchesfoundintablewillbenottaken.Maintainahistorybitincacheandpredictaccordingtothehistorybitincacheandpredictaccordingtothehistorybita64wordinstructioncachewasused.Hashthebranchaddresstombitsandaccessa2wordRAMcontaininghistorybits,andpredictaccordingtothehistorybit.LikeStrategy6,butusecountersinsteadofasinglehistorybit.Thedynamicmethodstendedtobemoreaccurate.Ofthefeasiblestrategies,strategy7wasthemostaccurate.Italsohadtheadvantageofusingrandomaccessmemoryratherthanassociativememory.Forattachinglevelsofconfidencetopredictions,strategy7waseasilyadaptedandgavegoodresults.Atleastfortheapplicationsstudiedhere,strategy7isprobablythebestchoicebasedonaccuracy,cost,andflexibility.REFERENCESD.W.Andersonetal.TheIBMSystem/360model91Machinephilosophyandinstructionhandling.IBMJournalJan.1967.824.MJFlynn.Somecomputerorganizationsandtheir..effectiveness,IEEETransactionsonComputers.C21Sept.1972.948960.3H.D.Shapiro.AcomparisonofvariousmethodsfordetectingandutilizingparallelismInasingleinstructionstream.Proceedingsofthe1977internationalConferenceonParallelProcessingAug.1977.6776.208.E.Knuth.TheArtofComputerProgremming.vol.3SortingandSeerchingReading,Mass.AddisonWesley1973.6495.5J.C.Gibson,TheGibsonmixReportTR06.2043,IBMSystemsDevelopmentDivision,1970.L.J.Shustek.AnalysisandperformanceofcomputerinstructionsetsReport205.StanfordLinearAcceleratorCenter,1978.7RNIbbett.TheMU5instructionpipeline,TheComputerJurel,15Feb.1972.4250.as1ProjectStaff.AdvanceddigitalcomputingtechnologybasedevelopmentforNavyapplicationsTheSlproject,LawrenceLivermoreLaboratoriesTechnicalreportUCID18038.1978.91.Flores.LookaheadcontrolintheIBMSystem370Model165,Computer,7Nov.19741,2438.OE.M.RisemanandC.C.Foster.Theinhibitionofpotentialparallelismbyconditionaljumps,IEEETrensectionsonComputers,C21Dec.19721,14051411.209ProgramPredictionAccuracyADVAN99.4GIBSON65.4SC1296.2SINCOS80.2SORTST57.4TBLLNK61.5Figure1.AccuracyofPmdictionIforStrategy1ProgramPredictionAccuracyADVAN98.9GIBSON97.9SC1296.0SINCOS76.2SORTST81.7TBLLNK91.7Figum2.AccuracyofPmdictionIforStrategy2210
编号:201401051948096802    大小:895.62KB    格式:PDF    上传时间:2014-01-05
  【编辑】
5
关 键 词:
工业、机械、能源、设计、建模、模具、工学
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
  人人文库网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

当前资源信息

4.0
 
(2人评价)
浏览:9次
baixue100上传于2014-01-05

官方联系方式

客服手机:17625900360   
2:不支持迅雷下载,请使用浏览器下载   
3:不支持QQ浏览器下载,请用其他浏览器   
4:下载后的文档和图纸-无水印   
5:文档经过压缩,下载后原文更清晰   

相关资源

相关资源

相关搜索

工业、机械、能源、设计、建模、模具、工学  
关于我们 - 网站声明 - 网站地图 - 友情链接 - 网站客服客服 - 联系我们
copyright@ 2015-2017 人人文库网网站版权所有
苏ICP备12009002号-5