三个臭皮匠胜过一个诸葛亮

ExploitingThread-LevelParallelismin

GeneralPurposeApplicationsPen-ChungYew游本中

DepartmentofComputerScienceandEngineeringUniversityofMinnesotahttp:///Agassiz2023/1/111PCYew-Taiwan三個臭皮匠勝過一個諸葛亮

三個諸葛亮勝不過一個臭皮匠Pen-ChungYew游本中

DepartmentofComputerScienceandEngineeringUniversityofMinnesotahttp:///Agassiz2023/1/112PCYew-TaiwanImpactofHardwareTechnologyonComputerArchitecturesPerformance

improvementofmicroprocessorssofarhasbeendrivenprimarilybyhigherclockrates:

smallerfeaturesizes

(Moore’sconjecture),higherpowerdensity,highercoolingcostResults?IntelcancelledtwoPentiumprojectsrecentlyVLSItechnologyallowsmorethan1billiontransistorsonasinglechip=>plentyofgates,whattodowiththem?Superscalarishardtoscalebeyond~10instructionsperclockcycle:inherent

ILP(Instruction-LevelParallelism)limitationinapplicationprograms,longwiredelays,highpowerdensityMemorywallisgettinghigherbetweenCPUandstoragedevicesImprovingsingleprogramperformanceisstillveryimportant2023/1/113PCYew-TaiwanParallelProcessingComestotheRescue–Finally?Parallelprocessinghasbeenproposedtosalvageclockratelimitation=>forthepastthirtyyears!!!Finally?=>multiplecoresinIntel’sroadmapaswellasinmostembeddedprocessorstodayWhatisnewhere?

Usethread-levelparallelism(TLP)toimproveinstruction-levelparallelism(ILP)

forgeneral-purposeapplications2023/1/114PCYew-TaiwanILPvs.TLPTimeop1op2op3op4op5op6op7op8op9op10op11op12……………..op21op22op23op24t1t2t3t6Timet1t2t3t6op1op2op3op4op5op6op7op8op9op10op11op12…………op21op22op23op24Th1Th2Th3Th4SuperscalarTLPILP2023/1/115PCYew-TaiwanParallelProcessingComestotheRescue–Finally?IsthereenoughTLPingeneral-purposeapplicationprograms(toimproveILP)?=>muchharderthanscientificapplications(floating-point-intensive)2023/1/116PCYew-Taiwan2023/1/117PCYew-TaiwanTLPChallengesinGeneral-PurposeApplicationsMostlyDo-whileloopsNeedthread-levelcontrolspeculationParallelismexistsmostlyinouterloopsNotgoodforVLIW(i.e.softwarepipelining),orvectorprocessing=>needthread-levelsupportPointerscomplicatealiasanddatadependenceanalysisNeedruntimedisambiguationanddataspeculationManysmallloopsanddoacrossloopsNeedfastandlowoverheadcommunicationSmallbasicblocks–needtoexploitbothILPandTLP

Neednewapproachestoapplyparallelprocessingtosuchapplications!!2023/1/118PCYew-TaiwanOutlineMulti-threadedarchitecturesSpeculationtobreakdependencySpeculativeexecutiononsingle-threadedprocessorsSpeculativeexecutiononmulti-threadedprocessorsProfile-basedanalysesConclusion2023/1/119PCYew-TaiwanMulti-ThreadedArchitectures

Toimprovesingle-programspeedupMultiscalarSuperthreaded

ProrcessorsTraceprocessorMultiprocessoronachipToimproveresourceutilization,throughputSimultaneousMultithreading(SMT)TohidememorylatencyTeracomputer,HyperthreadingTosupportsystem/applicationfunctionalityReference:SpeculativeExecutioninHighPerformanceComputerArchitectures,editedbyKaeliandYew,CRCPress,20052023/1/1110PCYew-TaiwanSuperthreadedArchitectures

Exploitthread-levelparallelismtoenhanceILPMultiplevs.singleinstructionwindows(notforscalabilityasintraditionalparallelprocessing)Controlspeculation(notstoppedbybranchinstructions)Dataspeculation(notstoppedbydatadep’sbetweenthreads)Fastcommunication=>smalltaskgranularityHighcachehitrates,automaticdataprefetchingNeednewhardwareandcompiler/softwaresupportReference:

TheSuperthreadedProcessorArchitecture,Tsai,etal

IEEETrans.OnComputers,Sept19992023/1/1111PCYew-Taiwan

InstructionCache

