Java外文资料

Java毕业设计外文翻译资料

SableSpMT:ASoftwareFrameworkforAnalysingSpeculative

MultithreadinginJava

ChristopherJ.F.Pickett

ClarkVerbrugge

SchoolofComputerScience,McGillUniversity

Montr´eal,Qu´ebec,CanadaH3A2A7

{cpicke,clump}@sable.mcgill.ca

Speculativemultithreading(SpMT)isapromisingoptimisationtech-niqueforachievingfasterexecutionofsequentialprogramsonmultipro-cessorhardware.Analysisofanddataacquisitionfromsuchsystemsis

howeverdif?cultandcomplex,andistypicallylimitedtoaspeci?chard-waredesignandsimulationenvironment.Wehaveimplementeda?exible,software-basedspeculativemultithreadingarchitecturewithinthecontextofafull-featuredJavavirtualmachine.WeconsidertheentireJavalanguageandprovideacompletesetofsupportfeaturesforspeculativeexecution,http://wendang.chazidian.comingoursystemweareabletogener-ateextensivedynamicanalysisinformation,analysetheeffectsofruntimefeedback,anddeterminetheimpactofincorporatingstatic,of?ineinforma-tion.OurapproachallowsforaccurateanalysisofJavaSpMTonexisting,commoditymultiprocessorhardware,andprovidesavehicleforfurtherex-perimentationwithspeculativeapproachesandoptimisations.

KeywordsJava,virtualmachines,speculativemultithreading,threadlevelspeculation,pro?ling,staticanddynamicanalysis.

1.Introduction

Speculativemultithreading(SpMT),alsoknownasthreadlevelspeculation(TLS),isapromisingtechniquefordynamicparal-lelisationofsequentialprograms.Ithasbeeninvestigatedthroughmanyhardwareproposalsandsimulations[2,4,5,8,11,14,16,17,20,21,24,25,30,31,34,35,36,37,39,41],andasmallerbutnotinsigni?cantnumberofsoftwaredesigns[3,6,18,19,26,27,28,32,40,42],eachofferingitsownanalysisofvariousimplemen-tationandoptimisationtechniques.However,itisdif?culttoeval-uatetheseproposalswithrespecttoandincombinationwitheachother,astherearemultiplesourcelanguages,threadpartitioningschemes,SpMTcompilers,andhardwaresimulatorsbeingused.Evenifthesevariablesremain?xed,itishighlyunlikelythatanidenticalsoftwarearchitectureand/orsetofsimulationparameterswillbeused.

WepresentSableSpMTasacommonframeworkandsolutiontotheseproblems,asanextensionoftheSableVMJavavirtualma-chine[13].SableSpMTprovidesaconvenienthardwareabstrac-tionlayerbyoperatingatthebytecodeinstructionlevel,takesthefullJavalanguageandVMspeci?cationintoaccount,supports

staticanalysisthroughtheSootbytecodecompilerframework[38]andparsingofJavaclass?leattributes[29],andworksonexistingmultiprocessorsystems.SableSpMTprovidesafullsetofSpMTsupportfeatures,includinggenericspeculativemethodlevelpar-allelism(SMLP)andreturnvalueprediction(RVP).OurworkisdesignedtofacilitateSpMTresearch,andincludesauniquedebug-gingmode,logging,andportabilityamongstthefeaturesthatmakeitappropriateforexperimentationandnewdesigns.

WereportonbothJavabenchmarkandframeworkbehaviourtoillustratetheformsofexperimentalanddesignanalysiswesupport.Throughdynamicmeasurementsweshowthatwhilespeculativecoverage,thepercentageofsequentialprogramexecutionthatoc-curssuccessfullyinparallel,canbequitehighinJavaprograms,theoverheadcostsaresigni?cantenoughinourinitialimplementationtoprecludeactualspeedup.However,weareabletoperformex-perimentstodetermineupperboundsonspeedupintheabsenceofalloverhead,andourexecutiontimesarestillbetterthanthoseof-feredbyhardwaresimulatorsprovidingsimilarfunctionality[20].WealsobreakdowntheSpMToverheadcoststodetermineper-formancebottlenecksandsetoptimisationgoals.Inourcaseover-headisdominatedbyveri?cationofspeculativethreadsandtheconcomitantinterprocessormemorytraf?c,lockandbarriersyn-chronization,andupdatecostsforreturnvalueprediction(RVP),aruntimeoptimisationtechniquethatcanimproveSMLPperfor-mancebyupto2-fold[16].WithregardstoRVP,resultsgatheredwithinourframeworkextendpreviousstudiestoincludemorere-alisticbenchmarkruns,offerfurtherdataontherelativebene?ts,requirementsandcostsofvariouspredictionstrategies,andexposethepotentialbene?tsofexploitingbothstaticandruntimefeedbackoptimisationinformation.

