Meta-Scheduling and Task Reallocation in a Grid En

Meta-SchedulingandTaskReallocationinaGridEnvironmentYvesCaniou,EddyCaron,GhislainCharrier,FrédéricDesprezUniversitédeLyon,LIP/ÉNSLyonADVCOMP’09–October132009MotivationsContextMulti-clustergridMeta-scheduler(globalscheduling)Resourcemanagementsystems(localscheduling)ProblemsUserstendtoover-evaluatewalltimesSchedulingimpactedbytheseerrorsovertimeGoalsMinimizethejobswaitingtimebyreallocatingthemComparedifferentreallocationheuristicsG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment2/26MotivationsContextMulti-clustergridMeta-scheduler(globalscheduling)Resourcemanagementsystems(localscheduling)ProblemsUserstendtoover-evaluatewalltimesSchedulingimpactedbytheseerrorsovertimeGoalsMinimizethejobswaitingtimebyreallocatingthemComparedifferentreallocationheuristicsG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment2/26MotivationsContextMulti-clustergridMeta-scheduler(globalscheduling)Resourcemanagementsystems(localscheduling)ProblemsUserstendtoover-evaluatewalltimesSchedulingimpactedbytheseerrorsovertimeGoalsMinimizethejobswaitingtimebyreallocatingthemComparedifferentreallocationheuristicsG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment2/26OutlineIntroductionGridRPCResourcemanagementsystemsExperimentalframeworkSimulatorAlgorithmsSimulationsSimulationsresultsDiscussionsConclusionandfutureworksG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment3/26OutlineIntroductionGridRPCResourcemanagementsystemsExperimentalframeworkSimulatorAlgorithmsSimulationsSimulationsresultsDiscussionsConclusionandfutureworksG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment4/26GridRPCArchitectureRPCRemoteProcedureCallRequestAgentServerClientCallRegisterResultsIdentifierGridRPCServerComputerequestsAgentSelectaservertoexecuteacomputationalrequestClientAsktheagentforaserverandsendtheserveracomputationalrequestG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment5/26GridRPCArchitectureRPCRemoteProcedureCallRequestAgentServerClientCallRegisterResultsIdentifierGridRPCServerComputerequestsAgentSelectaservertoexecuteacomputationalrequestClientAsktheagentforaserverandsendtheserveracomputationalrequestG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment5/26ResourcemanagementsystemsReservecomputationalresourcesLocalschedulingisperformedtochoosethejobsexecutionorderFirstComeFirstServe(FCFS)PBS,SGE,Maui...ConservativeBackfilling(CBF)Maui,LoadLeveler,OAR...G.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment6/26BatchalgorithmsFCFSProcessorsTimet0t1CBFProcessorsTimet0t1G.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment7/26BatchalgorithmsFCFSProcessorsTimet0t1CBFProcessorsTimet0t1G.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment7/26OutlineIntroductionGridRPCResourcemanagementsystemsExperimentalframeworkSimulatorAlgorithmsSimulationsSimulationsresultsDiscussionsConclusionandfutureworksG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment8/26SimulatorSimgridAPIstodevelopdistributedapplicationssimulatorsSimbatchLibrarysimulatingbatchalgorithmsdevelopedwiththeMSGAPIofSimgridReallocationssimulatorSimgridapplication(MSGAPI)usingSimbatchG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment9/26SimulatorarchitectureSameasGridRPC:ServerRunsontheclusterfrontal.SubmitsjobstotheRMSAsksanestimatedcompletiontimeofajobtotheRMSCancelajobinthesystemSendsinformationtotheagentAgentMeta-schedulerManagesreallocationClientAskstheagentforaserverforeachjobSendsthejobstotheserversG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment10/26SchedulingalgorithmsMinimumCompletionTime(MCT)OnlinealgorithmChoosestheserverabletocompletethejobtheearliestMinMin/MaxMinOfflinealgorithmsComputeMCTforeachjobChoosesthejobwiththemin/maxMCTStartsagainontheremainingjobsG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment11/26ReallocationalgorithmgetwaitingjobsoneachserverwhiletherearejobstotestforreallocationexecuteMCT/MinMin/MaxMinifnewECToldECTthencanceljoboncurrentserversubmitjobtotheotherserverremovejobfromthelistofjobstotestG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment12/26SimulatedjobsTracesofGrid’5000Noadvancedreservations6scenariosNoinput/outputdataMonthBordeauxLyonToulouseTotalJanuary1308458348814155February5822269511239640March11673831594920937April332501330146136041May67652179157310517June4094354015489182G.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment13/26SimulatedplatformMeta-scheduler(MCT)3clustersBordeaux(650cores)Lyon(270cores)Toulouse(434cores)HeterogeneousBordeaux:slowestclusterLyon:20%fasterthanBordeauxToulouse:40%fasterthanBordeauxThethreeclustersusethesamebatchalgorithmG.Charrier,ÉNSLyonMeta-SchedulingandTaskReallocationinaGridEnvironment14/26OutlineIntroductionGridRPCResourcemanagementsystemsExperimentalframeworkSimulatorAlgorithmsSimulationsSimulationsresultsDiscussionsConclusiona