DataCacheThreadprocessingunitExecutionUnitComm.UnitMemoryBufferWritebackUnitThreadprocessingunitExecutionUnitComm.UnitMemoryBufferWritebackUnitThreadprocessingunitExecutionUnitComm.UnitMemoryBufferWritebackUnitThreadprocessingunitExecutionUnitComm.UnitMemoryBufferWritebackUnit2023/1/1112PCYew-TaiwanSpeculation:

BreakingProgramDependencyControlanddata

dependenceslimitprogramperformanceHowever,MostbrancheshavegoodpredictabilityMostdatadependences

happeninfrequently

atruntimeSpeculationisaneffectiveapproachtobreakdependencesOptimizeprogramexecutionbyignoringinfrequent

datadependences,ortakingpredictedpathsCheck

possibleviolation(mis-speculation)atruntimeRecoverifviolationoccurs2023/1/1113PCYew-TaiwanTypeofSpeculationControlspeculationSpeculateonprogramcontrolflowpathDataspeculationSpeculateonhowlikelymemoryreferencesaretothesamememorylocation(address)ValuespeculationSpeculationontheresultvalueofanoperation2023/1/1114PCYew-TaiwanOutlineMulti-treadedarchitecturesSpeculationtobreakdependencySpeculativeexecutiononsingle-threadedprocessorsSpeculativeexecutioninmulti-threadedprocessorsProfile-basedanalysesConclusion2023/1/1115PCYew-TaiwanSpeculationonIntelIA64BothcontrolanddataspeculationaresupportedonIntelIA64SpecialinstructionsandhardwareareprovidedMemoryloadoperationistargetedforspeculationMemorydelayisusuallythebottleneckofperformanceMemoryloadisusuallythestartofspeculativeoperations2023/1/1116PCYew-TaiwanSpeculatingonDataDependence

MorespeculativeoptimizationsI1:…=*qI2:*p=bI3:…=*qI4:*r=…I5:…=*pI6:*r=…SpeculateonthisdependenceRedundancyeliminationopportunity2023/1/1117PCYew-TaiwanSpeculateonDataDependences

MorespeculativeoptimizationsI1:…=*qI2:*p=bI3:…=*qI4:*r=…I5:…=*pI6:*r=…SpeculateonthisdependenceCopypropagationopportunity2023/1/1118PCYew-TaiwanSpeculateonDataDependences

MorespeculativeoptimizationsI1:…=*qI2:*p=bI3:…=*qI4:*r=…I5:…=*pI6:*r=…SpeculateonthisdependenceDeadstoreeliminationopportunity2023/1/1119PCYew-TaiwanObservationsSpeculativeoptimizationopportunitiesexistinmanyapplications(originally,itwasonlyformemorylatencyhidingduringcodescheduling)AgeneralcompilerframeworkisneededtosupportbothcontrolanddataspeculationinoptimizationsNeedtogeneraterecoverycodeformis-speculationNeedextensivesupportfordatadependence,alias,andvalueprofiling

(nolongerconservativeanalysis)Reference:

ACompilerFrameworkforSpeculativeAnalysisandOptimizations,ACM/SIGPLANConf.OnProgrammingLanguageDesignandImplementation(PLDI),June2003,alsoinACMTrans.OnArchitectureandCodeOptimization(TACO),Vol.1,No.3,Sept.2004,pp.247-2712023/1/1120PCYew-TaiwanACompilerFramework:

IntelOpenResearchCompiler(ORC)2023/1/1121PCYew-TaiwanPerformanceImprovementofSpeculativeRegisterPromotionBasedonaliasprofileandcomparedwith–O3withtype-basedaliasanalysisonIntelORCcompiler2023/1/1122PCYew-TaiwanValueSpeculation

ValueLocality:likelihoodofapreviously-seenvaluerecurringwithinastoragelocationObservedinanystoragelocationsRegistersCachememoryMainmemoryMostworkfocussingonvaluestoredinregisterstobreakpotentialdatadependences:registervaluelocality2023/1/1123PCYew-TaiwanPerformanceofValuePredictorsPredictabilityofDataValues,SazeidesandSmith,Micro-30,1997Lastvaluepredictionvariesfrom23%to61%,averageabout40%Stridepredictionvariesfrom38%to80%,averageabout56%FCMwithanorderof3variesfrom56%toover90%,withanaverageofabout78%ImprovementdiminishesasorderincreasesLesssensitivetodifferenttypesofinstructions2023/1/1124PCYew-TaiwanOutlineIntroductionSpeculationtobreakdependencySpeculativeexecutiononsingle-threadedprocessorsSpeculativeexecutiononmulti-threadedprocessorsProfile-basedanalysesConclusion2023/1/1125PCYew-TaiwanCompilerOptimizationsforSpeculativeThreadsWithoutcompileroptimization,thereislimitedTLPevenunderperfecthardwaresupport.[OplingerPACT99]CompilerhavetodecideWhichloops/regionstobetransformedintothreadUsesynchronizationorspeculationHowtoschedulethecodetoimproveoverlapsWhattransformationstobeusedWhen/HowtogeneraterecoverycodeProfile-basedanalysiscouldbeveryefficient2023/1/1126PCYew-TaiwanLoopSelectionprogramspeedupCarefullyselectedloopscanimproveperformancesignificantly!2023/1/1127PCYew-TaiwanSpeculativeCodeMotion*p=*p=*p==*p=*p=*p*p=*p=*p=