Hardwaresimulationshavealreadydemonstratedthegreatpo-tentialinspeculativemultithreading.Wecontendthatthesametechniques,however,canbeinvestigatedmoregenerallyandef-?cientlyatthevirtualmachinelevelusingcommoditymultipro-cessorhardware,givenanappropriateanalysisframework.Virtualmachinesallowforexplorationofcomplexdesignchanges,facil-itatedetailedinstrumentation,providehighlevelinformationthatisnotgenerallyavailabletohardwareapproaches,andareabletointeractdirectlywiththeunderlyingarchitecture.Ourworkisin-tendedtoenableSpMTinvestigationsbyprovidinganexecutionandanalysisenvironment,ageneraldesignandcomponentry,andrealdatafromaworkingimplementation.1.1Contributions

Wemakethefollowingspeci?ccontributions:

?WedescribeSableSpMT,acompleteimplementationofSpMTforJavathatrunsonrealmultiprocessorhardware,andpresentitssuitabilityasananalysisframework.Thisisthe?rstcom-pletesuchworkwithinavirtualmachine.

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro?torcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthe?rstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspeci?cpermissionand/orafee.PASTE’05September5–6,2005,Lisbon,Portugal.

c2005ACM1-59593-239-9/05/0009...$5.00.Copyright??

59

Java毕业设计外文翻译资料

?WesimplifytheimplementationandanalysisofnewSpMTde-signsbyprovidingadeterministic,single-threadeduniproces-sormode,aswellasloggingfacilities,statisticsgathering,andfullJVMsupport.

?Wedemonstratethathighlevelanalysisinformationcanbeeas-ilyexploitedbyourframework.Ahead-of-timeresultscom-putedbySootaswellasruntimepro?ling-basedfeedbackcanpassedtoourexecutionenginetoimproveperformance,andweillustratethetechniqueusingourworkonRVP.

?Weprovidedetaileddataonthespeculativeexecutionofnon-trivialprograms,whichincludeabreakdownofoverheadcosts,theimpactofhighlyaccurateRVP,twodifferentmeasurementsofdynamicparallelism,andoverallrunningtimes.

InSection2wediscussrelatedworkontheanalysisofspecu-lativemultithreading.InSection3wedescribethegeneralSpMTmodelwehaveusedandgiveanoverviewofhowourframeworkisconstructedanditsmainfeatures.ThisincludesanexpositionofthecomponentsrequiredforJavaSpMT,ourmultithreadedexe-cutionandsingle-threadeddebuggingmodes,systemcon?gurationoptions,andthedataloggingandtracegenerationfeatures.InSec-tion4weanalyseactualdataandshowthe?exibilityofoursystemintermsofdatagathering.Finally,wediscussfutureworkandcon-cludeinSection5.

LiljathroughmanualJavasourcetransformations[18];similarlyWelcetal.demonstrategoodspeedupofloopsineasilyparallelis-ablebenchmarks,throughapplicationofsafefuturesforJava[40],sourcelevelannotationsthatprovideSpMT-likefunctionalityanddependonVMsupportforparallelisation.Opposingly,WargandStenstr¨omarguethatJava-basedSpMThasinherentlyhighover-headcostswhichcanonlybeaddressedthroughhardwaresup-port[39].Ourdataandanalysisaresigni?cantlymorecomprehen-sivethanpriorstudies,andsuggestthatwhileoverheadscanbequitehigh,thereissuf?cientpotentialparallelismtooffsetthecost.Wehaveanalysedreturnvaluepredictionaspartofourinvesti-gationintoSpMTbehaviour.ValuepredictionforSpMThasbeenexploredbyseveralgroups[4,8,25],andisgenerallywell-studied.Thespeci?cutilityofreturnvaluepredictionformethodlevelspec-ulationinJavawasshownbyHuetal.[16],withfurtherpredictionaccuracyinvestigatedbytheauthors[26,27];ourvaluepredictionapproachhereisbasedonthesedesigns.

