Continuous Program Optimization A Case Study

ContinuousProgramOptimization:ACaseStudyTHOMASKISTLERandMICHAELFRANZUniversityofCalifornia,IrvineMuchofthesoftwareineverydayoperationisnotmakingoptimaluseofthehardwareonwhichitactuallyruns.Amongthereasonsforthisdiscrepancyarehardware/softwaremismatches,modularizationoverheadsintroducedbysoftwareengineeringconsiderations,andtheinabilityofsystemstoadapttousers'behaviors.Theobvioussolutiontotheseproblemsistodelaycodegenerationuntilloadtime.Thisistheearliestpointatwhichapieceofsoftwarecanbene-tunedtotheactualcapabilitiesofthehardwareonwhichitisabouttobeexecuted,andalsotheearliestpointatwichmodularizationoverheadscanbeovercomebyglobaloptimization.Astillbettermatchbetweensoftwareandhardwarecanbeachievedbyreplacingthealreadyexecutingsoftwareatregularintervalsbynewversionsconstructedon-the-flyusingabackgroundcodere-optimizer.Thisnotonlyenablestheuseofliveprolingdatatoguideoptimizationdecisions,butalsofacilitatesadaptationtochangingusagepatternsandthelateadditionofdynamiclinklibraries.Thispaperpresentsasystemthatprovidescodegenerationatload-timeandcontinuouspro-gramoptimizationatrun-time.First,thearchitectureofthesystemispresented.Then,twooptimizationtechniquesarediscussedthatweredevelopedspecicallyinthecontextofcontin-uousoptimization.Therstoftheseoptimizationscontinuallyadjuststhestoragelayoutsofdynamicdatastructurestomaximizedatacachelocality,whilethesecondperformsprole-driveninstructionre-schedulingtoincreaseinstruction-levelparallelism.Thesetwooptimizationshaveverydierentcost/benetratios,presentedinaseriesofbenchmarks.Thepaperconcludeswithanoutlooktofutureresearchdirectionsandanenumerationofsomeremainingresearchproblems.Theempiricalresultspresentedinthispapermakeacaseinfavorofcontinuousoptimization,butindicatethatitneedstobeappliedjudiciously.Inmanysituations,thecostsofdynamicoptimizationsoutweightheirbenet,sothatnobreak-evenpointiseverreached.Infavorablecircumstances,ontheotherhand,speed-upsofover120%havebeenobserved.Itappearsasifthemainbeneciariesofcontinuousoptimizationaresharedlibraries,whichatdierenttimescanbeoptimizedinthecontextofthecurrentlydominantclientapplication.CategoriesandSubjectDescriptors:D.3.4[ProgrammingLanguages]:Processors|Run-timeEnvironments;D.3.4[ProgrammingLanguages]:Processors|CodeGeneration;D.3.4[Pro-grammingLanguages]:Processors|Compilers;D.3.4[ProgrammingLanguages]:Proces-sors|OptimizationGeneralTerms:DynamicCodeGeneration,ContinuousProgramOptimization,DynamicRe-OptimizationAuthors'currentaddresses:ThomasKistler,TransmetaCorporation,3940FreedomCircle,SantaClara,CA95054.MichaelFranz,DepartmentofInformationandComputerScience,UniversityofCaliforniaatIrvine,Irvine,CA92697{3425.PartsofthisworkarefundedbyaCAREERawardfromtheNationalScienceFoundation(CCR{97014000)andbytheCaliforniaMICROProgramwithindustrialsponsorMicrosoftResearch(ProjectNo.99-039).AprecursortothechapteronthesimilarityofprolingdatapreviouslyappearedasarefereedcontributionintheProceedingsoftheWorkshoponProleandFeedback-DirectedOptimization,Paris,France,October1998.2
T.KistlerandM.Franz1.INTRODUCTIONInthewakeofdramaticimprovementsinprocessorspeed,itisoftenoverlookedthatmuchofthesoftwareineverydayoperationisnotmakingthebestuseofthehardwareonwhichitactuallyruns.Thevastmajorityofcomputersareeitherrunningapplicationprogramsthathavebeenoptimizedforearlierversionsofthetargetarchitecture,or,worsestill,areemulatinganentirelydierentarchitectureinordertosupportlegacycode.Therstreasonwhyhardwareandsoftwareareoftenmismatchedislinkedtothespeedoftechnologyevolution.Usersdemandbackwardcompatibilityandareoftenunwillingtogiveupexistingsoftwarewhenupgradinghardware.Asaresultofthis,animmenseamountoflegacycodeisinuseeveryday:16-bitsoftwareon32-bitpro-cessors,emulatedMC680x0codeonPowerPCMacintoshcomputers,andsoonalsoIA32codeonIA64hardware.Simultaneously,purelylogisticalconstraintsmakeitunfeasibleforsoftwarevendorstoprovideseparateversionsofeveryprogramforeveryparticularhardwareimplementationofaprocessorarchitecture.Justcon-sider:thereareseveralmajormanufacturersofIA32-compatibleCPUs,andeachofthesehasaproductlinespanningseveralprocessors|thetotalvariabilityisfartoogreattomanageinacentralizedfashion.Thesecondreasonwhythecapabilitiesofthehardwarearenotexploitedtothefullesthastodowithsoftwareengineeringconcerns.Increasingly,softwareisdevel-opedanddistributedassmallercomponentsthatarelinkedtogetherdynamicallyonlyattheend-userssite.Unfortunately,thereisamodularizationcostassociatedwithseparatecompilation|sinceneithertheend-user'scongurationnorthecom-ponents'interactionschemesareknownatcompile-time,manytraditionalglobalcodeoptimizationscannotbeappliedacrosscomponentboundaries.Theaddedbenetsofcomponent-orientationareusuallysogreatthatthisdrawbackisreadilyacceptedbysoftwaredevelopersaswellasusers.Theobvioussolutiontoovercomingbothoftheseperformanceimpedimentssi-multaneouslyistodelaycodegenerationatleastuntilloadtime.Notonlyarethehardwarecharacteristicsofthetargetmachinedeniteatthispoint,butload-timecodegenerationalsomakesitpossibletoperfor