=*p=*p=*pstall

critical

pathother

computation

beforecodemotionaftercodemotion2023/1/1128PCYew-TaiwanOutlineIntroductionSpeculationtobreakdependencySpeculativeexecutiononsingle-threadedprocessorsSpeculativeexecutiononmulti-threadedprocessorsProfile-basedanalysisConclusion2023/1/1129PCYew-TaiwanCrucialConsiderationsinDependenceProfilingProgramcoverage=>needcompiler’ssupportoruseheuristicrulesInputsensitivityProfilingoverhead(spaceandtime)Usingaliasanddatadependenceprofilesisinherentlyspeculative=>needhardwaresupportforcorrectexecution2023/1/1130PCYew-TaiwanAliasProfilingvs.StaticAnalysis

Mostpossibledatadependencereportedbycompilerdonotoccuratruntime2023/1/1131PCYew-Taiwan

DataDependenceProfilingDatadependenceedgesamongmemoryreferencesandfunctioncallsDetailedinformationtype:flow,anti,output,orinputprobability:frequencyofoccurrenceWhenloopsaretargeteddependencedistance:limited2023/1/1132PCYew-TaiwanOverheadofProfiling96110102121120020406080bzip2craftygapgccgzipmcfparserperlbmktwolfvortexvpraverageXtimessloweraliasDDwithoutdistanceDDforinnermostloopsDD4-levelloopsCompiler:ORCversion2.0Machine:Itanium2,900MHzand2GmemoryBenchmarks:SPECCPU2000IntInstrumentationoptimizationhasbeendone2023/1/1133PCYew-TaiwanTechniquestoReduceProfilingOverheadReducethespacerequirementbyhashtableLargergranularityofaddressSmalleriterationcounterSamplingSamplethesnapshotsofproceduresorloopsinsteadofindividualreferencesUseinstrumentation-basedsamplingframeworkSwitchatproceduresorloops2023/1/1134PCYew-TaiwanConclusionsMicroprocessorshavecaughtupwithsupercomputersin’90andhavegonemulti-coreItisnon-trivialtoapplycurrentsupercomputingtechnologiestogeneral-purposeapplicationsNewarchitecturalsupportsuchasthread-levelspeculativeexecution,andnewcompilertechniquessuchasspeculativeoptimizationsusingaliasanddatadependenceprofiling,evendynamicoptimizationatruntime,arecrucial–asalwaysAveryexcitingandneweraforparallelprocessingmighthavearrived(especiallyinembeddedsystems)–finally!2023/1/1135PCYew-TaiwanReferencesJ.Linetal,ACompilerFrameworkforSpeculativeAnalysisandOptimizations,Proc.OfACM/SIGPLANConf.OnProgrammingLanguageDesignandImplementation(PLDI),June2003,alsoinACMTrans.OnArchitectureandCodeOptimization(TACO),Vol.1,No.3,Sept.2004,pp.247-271J.Linetal,RecoveryCodeGenerationforGeneralSpeculativeOptimizations,toappearinACMTrans.OnArchitectureandCodeOptimization(TACO)2005.(3)J.Linetal,SpeculativeRegisterPromotionUsingAdvancedLoadAddressTable(ALAT),Proc.OfIEEE/ACMInt’lSymp.OnCodeGenerationandOptimization(CGO),March2003(4)T.Chenetal,DataDependenceProfilingforSpeculativeOptimizations,Proc.OfInt’lConfonCompilerConstruction(CC),March2004(5)T.Chenetal,AnEmpiricalStudyontheGranularityofPointerAnalysisinCprograms,Proc.15thWorkshoponLanguagesandCompilersforParallelComputing(LCPC),August2002(6)J.Y.Tsaietal,TheSuperthreadedProcessorArchitecture,IEEETransonComputers,specialissueonMultithreadedArchitecture,Vol.48,No.9,Sept19992023/1/1136PCYew-TaiwanControlSpeculationld.s:movetheloadoperationacrossthebarri