3.Framework

Webeginwithanoverviewofourframework,followedbyabriefexpositionofourspeculativeexecutionmodel,andsomeofthefea-turesofourframeworkthathelpwithimplementationanddebug-gingofsuchacomplex

undertaking.

2.RelatedWork

Speculativemultithreadingapproacheshavebeendevelopedpri-marilyinthecontextofnovelhardwareenvironments.AnumberofgeneralpurposespeculativearchitecturessuchastheMultiscalararchitecture[11],theSuperthreadedarchitecture[37],MAJC[36],Hydra[14],andseveralotherdesigns[21,34]havebeenproposed,andsimulationstudieshavegenerallyshownquitegoodpotentialspeedups.Steffanetal.givearecentimplementationandgoodoverviewofthestateoftheartin[35].

Fromthespeculativehardwarelevel,anexecutingJavavir-tualmachinedoesnothavedistinguishedperformanceincom-parisonwithotherapplications[39].Asaninterpretedlanguage,however,Javacanprovidehigherlevelabstractionsandinforma-tionthangenericmachinecode.Highlevelprograminformationisusedinafewhybridsoftware/hardwarestudies,includingChenandOlukotun’sthreadlevelspeculationsystemforJava[5].Javatracesappliedtosimulatedarchitectureshavebeenusedbyseveralresearchers,includingHuetal.intheirstudyoftheimpactofre-turnvalueprediction[16],andWhaleyandKozyrakis’recentstudyofheuristicsformethodlevelspeculation[41].

SoftwarearchitecturesforSpMTarelesscommon.RundbergandStenstr¨omdescribeasoftwareapproachtospeculationinC[32].Theirprototypeimplementationshowsgoodspeedup,butisveri?edonlythroughhanddonetransformationsandgreatlylim-itedrealworldtesting.KaziandLiljadescribeasoftwarelibraryforcoarse-grainedthreadpipelining[19],demonstratedthroughman-ualparallelisationofloopsinCprograms.The“Softspec”softwarespeculationenvironment[3]concentratespurelyonloop-basedspeculation.Theapproachdependsonmachinecodelevelruntimepro?lingtoidentifyindependentloopbodiessuitableforspecula-tiveexecution.CintraandLlanoshavedevelopedaFORTRAN-basedsystemthatalsospeculatesonloopbodies[6].Theseap-proachesallachievegoodperformanceresults,butnonearebasedonJavaordesignedspeci?callyasexperimentalframeworks.

OnlyverylimitedstudiesonlanguagelevelspeculationforJavahavebeendonepreviously.Yoshizoeetal.giveresultsfromapartiallyhand-donelooplevelspeculationstrategyimplementedinarudimentary(e.g.,noGC)prototypeVM[42].Theyshowgoodspeedupforsimplesituations,butlackofheapanalysislim-itstheirresults.AmoreconvincinganalysisisgivenbyKaziand

TheoverallSableSpMTexecutionenvironmentisshowninFigure1.SableVMpreparesspecialspeculativeandnormalnon-speculativeversionsofmethodsatruntimefromdynamicallyloadedclasses,whicharereadinfromJava.class?les.Soot[38]isusedtotransform,analyse,andattachattributestotheseclassesinanahead-of-timestep[29],althoughthiscouldalsooccuratrun-time.Twoexecutionmodesareprovided,asingle-threaded“sim-ulation”modeandatruemultithreadedmode,bothofwhichcanexploitareturnvaluepredictionframework.ThemultithreadedmodesplitssingleJavathreadsacrossmultipleprocessorsonanSMPmachine.

3.1SpeculativeMethodLevelParallelism

ThreadsarecreatedusingtheSpMTvariantknownasspecula-tivemethodlevelparallelism(SMLP)[4,5,16,39,41],depictedinFigure2.Ordinarysequentialbytecodeexecutionisshownin

60

Java毕业设计外文翻译资料

