AComparisonofLocalandGangSchedulingonaBeowulfClusterPeterStrazdinsandJohnUhlmann,DepartmentofComputerScience,AustraliunNationalUniversityActonACT0200AUSTRALIA{Peter.Strazdins@cs.anu.edu.au,John.Uhlmann@anu.edu.au]Abstract1IntroductionGangscheduling[6],oroneofitsmanyvariants[II,GangSchedulingandrelatedtechniquesarewidelybe-16,191,iswidelybelievedtobenecessaryforoptimaldis-lievedtobenecessaryforefficientjobschedulingondis-tributedmemorymultiprocessorresourceutilizationwithtributedmemoryparallelcomputers.Thisishecausetheytime-sharedjobswithmedium-tofine-grainedcommuni-minimizecontextswitchingoverheadsandpermittheparal-cationpatterns.leljobcurrentlyrunningtoprogressatthefastestpossiblerate.Thesetechniquesrequirethat,oneachnode,theprocessesrelatedtoaparticularparalleltask(gangs)arescheduledHowevecinthecaseofclustercomputers,andpanicu-torunsimultaneously.GangsarepackedtogetherandarelarlythosewithCOTSnetworks,thesebenefitscanbeout-preemptedandrescheduledasaunit.Aswellasreducingweighedinthemultiplejobtime-sharingcontextbythelosscontextswitchingoverheads.thisensuresmessagesassoci-theabilitytoutilizetheCPUforotherjobswhenthecurrentatedwithaparalleljobarereceivedassoonaspossiblearter;ohiswaitingformessages.delively,andhencepermitsthatparalleljobtoprogressop-timally.ExperimentsonaLinuBeowulfclusterwithIOOMbfastGangScheduling(alsoknownasexplicitco-scheduling)EthernetswitchesaremndecomparingtheScorebuddy-normallyrequiresconsiderableinfrastructuretobeaddedtobasedgangschedulingwithlocalscheduling(pmvidedbycluster.ExistingsystemsincludeScore[IO]andParPar[9].theLinu2.4kernelwithMPIimplementedoverTCP/IP).Analternativeisimplicitco-scheduling,wherethepro-Resultsforcommunication-intensivenumericalapplicationscessesinthegangarenotexplicitlycoscheduledbutshouldon16nodesrevealthatgangschedulingresultsin'slow-coschedulethemselvesthroughtheirbehaviourandlocaldowns'uptoafactoroftwogreaterfor8simultaneousjobs.schedulingpolicies,e.g.ifamessagearrivesforanon-Thi