搜索
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.Thesetwooptimizationshaveverydi erentcost/bene tratios,presentedinaseriesofbenchmarks.Thepaperconcludeswithanoutlooktofutureresearchdirectionsandanenumerationofsomeremainingresearchproblems.Theempiricalresultspresentedinthispapermakeacaseinfavorofcontinuousoptimization,butindicatethatitneedstobeappliedjudiciously.Inmanysituations,thecostsofdynamicoptimizationsoutweightheirbene t,sothatnobreak-evenpointiseverreached.Infavorablecircumstances,ontheotherhand,speed-upsofover120%havebeenobserved.Itappearsasifthemainbene ciariesofcontinuousoptimizationaresharedlibraries,whichatdi erenttimescanbeoptimizedinthecontextofthecurrentlydominantclientapplication.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.2T.KistlerandM.Franz1.INTRODUCTIONInthewakeofdramaticimprovementsinprocessorspeed,itisoftenoverlookedthatmuchofthesoftwareineverydayoperationisnotmakingthebestuseofthehardwareonwhichitactuallyruns.Thevastmajorityofcomputersareeitherrunningapplicationprogramsthathavebeenoptimizedforearlierversionsofthetargetarchitecture,or,worsestill,areemulatinganentirelydi erentarchitectureinordertosupportlegacycode.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