Figure2.SequentialandSMLP-basedbytecodeexecution.Figure2a,wherethetargetmethodofanINVOKE<X>instructionexecutesbeforetheinstructionsfollowingthereturnpoint.Specu-lativeSMLP-basedexecutionisshowninFigure2b.Uponreach-ingamethodcallsite,thenon-speculativeparentthreadT1forksaspeculativechildthreadT2.Ifthemethodisnon-void,apre-dictedreturnvalueispushedonT2’soperandstack.T2thencon-tinuespastthereturnpointinparallelwiththeexecutionofthemethodbody,bufferingallreadsfrommainmemory.WhenT1re-turnsfromthecall,itjoinsT2.Iftheactualreturnvaluematchesthepredictedreturnvalue,andtherearenodependenceviolationsbe-tweenbufferedreadsandpost-invokevalues,T2’sbufferedwritesarecommittedandnon-speculativeexecutionjumpsaheadtowhereT2leftoff,yieldingspeedup.Iftherearedependenceviolationsorthepredictionisincorrect,T2issimply

aborted.

childthreadsaprotectedexecutioncontext.NewSPMTFORKandSPMTJOINinstructionssurroundeverycallsite;theforkinstructioninsertschildthreadsintoapriorityqueue,whicharedequeuedandexecutedonseparateprocessorsbySpMThelperthreads,andthejoininstructionstopsandvalidateschildren,eithercommittingorabortingthem.Whileexecutingspeculativecode,weneedmodi?edbytecodeinstructionstoprotectagainstunsafecontrol?ow;forexample,GETFIELDismodi?edtoreadfromadependencebuffer,andMONITOREXITcausesspeculationtocometoanabrupthalt,althoughitdoesnotautomaticallyforceabortion.Finally,weneedtomakesurespeculationinteractssafelywithexceptionhandling,garbagecollection,nativemethodexecution,synchronization,classloading,andthenewJavamemorymodel[23].

WemakeseveraldifferentoptimisationstothesecomponentsinSableSpMT,someofthemorenotableonesbeingaggressivereturnvalueprediction[26,27],improvementstothedependencebuffer,allowingforspeculativethreadstoenterandexitmethods,betterenqueuingalgorithms,speculativeobjectallocation,andreductionofinterprocessormemorytraf?c.Mostofthetechniqueswehaveencounteredintheliteraturecanalsobeimplementedwithinourframework;inSection4weillustratetypicaldatagatheringandanalysisusingourworkonreturnvaluepredictionandthespecula-tiveengineitselfasexamples.3.2Single-threaded

Mode

Figure4.Single-threadedsimulationmode.

Oneoftheuniquefeaturesofourdesignisasingle-threadedsimulationmodethatmimicstheprocessofspeculativeexecutioninasinglethread.EarlyoninthedevelopmentofSableSpMT,wefoundourselveswantingsomewaytotestthecomponentswehadwritteninthecontextofanexecutingJVM,withoutintroducingthecomplexityofactualconcurrencyintoourdebuggingprocess.TheresultingdeterministicdesignisshowninFigure4.InthismodeasinglethreadofJavaexecutionfollowsthecompletespeculativecontrol?ow.Uponreachingaforkpoint,themethodcallisskipped,andtheensuingcodeisexecutedspeculatively;whenaterminat-ingconditionisreached,thesamethreadjumpsbacktothenon-speculativeexecutionofthemethodcall,anduponreturningfromthecall,itattemptstojoinwithitsownspeculativeresult.

Figure3.Multithreadedmode.

ManycomponentsareneededforSMLPtoworkproperlyinaJVM,thefulldetailsofwhicharegivenin[28].AhighlevelviewofthemultithreadedmodethatbringstogetherallofthesecomponentsisshowninFigure3.Adependencebufferprotectsmainmemoryfromout-of-orderandpossiblyinvalidspeculativeoperations,andsomeformofstackbufferingisnecessarytogive

61

Java毕业设计外文翻译资料

Therearethreeprimaryadvantagestohavingthissingle-threadedsimulationmode.First,itallowsfortestingofSpMTcomponentsinanincompletesystem,mostimportantlyonewith-outmultiprocessorsupport.Itdoessobyprovidingstatesavingandrestoral,andinterleavingtheexecutionofspeculativeandnon-speculativecode.Second,bynotrunningmultiplethreadsitpre-ventsraceconditions,deadlocks,andmemorytraf?cfrominter-feringwithdevelopment,helpingtominimizethesearchspacewhenfacedwithdebugging.WewereabletoalternatecodingwithdesigningsupportforSpMTaccordingtothefullJVMSpeci?ca-tion[22],andonlyafterwehadcompletedarequirementsanalysisinthismannerdidwedevelopthemultithreadedexecutionmode.Third,itmeanswehavethefoundationsforJavacheckpointingandrollbackwithinavirtualmachine.ThishasutilityforJavaoutsideofSpMT,intraditionaldebugging[7],databasetransac-tions(e.g.injava.sql.Connection()),formalveri?cation[10],fault-tolerance[12],andsoftwaretransactionalmemory[15].3.3

