A Competitive Analysis of Load Balancing Strategie

,,1{18()cKluwerAcademicPublishers,Boston.ManufacturedinTheNetherlands.ACompetitiveAnalysisofLoadBalancingStrategiesforParallelRayTracingALANHEIRICH&[e-mail],[e-mail]erSystems,2011N.ShorelineBlvd.,MountainView,CA94043DepartmentofComputerScience,CaliforniaInstituteofTechnology,Pasadena,CA91125Editor:H.ArabniaAbstract.Thispaperexaminestheeectivenessofloadbalancingstrategiesforraytracingonlargeparallelcomputersystemsandclustercomputers.Popularstaticloadbalancingstrategiesareshowntobeinadequateforrenderingcompleximageswithcontemporaryraytracingalgorithms,andforrenderingNTSCresolutionimageson128ormorecomputers.Strategiesbasedonimagetilingareshowntobeineectiveexceptonverysmallnumbersofcomputers.Adynamicloadbalancingstrategy,basedonadiusionmodel,isappliedtoaparallelMonteCarlorenderingsystem.Thediusivestrategyisshowntoremedythedefectsofthestaticstrategies.Ahybridstrategythatcombinesstaticanddynamicapproachesproducesnearlyoptimalperformanceonavarietyofimagesandcomputersystems.Thetheoreticalresultsshouldberelevanttootherrenderingandimageprocessingapplications.Keywords:loadbalancing,raytracing,rendering,graphics,imageprocessing,diusion.1.IntroductionHighqualitycomputergeneratedimagescanattaintheclarityandrealismofpho-tographs.Techniquesforphoto-realisticimagesynthesismodelthetransportoflightthroughgeometricallycomplexscenes.Themostpopularofthesetechniques,raytracingandradiosity[7,11]requiremassiveamountsofoatingpointcalcu-lations,comparabletotherequirementsofthelargestproblemsincomputationalscienceandengineering.Ithaslongbeenrealizedthatparallelcomputerscanbeaneectivewaytoacceleratethesecomputations[5,10,14].Theadventofcommoditybasedclustercomputinghasmadeitpossibletoren-derphoto-realisticimagesinreasonabletimeonmodestbudgets.Totakeasingleexample,aparallelrenderingsystemrunningona$50,000commodityclustercom-puter(the3.2GFlopsNASA/CaltechBeowulfsystem)rendersacompleximage,whichtakesclosetoanhouronahighperformanceworkstation,inundertwomin-utes[10,16,17].Furtherspeedupscanbeobtainedbylargerclustersandhighperformanceparallelcomputers.Thesespeedupsaremostimportantininteractivesettingswhereahumanisin-the-loopwaitingforimagestoberendered.Thesesettingsoccurinproductdesign,architecturalwalkthroughs,andinpreviewingcommercialanimation.Inthefaceofdemandingperformancerequirementsitisnecessarytousecomputingresourceseciently.Thisrequiresaneectiveloadbalancingstrategythatcandistributeworkamongthecomputerswithoutaddingsignicantlytotheoverheadofthecomputation.2Thispapercomparestheeectivenessofpopularstrategiesforloadbalancingraytracingcomputationsonlargeparallelcomputersystems.Itconsidersstaticimagepartitioningstrategies,bothwithandwithoutrandomization,andcomparesthemtoadynamicschemebasedonadiusionmodel[9].Usingbothoinesimulation,andonlineperformancemeasurements,thepaperdemonstratesthatstaticstrategiesproduceunacceptablelevelsofworkloadimbalanceinrenderingcompleximages.Thispointisunderscoredbyananalysisoftheeectivenessofrandomizationstrategies,whichshowsthatthesestrategiesdonotscaleeectivelytolargenumbersofprocessors.Underasetofgenerousassumptions,pixellevelrandomassignmentisshowntobeineectiveforNTSCresolutionimagesonparallelcomputerswith128processorsormore.Strategiesinwhichtheimageisdividedintotiles,whicharethenrandomlydistributed,areevenlesseective,withtheeectivenessdecreasingasthetilesizeincreases.Thisanalysisshouldberelevanttootherrenderingandimageprocessingapplications.Thepaperconcludesbymeasuringtheonlineperformanceofadynamicloadbalancingschemebasedonadiusionmodel.Suchschemes,whichcanbeimple-mentedasaformofwork-stealing,havepreviouslybeenanalyzedandshowntoscalewithoutlimit[8,9].Inthispaperthesepredictionsaretestedempiricallybymeasuringtheperformanceoftheseschemesonsubstantialtestproblems.Ingen-eralthedynamicschemeprovedatleastaseectiveasthebestofthestaticschemesandwasusuallysuperior.Thebestresultswereobtainedwithahybridstrategy,inwhichtheproblemwasinitializedusingthebeststaticscheme,andsubsequentlyrebalancedusingthedynamicscheme.Withthehybridstrategysomeresultswerewithinsecondsoftheoptimaltimeonrunsthatlastedforoveranhour.2.RaytracingonparallelcomputersRaytracingalgorithmsestimatetheintensityandwavelengthsoflightenteringthelensofavirtualcamerainasimulatedenvironment.Thesequantitiesareestimatedatdiscretepointsintheimageplanethatcorrespondtopixels.Theestimatesaretakenbysendingraysoutofthecameraandintothescenetoapproximatethelightreectedbacktothecamera.Thisprocessrequiresndingpointsofintersectionamongraysandobjectsintheenvironment,acommongeometricalproblemknownasraycasting.Whentheseestimatesfaithfullyreectthescatteringpropertiesofmaterialsandtheemissivepropertiesoflightsourcestheresultscanbebreathtaking,andevenindistinguishablefromphotographs.Thecosttocomputeindividualpixelscanvarydramatically,dependingonthecomplexityofthemodelbeingrenderedandthealgorithmemployed.Dierentsurfaceswillscatterdierentamountsoflight,requiringdierentamountsofcom-putationtofollowtheass