SystemCon?guration

Systempropertiesspeci?edonthecommandlineareusedtose-lectdifferentSpMTalgorithmsanddatastructures,whichfacil-itatesexperimentalanalysisbyeliminatingtheneedformultipleVMbuilds.AschangestoSableSpMTareintroduced,ratherthanoutrightreplaceoldcontrol?oworadjustconstantstooptimalval-ues,systempropertiesareusedwhereverpossible,andthusitisstraightforwardtomakecontrolledcomparisonsandreverttooldcon?gurations.In?nalizedbuilds,thesepropertiescanbeautomat-icallyconvertedtoconstantsviapreprocessordirectivesandasin-gleAutoconfconfigureoption,sothattheaddedruntimeover-headofconditionalstestingthemwillbeoptimisedaway.Atthetimeofwriting,thereareover50suchproperties,controllingev-erythingfrommaximumRVPhashtablesizestothenumberofex-ecutingSpMThelperthreads,anditiseasytointroducenewones.Theonlyothersigni?cantcompile-timeconfigureoptionsinSa-bleSpMTallowtheuserto1)enableSpMTinthe?rstplace,2)enabledebuggingandassertions,and3)enablestatisticsgatheringforpost-executionanalysis.3.4

LoggingandTraceGeneration

----SS-S-S--S-S-@0x2a976bad68ALOAD_0@0x2a976bad70SPMT_FORK

ENQUEUESPMTCHILD@0x5ed850@0x2a976bad88INVOKESPECIALDEQUEUESPMTCHILD@0x5ed850STARTSPMT

enteringjava/lang/Object.<init>()V@0x2a976baf38ALOAD_0@0x2a976baf90RETURN@0x2a976baf40ALOAD_1

exitingjava/lang/Object.<init>()V@0x2a976badb0SPMT_JOIN

@0x2a976baf48SPMT_PUTFIELD

signallingspmtthreadhalt@0x5ed850STOPSPMT-SIGNALLED_BY_PARENTSPMTPASSED@0x5ed850

whenimplementingnewtechniques.SableVMsupportsonlytheJVMDIandJDWPforintegrationwithdebuggersatthistime,andalthoughwedonotprovidetracecompressionoranimple-mentationandextensionoftherelatedJVMPIorJVMTIpro?linginterfaces,thesefacilitiescouldbeincorporatedtopermitdetailedanalysisofSpMTexecutiontraces,usingadynamicmetricstoolsuchas*J[9].

4.ExperimentalAnalysis

Inthissectionwedescribeourreturnvaluepredictionframework,theintegrationofstaticanalysesintoSableSpMT,andvariouskindsofdynamicanalysisavailabletotheresearcher.Weprovideexper-imentalresultstodemonstratehowtheseanalysesgiveinsightintotheruntimebehaviourofindividualbenchmarks,componentsoftheframework,andtheframeworkasawhole,andhowtheysuggestinterestingareasforfutureinvestigationandoptimisationresearch.4.1ReturnValuePrediction

Methodcallreturnvaluesareoftenusedrelativelysoonafteramethodcall.Returnvalueprediction(RVP)allowsaspeculatingthreadtoproceedfurtherwithoutfailingduetosuchadependencybyheuristicallypredictingthereturnvalue.ItwaspreviouslyshownthataccurateRVPiscriticalforJavaSMLPperformance[16],andonthisbasiswesetouttoexplorehighlyaccurateRVPinSableSpMT[27].Weimplementedseveralwell-knownpredictors,includingacontextpredictorthatusesaper-callsitehashedhistoryofthelast?vereturnvalues,andahybridpredictorthatselectsthebestofseveralsub-predictorsatruntime.Wealsointroducedapowerfulnewmemoizationpredictorthatassociatesreturnvalueswithhashedmethodarguments.Whenexistingpredictorswerecombinedinahybridweachievedanaverageaccuracyof72%overSPECjvm98,andtheinclusionofthememoizationpredictorincreasedthisaverageto81%.ExploitingVMlevelknowledgeaboutthewidthofprimitivetypesallowedustoreducehashtablememoryby35%.

FulldetailsontheanalysesperformedinourinitialRVPstudyareavailablein[27];twooftheneaterresultsobtainedwerehowthecontextandmemoizationpredictorsexhibiteddramaticallydif-ferentaccuracydependingonbenchmark,andhowwewereabletoidentifyasmallpercentageofcallsitesasbeingresponsibleforeithertheproductionorconsumptionofhighlyvariabledata,ac-cordingto?nalcontextormemoizationpredictorsizesrespectively.TheRVPsystemisnowakeypartofSableSpMT;itiseasilyex-tendabletosupportnewtypesofreturnvaluepredictors,andcouldevenbeusedforgeneralpurposeloadvaluepredictionbyspecula-tivethreads.4.2StaticAnalysis

TheSootbytecodecompilerframework[38]isaconvenienttoolforahead-of-timestaticanalysisandtransformationintheabsenceoftheruntimestaticanalysissupporttypicallyfoundinJITcom-pilers.InFigure6weshowtheuseofSoottotransformthebaseinputJavaclass?lesinordertoinsertSPMTFORKandSPMTJOINinstructions.Thesameprocesscanalsobeusedtoappendstaticanalysisinformationasclass?leattributes[29],whicharethenin-terpretedbytheSpMTengine.

WeusesideeffectandcallgraphinformationderivedfromSoot’spoints-toanalysisintwocompileranalysesforimprovedRVP,andstudytheeffectonruntimepredictorbehaviourusingourframework[26].The?rstanalysisisareturnvalueuseanalysis(RVU),thatdetermineshowreturnvaluesareusedafterreturn-ingfromamethodcall.We?ndstaticallythatanaverage10%ofnon-voidcallsitesgenerateunconsumedreturnvalues,and21%ofcallsitesgenerateinaccuratereturnvalues,whichwede?neas

T1:P16384T1:P16384T1:P16384T1:P16384T1:P49156T1:P49156T1:P16384T1:P49156T1:P16384T1:P49156T1:P16384T1:P16384T1:P49156T1:P16384T1:P49156T1:P16384

Figure5.SpMTexecutiontrace.

Finally,SableSpMTprovidesacomprehensiveloggingandtracegenerationsystemthatcanpresentJavaSpMTeventsbythemselves,orinterleavethemwithexistingexecutiontracesofclassloading,methodinvocation,garbagecollection,synchroniza-tion,andbytecodeexecution.Anexampletracewithinterleavedmethodinvocation,bytecode,andSpMTeventsisshowninFig-ure5.Thesetracesareprimarilyusefulfordebuggingpurposes

62

Java毕业设计外文翻译资料

Figure7.Speculationoverhead.Bothnon-speculativeparentandspec-ulativechildthreadssufferwastedcyclesduetooverheadatforkatjoinpoints.

parentexecutioncompdbjackjavacjessmpegmtrtrtUSEFULWORK39%24%29%

initializechild2%5%3%enqueuechild4%10%10%TOTALFORKupdatepredictor7%13%12%

deletechild5%5%5%signalandwait15%14%11%validateprediction4%4%4%

validatebuffer4%6%6%commitchild5%5%7%abortchild<1%<1%<1%cleanupchild<1%<1%<1%

pro?ling11%10%10%TOTALJOIN53%59%57%PROFILING2%2%1%

30%

4%9%11%4%11%5%5%6%<1%<1%12%56%1%

21%4%7%12%5%19%7%5%6%<1%<1%11%67%1%

59%2%3%6%2%8%3%3%3%<1%<1%7%34%2%

49%1%2%7%2%26%2%1%2%<1%<1%5%47%1%

58%2%2%7%2%11%3%2%3%<1%<1%6%36%2%

Figure6.Staticanalysisintegration.

thosethatareusedonlyinsidebooleanorbranchexpressions.Ac-tualruntimemeasurementsshowlessimprovement:only3%ofdynamicmethodinvocationsreturnunconsumedvalues,whereas14%returninaccuratevalues.Thisanalysisdoesreducehashtablecollisions,saving3%ofpredictormemoryandincreasingaccuracybyupto7%.

Thesecondanalysiscomputesparameterdependence(PD),aformofslicingthatdetermineswhichparametersaffectthereturnvalue.Statically,weobservethat25%ofconsumedcallsiteswithoneormoreparametershavezeroparameterdependences,and23%havepartialdependences,suchthatthereturnvaluedoesnotdependononeormoreparameters.Atruntime,however,we?ndthat7%ofdynamicmethodinvocationshavezerodependencesandonly3%havepartialdependences.Theresultsofthisanalysisareexploitedtoeliminateinputstothememoizationpredictor,andtheaccuracyofmemoizationaloneforjack,javac,andjessincreasesbyupto13%,withoverallmemoryrequirementsbeingreducedbyafurther2%.Althoughtheseanalysesyieldonlyincrementalimprovements,atleastintheircurrentform,theydodemonstratehownewstaticanalysescanbeeasilyincorporatedintoSableSpMTandbothvalidatedandemployedatruntime.4.3

DynamicAnalysis

WenowdescribedynamicanalysisoftheSableSpMTengine,anextensionoftheSableVM1.1.9switchinterpreter.Allexperimentswereperformedona1.8GHz4-waySMPAMDOpteronmachinerunningLinux2.6.7,usingnative64-bitbinariesandrunningtheSPECjvm98benchmarksuite[33]atsize100(S100).Childrenwereforkedateverycallsitereachednon-speculatively,allfreepro-cessorswereoccupiedbyspeculativehelperthreads,andanopti-malreturnvaluepredictioncon?gurationwasused,unlessother-wisestated.4.3.1

SpeculationOverhead

TheoverheadofthreadoperationsinanySpMTsystemisamajorconcern[39],andthisisespeciallytrueinapuresoftwareenviron-ment.Weintroducedpro?lingsupportintoourframeworkinordertoprovideacompletebreakdownofSpMToverheadincurredbybothparentandspeculativechildthreads;refertoTables1and2respectively.AsshowninFigure7,parentthreadssufferoverheadwhenforking,enqueuing,joining,andvalidatingchildthreads,andchildthreadssufferonstartupandwhentheyreachsomestopping

condition.

Table1.Non-speculativethreadoverheadbreakdown.Parentexecution

consistsofusefulwork,forkoverhead,andjoinoverhead,andalsothepro?lingoverheadinherentindelineatingthesethreebroadtasks.Pro?linginthejoinprocessincludesthecostofgatheringoverheadinfofortheothereightsub-tasks,andofupdatingvariousSpMTstatistics.

helperexecutioncompdbjackjavacjessmpegmtrtrtIDLE

startup

querypredictorusefulworkshutdownpro?ling

EXECUTECHILDCLEANUPCHILD

PROFILING

86%<1%3%5%<1%<1%<1%1%

82%<1%5%6%<1%<1%<1%1%

78%<1%4%10%<1%<1%<1%1%

78%<1%4%10%<1%<1%<1%1%

78%<1%6%10%<1%<1%<1%<1%

55%<1%5%34%<1%1%<1%1%

53%1%15%20%<1%2%<1%1%

71%<1%8%13%<1%1%<1%<1%

Table2.Speculativethreadoverheadbreakdown.HelperSpMTthreadsexecuteinaloop,idlingforanopportunitytodequeuechildrenfromthepriorityqueue,andtheninitializethem,executethem,andcleanthemup.Thechildexecutionprocessitselfconsistsofstartup,queryingthereturnvaluepredictor,usefulwork(currentlyonlybytecodeexecution),andshutdown,inducedbyreachingsometerminationcondition.Thereispro?lingoverheadbothwhenexecutingspeculativecode,andwhenswitchingbetweentasksinthehelperloop.

ThestrikingresultinTable1isthattheparentspendssomuchofitstimeforkingandjoiningspeculativethreadsthatitsopportu-nitiesformakingprogressthroughnormalJavabytecodeandna-tivecodeexecutionarereducedbyupto5-fold.Weseethatjoin-ingthreadsissigni?cantlymoreexpensivethanforkingthreads,andthatwithinthejoinprocess,predictorupdatesandwaitingforthespeculativechildtohaltexecutionarethemostcostlysub-categories.Otheroverheadsub-categoriesarenotinsigni?cant,and

63